BFSで実際に見つかったパスを見つけるにはどうすればよいですか？

Question

私が解決しようとしている問題は、MRTシステムのツリーに関係しています。

各ノードは最大4つのポイントに接続することができ、多くを単純化します。ここに私の考えがあります。

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

私はすべてのポイントを検索するBFSために必要なすべての情報を保存するためにコードを書くことができますが、私の主な関心事は、BFSが適切にポイントを見つけていても、どのように私はそのパスを知ることができる、ということでしょうか？

BFSは各レベルを検索し、その中の1つが目的地に到達すると、実行ループから飛び出し、訪問したキューと未訪問のキューを取得します。ユーザーにどのように伝えるべきでしょうか訪問したキューがBFSが検索したすべてのノードでいっぱいになったときに訪問する必要があるのは何ですか？そうするには

Answer 1

、あなたはvを「発見」することを各ノードv、頂点uからマップされ、[頂点から頂点へ] map:V->Vを保存する必要があります。

BFSの繰り返し中にこのマップを作成します。

その後 - あなたは単に[地図で]ターゲット・ノードから行くことによってパスを再構築することができます - あなたが元に戻るまでアップし、それが[もちろん、逆に...]ヨールパス

です

頂点を列挙すると、このマップは配列として実装できることに注意してください。