问铁路线路的数据结构

EN

听起来像是一个直截了当的图问题，(对我来说)用图对铁路网络实际看起来的方式建模听起来很直观。

也就是说，每个桩号都有一个图形节点，其中的边表示它们之间的铁路连接。

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

首先，您有铁路网:这是非常自然地表示为图中的节点的车站和连接节点的边的铁路连接。

其次，你有火车，或者换一种说法，就是线路。这最自然地表示为通过上图的一组路径，每条路径对应于不同的列车。

我假设您需要所有可能的路由，其形式为

在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)