0

重複の可能性:
2 つの指定されたノード間のパスを見つけますか?

有向グラフが与えられた場合、2 つのノード間のすべての可能なパスを見つけてそれらのパスを返す方法。

Java でない場合は、アルゴリズムを教えてください。検索したところ、BFS または DFS を使用していることがわかりましたが、私の場合はどちらが優れているかわかりません。そして、最短経路だけでなく、すべての経路を追跡する方法。

たとえば、次のグラフがあるとします。

1 -> 2

1 -> 3

2 -> 3

3 -> 4

ノード 1 と 4 の間のパスの場合、出力は次のようになります。

最初のパス: 1 -> 2 -> 3 -> 4

2 番目のパス: 1 -> 3 -> 4

4

1 に答える 1

2

私にとって、逆方向のトラバーサルははるかに簡単です。アルゴリズムの手順は次のとおりです。

  1. 出発点として目的地（例では4）から開始します。
  2. 宛先として 2 番目の要素を持つすべてのノードを収集します (例: (3,4))。
  3. 開始点 (3最初の繰り返し) を新しい目的地として想定し、一致するノードがなくなるまで1&の手順を繰り返します。再帰の良いシナリオ。コレクションは [(1,2), (2,3), (3,4)], [(1,3), (3,4)] として取得されます。2
  4. 上記で作成したコレクションを確認し、逆方向の宛先がソースと等しい場合はそのままにし、そうでない場合は破棄します (この場合、破棄するものはありません)。あなたは完了です。
于 2012-12-13T03:54:51.377 に答える