data-structures - 巡回グラフ内の任意の 2 つのノード間のすべてのパスを検索するための幅優先検索

Question

巡回グラフの 2 つのノード間のすべてのパスを取得するために BFS を使用しようとしています。BFS は以前のノードを追跡しないことがわかったので、同じことを達成するには他のコレクションを追加する必要があります。

質問は - BFS を使用してノード内のすべてのパスを取得するのを避け、DFS を使用するか、BFS を使用することで解決策が得られるかどうかです。

そこにある場合は、同じロジックを教えてください。

Answer 1

単純なパス (サイクルなし) のみを見つけたいと仮定します。そうしないと、無限のパスが存在する可能性があります。これが要件でない場合、理論的には BFS または DFS のいずれかが機能します (ただし、DFS は 1 つのサイクルを探索し続け、他の短いパスを見つけることはありません) が、この要件を解除することは実際には意味がありません。

BFS と DFS の両方で、ノードごとに処理済みフラグを設定して、循環グラフで無限に多くのパスが発生しないようにする必要があります。

次の点を考慮してください。

A with children B, C
B with children C, D
C with children B, D

BFS を使用すると、C を処理する前に B が処理済みとしてマークされるため、A -> C -> B -> D を見逃すことになります。

DFS では、ツリーを上に戻るときに処理済みフラグをリセットする必要があるため、これは問題になりません。

ノードごとにこれまでのパス全体を追跡することもできますが、多くの余分なストレージ スペースと時間が必要になるため、これは現実的ではありません。

BFS の処理済みフラグを取り除き、パス内のノード数 > ツリー内のノード数のときに処理を停止し、単純ではないすべてのパスを出力から削除できます。