如何做列表遍歷？

我最近開始一個項目，涉及使用倫敦Ungerground數據集中的數據，以便查找距離給定站點數量爲n分鐘的路線。如何做列表遍歷？

到目前爲止，我已經能夠解析來自數據集的數據，並在每個站之間創建可能的路線。我現在有這具有以下屬性路由對象的列表：

Parent - the first station 
Child - the next linked station 
Line - whichever line the station is on 
Time - the time between the two stations

的數據我現在有，使用VICTORIA作爲起點站是：

我已經格式化我的輸出使它更容易讀取，但每行都是路由對象的表示。所以你有起始站，時間，下一站和線路。

VICTORIA => 1 <= PIMLICO : Victoria 
VICTORIA => 2 <= GREEN PARK : Victoria 
VICTORIA => 2 <= ST JAMES PARK : Circle 
VICTORIA => 2 <= SLOANE SQUARE : Circle 
PIMLICO => 2 <= VAUXHALL : Victoria 
GREEN PARK => 2 <= OXFORD CIRCUS : Victoria 
GREEN PARK => 1 <= WESTMINSTER : Jubilee 
GREEN PARK => 2 <= BOND STREET : Jubilee 
GREEN PARK => 1 <= PICCADILLY CIRCUS : Piccadilly 
GREEN PARK => 1 <= HYDE PARK CORNER : Piccadilly 
ST JAMES PARK => 1 <= WESTMINSTER : Circle 
SLOANE SQUARE => 1 <= SOUTH KENSINGTON : Circle 
VAUXHALL => 2 <= STOCKWELL : Victoria 
VAUXHALL => 2 <= PIMLICO : Victoria 
OXFORD CIRCUS => 1 <= PICCADILLY CIRCUS : Bakerloo 
OXFORD CIRCUS => 2 <= REGENTS PARK : Bakerloo 
OXFORD CIRCUS => 2 <= TOTTENHAM COURT ROAD : Central 
OXFORD CIRCUS => 1 <= BOND STREET : Central 
OXFORD CIRCUS => 2 <= GREEN PARK : Victoria 
OXFORD CIRCUS => 1 <= WARREN STREET : Victoria

從VICTORIA收集所有可能的路線的最佳方法是什麼？

例如：

VICTORIA > GREEN PARK > WESTMINSTER 
VICTORIA > GREEN PARK > BOND STREET 
VICTORIA > PIMLICO > VAUXHALL

來源

2013-07-02 gb1986

http://en.wikipedia.org/wiki/Backtracking –

這個問題似乎是題外話，因爲它是作業，回答傷害OP ... – eglasius

@eglasius，這不是作業，我避難沒有要求解決方案，我已經要求一種方法，它會指向我解決這個問題的方向。 – gb1986

聽起來像一個圖論的問題。我的最愛！

找到「所有可能的路線」的問題是，根據您提供的數據（或此情況下的任何實際數據集），您將遇到循環。因此，對於任何給定的路線，您將需要確保每個站僅被訪問一次。

既然你有一個單一的起點，我會推薦Djikstra's Alogrithm。這將找到一條從VICTORIA到其他所有車站的路徑（實際上是最短路徑）。至少，每一個可以到達的站點。這是一個衆所周知的，快速且相對容易實現的算法。在O（n^2）時間內正常運行，但可以按照一些數據結構進行O（m + nlogn）運算。

希望至少讓你走上正軌！

來源

2013-07-02 12:10:48

+10

我希望最後一行是有意的。 –

@Pat Lillis，謝謝你對這個問題的詳細解答。 – gb1986

當你的路徑長度> n分鐘時，你也可以阻止Dijkstra –

如何做列表遍歷？

回答

相關問題