DFSではなくBFSのグラフに含まれていると、結果が確実に見つかるのはなぜですか？

Question

私は、DFSが解決策を見つけるのが難しいと読んだことがありますが、BFSはなぜですか？私は本当にこれがどういうものなのか分かりません。

Answer 1

DFSは、深さの最初の検索が無限の枝に詰まり、探している頂点に到達しないことがあるためです。 BFSは、どんな枝であっても、各反復のルートから同じ距離にあるすべての頂点を通過するので、最終的に必要な頂点を見つけることができます。
例：

ルート - > V1 - > V2 - > V3 - > ...に行く永遠
| - > U。

この例では、DFSがルートから始まり、次にv1に進む場合です。入力したブランチが無限であるため、決してuに到達しません。 BFSは、ルートからv1またはuのいずれかに、次にもう一方に移動します。

Answer 2

@yuribは正しいですが、さらに複雑です。

グラフに目的の頂点がない場合、サイクルが検出されない限り、BFSもDFSも終了しません。また、サイクルを検出するための手順を実行している場合は、BFSとDFSの両方が終了します。

Answer 3

（有限数の頂点を持つグラフ上の）DFSとBFSの両方の出力は終了し、パス（またはむしろツリーですが、OPはそのツリーの1つのパスに関心があるようです）。グラフにサイクルがあるかどうかは関係ありません。これは、両方のプロシージャがすでにどの頂点が訪問されたかを記録し、同じ頂点を2回以上訪問することを避けるためです。 DFS/BFSの正常な実装はこれを行います。そうしないと、非循環グラフのみに制約されます（CLRSの擬似コードを参照）。

@yuribが述べたように、グラフに無数のノードがある場合、dfsは永遠にかかる可能性があります。無限のノードが存在するので、どの頂点が既に訪問されているか（潜在的に無限のメモリをとる）を実際に追跡することはできず、もし我々が探している頂点を含まない一意の頂点を含む無限のパス。

しかし、それがDFSが常に最短パスを見つけるわけではありません。有限グラフであっても、DFSは最短パスを見つけることができません。

主な理由は、BFSは、距離x + 1のノードに移動する前に、ルートから距離xのすべてのノードを常に探索することです。したがって、あるノードが距離kにある場合、ルートからそのノードまでの最小距離がk-1、k-2、...、0ではないことが分かります。

DFSは、基本的に1つのパスに沿ってノードを探索し、別のパスを参照する前にそのパスに新しいノードがなくなるまで探索します。 DFSは、基本的に任意の順序で、ノードの各後継者を1つずつ探索します。つまり、ターゲットノードへのパスが最初に見つかったばかりなので、ターゲットノードまでのパスが長くなる可能性があります。上記画像における

、BFSは、第B及びEを探索し、次にEを介してDに到達する - root-> E-> DとDに私たちのパスを与えます。 DFSは最初にBから検索を開始することができるので、明らかに最短ではないルートroot-> B-> C-> Dを見つけることができます。

重要な決定は、Eの前にBを調べることだったことに注目してください。DFSはEをよく選択し、正解に到着した可能性があります。しかし、一般的にどの経路を先に下るかを知る方法はありません（最短経路を知ることがわかっていれば）。 DFSの場合、発見されるパスは、後続ノードを探索する順序に依存するだけであり、最短パスが得られるかどうかは問わない。