当前位置：文江博客话题详情

铁路路线的数据结构

发布于 2024-12-20 21:06:43 字数 129 浏览 0 评论 0原文

铁路路线的良好数据结构是什么？我有所有火车的信息，以及它们经过的所有车站的信息。给定两个车站，我需要想出所有可能的路径。

我想出了一个图表，其中键是起始站，邻接列表代表它经过的站。

但我认为这不会给我正确的答案。

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

懷念過去 2024-12-27 21:06:43

听起来像是一个简单的图形问题，并且（对我来说）用图形对铁路网络的实际外观进行建模听起来很直观。

也就是说，每个车站都有一个图节点，边代表它们之间的铁路连接。

然后问题就变成了图搜索，有很多算法可供选择。

回复收藏 0 原文

ぃ弥猫深巷。 2024-12-27 21:06:43

首先，有铁路网络：这很自然地表示为图中的节点，铁路线是连接节点的边。

其次，有火车，或者换句话说，有线路。这最自然地表达为上图的一组路径，每条路径对应于不同的火车。

我假设您需要以下形式的所有可能的路线

在S0站乘坐T1火车，前往S1站，转乘T2火车，前往S2，等等......到达目的地。

在这种情况下，我将在单个多图结构中对铁路网络和火车进行建模，其中具有从车站 Sn 到车站 Sm 的多个边，每个边对应于从 Sn 到 Sm 的不同列车的边。其结构将是一组节点，每个节点都有一个传出边的列表。

然后执行简单的深度优先搜索，标记各个边以确保不会遍历一条边两次，如以下生成器伪代码所示：

// path is a list of edges
// src,dst are nodes

procedure generate_route (path, src, dst)
  if src == dst
    yield path
  else
    for e in all outgoing edges of src
      if e is not visited
         mark e as visited
         generate_route (path + e, e.dst, dst)

First, you have the railway network: this is very naturally expressed as stations being the nodes in a graph and railway links being the edges, which connect the nodes.

Second, you have the trains, or, put it another way, the lines. This is most naturally expressed as a set of paths through the above graph, each path corresponding to a different train.

I assume that you need all the possible routes in the form of

Take train T1 at station S0, travel to station S1, switch to train T2, travel to S2, etc... arrive at destination.

In such a case, I'd model both the railway network and the trains in a single multi- graph structure, with multiple edges leading from station Sn to station Sm, each edge corresponding to different train which passes from Sn to Sm. The structure for this would be a set of nodes, each node having a list of outgoing edges.

Then perform a simple depth first search, with marking individual edges to make sure you don't traverse an edge twice, like in the following generator pseudocode:

// path is a list of edges
// src,dst are nodes

procedure generate_route (path, src, dst)
  if src == dst
    yield path
  else
    for e in all outgoing edges of src
      if e is not visited
         mark e as visited
         generate_route (path + e, e.dst, dst)

回复收藏 0 原文

~没有更多了~