たとえば、次のグラフを見てみましょう。
ここで、頂点 3 から始めて、頂点 7 を見つけたいとしましょう。深さ優先検索 (実装によって異なります) は、最初に子を調べます。さて、この例では、議論のために、頂点 2 から開始し、頂点 4 と頂点 2 に移動し、頂点に戻って頂点 7 に移動し、問題は解決しました。
私が望むもの: x から y に到達する可能性のあるすべてのパスを取得したい (例: 3 から 7: 3,1,4,7 - 3,5,7 - 3,4,7 - 3,5,6,9,7)。深さ優先検索では得られないこと。
あなたが提案するアルゴリズムは何ですか？
ありがとうございました！
修正された BFS アルゴリズム ( http://en.wikipedia.org/wiki/Breadth-first_search ) を使用する必要があります。各頂点で、この頂点につながる隣接ノードを 1 つだけ持つのではなく、この頂点 (先行) につながる隣接ノードのリストを保存する必要があります。
これからすべてのパスを見つけたい場合は、終了ノードから開始し、すべての頂点でパスを分岐する必要があります。これには、複数の先行ノードがあり、ノードを開始するまで、各頂点の先行ノードによって作成された方法に従います。あなたが持っているすべてのブランチ。
編集: BFS の代わりに DSF アルゴリズムを使用して、同じ方法で変更できます。