98

主に、BFS ではなく、グラフ内のサイクルを見つけるために DFS が使用されます。理由はありますか？どちらも、ツリー/グラフをトラバースしているときに、ノードが既にアクセスされているかどうかを確認できます。

4

10 に答える 10

84

深さ優先検索は、幅優先検索よりも早くバックトラックできるため、メモリ効率が高くなります。コール スタックを使用すると実装も簡単になりますが、これはスタックをオーバーフローしない最長パスに依存します。

また、グラフが方向付けされている場合は、ノードにアクセスしたかどうかだけでなく、どのようにしてそこに到達したかを覚えておく必要があります。そうでなければ、サイクルを見つけたと思うかもしれませんが、実際には 2 つの別個のパス A->B しかありませんが、それはパス B->A があるという意味ではありません。例えば、

から BFS を実行0すると、サイクルが存在すると検出されますが、実際にはサイクルはありません。

深さ優先検索を使用すると、下降するときにノードを訪問済みとしてマークし、バックトラックするときにそれらのマークを解除できます。このアルゴリズムのパフォーマンスの改善については、コメントを参照してください。

有向グラフでサイクルを検出するための最適なアルゴリズムについては、 Tarjan のアルゴリズムを参照してください。

于 2010-05-19T21:44:45.090 に答える
31
  1. DFSは実装が簡単です
  2. DFSがサイクルを検出すると、スタックにはサイクルを形成するノードが含まれます。同じことはBFSには当てはまらないため、見つかったサイクルも印刷する場合は、追加の作業を行う必要があります。これにより、DFSがはるかに便利になります。
于 2010-05-19T21:51:24.560 に答える
13

グラフが無向である場合、BFS は合理的である可能性があります (有向グラフでサイクルを報告する BFS を使用した効率的なアルゴリズムを示すゲストになってください!)、各「交差エッジ」がサイクルを定義します。クロス エッジが{v1, v2}であり、それらのノードを含むルート (BFS ツリー内) がrである場合、サイクルはr ~ v1 - v2 ~ r(~はパス、-単一のエッジ) であり、DFS とほぼ同じように簡単に報告できます。

BFS を使用する唯一の理由は、(無向) グラフのパスが長く、パス カバーが小さい (つまり、深くて狭い) ことがわかっている場合です。その場合、BFS は、DFS のスタックよりもキューに必要なメモリが比例して少なくなります (もちろん両方とも線形です)。

他のすべてのケースでは、DFS が明らかに勝者です。有向グラフと無向グラフの両方で機能し、サイクルを報告するのは簡単です。祖先から子孫へのパスにバックエッジを連結するだけで、サイクルが得られます。全体として、この問題に関しては BFS よりもはるかに優れて実用的です。

于 2010-05-20T08:53:01.610 に答える
2

ツリー内のランダムな場所にサイクルを配置すると、DFSは、ツリーの約半分が覆われたときにサイクルにヒットする傾向があり、サイクルが進む場所をすでに通過した時間の半分と、通過しない時間の半分（そして、ツリーの残りの半分で平均してそれを見つけるでしょう）、それでそれはツリーの平均で約0.5 * 0.5 + 0.5 * 0.75=0.625を評価します。

ツリー内のランダムな場所にサイクルを配置すると、BFSは、その深さでツリーのレイヤーを評価した場合にのみサイクルにヒットする傾向があります。したがって、通常、バランス二分木の葉を評価する必要があり、その結果、通常、より多くのツリーが評価されます。特に、3/4の時間、2つのリンクの少なくとも1つがツリーの葉に表示されます。これらの場合、ツリーの平均3/4（リンクが1つある場合）または7/を評価する必要があります。ツリーの8つ（2つある場合）なので、1/2 * 3/4 + 1/4 * 7/8 =（7 + 12）/ 32 =21/32=を検索することを期待できます。リーフノードから離れてサイクルが追加されたツリーを検索するコストを追加することなく、ツリーの0.656...。

さらに、DFSはBFSよりも実装が簡単です。したがって、サイクルについて何かを知らない限り、これを使用します（たとえば、サイクルは検索元のルートの近くにある可能性が高く、その時点でBFSが有利になります）。

于 2010-05-19T21:53:05.163 に答える
1

グラフが循環的であることを証明するには、グラフに 1 つの循環があることを証明する必要があります (エッジが直接的または間接的にそれ自体を指しています)。

DFS では、一度に 1 つの頂点を取り、サイクルがあるかどうかを確認します。サイクルが見つかるとすぐに、他の頂点のチェックを省略できます。

BFS では、多くの頂点エッジを同時に追跡する必要があり、多くの場合、最後にサイクルがあるかどうかを確認します。グラフのサイズが大きくなるにつれて、BFS は DFS と比較してより多くのスペース、計算、および時間を必要とします。

于 2015-07-28T01:32:24.767 に答える
0

再帰的な実装について話しているのか、反復的な実装について話しているのかによって異なります。

再帰的 DFS は、すべてのノードを 2 回訪問します。反復 BFS はすべてのノードを 1 回訪問します。

サイクルを検出したい場合は、隣接関係を追加する前後の両方で、ノードを「開始」するときとノードを「終了」するときの両方で、ノードを調査する必要があります。

これには Iterative-BFS でより多くの作業が必要になるため、ほとんどの人は Recursive-DFS を選択します。

たとえば std::stack を使用した Iterative-DFS の単純な実装には、Iterative-BFS と同じ問題があることに注意してください。その場合、ダミー要素をスタックに配置して、ノードでの作業がいつ「終了」したかを追跡する必要があります。

Iterative-DFS がノードをいつ「終了」するかを決定するために追加の作業を必要とする方法の詳細については、この回答を参照してください (TopoSort のコンテキストで回答):

再帰なしの DFS を使用したトポロジカル ソート

うまくいけば、ノードの処理をいつ「終了」するかを決定する必要がある問題に対して人々が Recursive-DFS を好む理由を説明できます。

于 2016-02-09T20:28:46.703 に答える