铁路线路数据结构

Question

铁路线路良好的数据结构是什么？我有关于所有列车的信息，他们所经过的所有车站。给定两个电台，我需要想出所有可能的路径。

我想出了一张图，其中key是起始站，邻接列表表示它正在通过的站。

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

Answer 1

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

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

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

Answer 2

首先，你有铁路网络：这非常自然地表示为站点是图中的节点，铁路链接是连接节点的边缘。

其次，你有火车，或换句话说，线路。这很自然地表示为通过上述图表的一组路径，每条路径对应于不同的列车。

我认为你需要

乘火车T1车站S0，旅游站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)