如何找到BFS找到的實際路徑？

Question

我試圖解決的問題涉及到一個MRT系統的樹。

每個節點最多可以連接4個點，這可以大大簡化。這是我的想法。

struct stop { 
    int path, id; 
    stop* a; 
    stop* b; 
    stop* c; 
    stop* d; 
}; 

我可以編寫代碼來保存我需要BFS搜索所有點的所有信息，但我主要關注的是，儘管BFS找到正確的點，我怎麼能知道它的路徑？

BFS將搜索每一個級別，而當它的一個到達我的目的地，它會跳出運行循環，然後，我會得到一個訪問隊列和未訪問過的隊列，我怎麼告訴用戶當訪問隊列充滿BFS搜索到的每個節點時，他需要訪問哪些內容？

Answer 1

要做到這一點，你需要存儲map:V->V [從頂點到頂點]，將從每個節點v，頂點u是「發現」 v地圖。

您將在BFS迭代期間填充此地圖。

後 - 你可以通過簡單地從[在地圖]目標節點去重構的路徑 - 直到你回來的來源，它是侑路徑[逆轉，當然...]

請注意，如果列舉頂點，則此映射可以作爲數組實現。