私はどこかで、BFSが解決策を見つけるために、DFSが保証されていないことを読みました。なぜですか？私はこれがどのように真実であるかを本当に理解していません..誰かがこれを証明する私のためのケースを示すことができますか？
質問する
4682 次
3 に答える
5
DFSは、深さ優先探索であるため、無限分岐でスタックし、探している頂点に到達しない可能性があります。BFSは、どのブランチにあるかに関係なく、各反復でルートから同じ距離にあるすべての頂点を通過するため、最終的に目的の頂点を見つけます。
例：
ルート->v1->v2->v3->...永遠に続く
|->u。
この例では、DFSがルートから始まり、v1に進む場合。入力したブランチは無限であるため、uに到達することはありません。BFSは、ルートからv1またはuのいずれかに移動し、次にもう一方に移動します。
于 2010-12-11T12:41:37.067 に答える
2
DFSとBFSの両方の出力（頂点の数が有限のグラフ上）は終了し、パス（またはツリーではなく、OPはそのツリーの1つのパスにのみ関心があるようです）を生成します。グラフにサイクルがあるかどうかは関係ありません。どちらの手順でも、どの頂点がすでにアクセスされたかが記録され、同じ頂点に複数回アクセスすることが回避されるためです。DFS / BFSの適切な実装はこれを行います。そうしないと、非巡回グラフのみに制限されます（CLRSで指定された擬似コードを参照してください）。
@yuribが述べたように、グラフにノードの数が無限である場合、dfsは永久にかかる可能性があります。無限のノードがあるため、どの頂点がすでにアクセスされているかを実際に追跡することはできません（潜在的に無限のメモリを使用します）。たとえアクセスしたとしても、探している頂点を含まない一意の頂点を含む無限のパスが存在する可能性があります。 。
ただし、DFSが常に最短パスを見つけるとは限らない理由はそれだけではありません。有限グラフでも、DFSは最短経路を見つけられない場合があります。
主な理由は、BFSは、距離x + 1のノードに移動する前に、ルートから距離xのすべてのノードを常に探索するためです。したがって、ノードが距離kで見つかった場合、ルートからそのノードまでの最小距離はkであり、k-1、k-2、...、0ではないことを確認できます（そうでない場合は、以前に遭遇したはずです）。
一方、DFSは基本的に、あるパスに沿ってノードを探索し、そのパスに新しいノードがなくなるまで、別のパスを調べます。DFSは、基本的に任意の順序で、ノードの各後続を1つずつ探索します。これは、ターゲットノードが最初にそのパスをたまたま探索したという理由だけで、ターゲットノードへのより長いパスを見つける可能性があることを意味します。
上の画像では、BFSは最初にBとEを探索し、次にEを介してDに到達します-ルート->E->DとしてDへのパスを提供します。DFSは最初にBから検索を開始する可能性があるため、ルート-> B-> C-> Dのパスが見つかりますが、これは明らかに最短ではありません。
重要な決定は、Eの前にBを探索することであったことに注意してください。DFSはEを選択し、正しい答えに到達した可能性があります。しかし、一般に、最初にどのパスをたどるかを知る方法はありません（とにかく最短パスを知っている場合）。DFSの場合、検出するパスは、後続ノードを探索する順序に依存するだけであり、最短パスが生成される場合と生成されない場合があります。
于 2010-12-11T14:47:49.620 に答える
0
@yuribは正しいですが、さらに複雑です。
目的の頂点がグラフにない場合、サイクルがある場合はBFSもDFSも終了しません...サイクルを検出する手順を実行しない限り。また、サイクルを検出するための手順を実行している場合は、BFSとDFSの両方が終了します。
于 2010-12-11T13:16:49.850 に答える