鐵路線路數據結構

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)