algorithm - 幅優先検索に対する深さ優先検索の利点、またはその逆

Question

私は2つのグラフトラバーサルアルゴリズム、深さ優先検索と幅優先検索を研究しました.両方のアルゴリズムがグラフトラバーサルの同じ問題を解決するために使用されるので、2つから選択する方法を知りたいです.つまり、その他、または特定のシナリオでどちらかを選択する理由は何ですか?

ありがとうございました

Answer 1

私にとっての主な違いは、やや理論的なものです。無限のサイズのグラフがある場合、選択した最初のパスの外に要素が存在する場合、DFS は要素を見つけることができません。基本的に、最初のパスをたどり続け、要素を見つけることはありません。BFS は最終的に要素を見つけます。

グラフのサイズが有限である場合、DFS は外れ値 (ルートとゴールの間の距離が大きい) 要素をより速く見つけ、BFS は近い要素をより速く見つけます。DFS が浅い要素のパスを選択する場合を除きます。

Answer 2

一般に、最短パスの検索に関連する問題や、多少関連する問題には、BFS の方が適しています。ここでは、1 つのノードからそれに隣接するすべてのノードに移動するため、パスの長さ 1 からパスの長さ 2 などに効果的に移動します。

反対側の DFS は、接続の問題やグラフ内のサイクルを見つけるのに役立ちます (ただし、BFS を少し変更することでサイクルを見つけることもできると思います)。DFS との接続を判断するのは簡単です。DFS プロシージャから explore プロシージャを 2 回呼び出すと、グラフが切断されます (これは無向グラフの場合です)。DFS の修正版である有向グラフの強連結成分アルゴリズムをここで見ることができます。DFS のもう 1 つのアプリケーションは、トポロジカル ソートです。

これらは、両方のアルゴリズムのいくつかのアプリケーションです。

DFS:

接続
性 強結合成分
トポロジカル ソート

BFS:

最短パス (ダイクストラは BFS の一部を変更したものです)。
グラフが二分法かどうかのテスト。

Answer 3

完全/完全なツリーの場合、DFS はツリーの深さに関して線形量のスペースを使用しますが、BFS はツリーの深さに関して指数関数的な量のスペースを使用します。これは、BFS の場合、キュー内のノードの最大数がツリーの 1 レベルのノード数に比例するためです。DFS では、スタック内のノードの最大数はツリーの深さに比例します。

Answer 4

多重連結グラフをトラバースする場合、ノードがトラバースされる順序は、トラバース メソッドによって追跡されるノードの数に (何桁も) 大きな影響を与える可能性があります。幅優先を使用すると、ある種のアルゴリズムが大幅に改善されます。深度検索を使用すると、他のものは大幅に改善されます。

極端な場合、N 個の葉ノードを持つ二分木で深さ優先検索を行うには、トラバース メソッドで lgN ノードを追跡する必要がありますが、幅優先検索では少なくとも N/2 ノードを追跡する必要があります (スキャンする可能性があるため)。任意のリーフ ノードをスキャンする前に、他のすべてのノードをスキャンします。最初のリーフ ノードをスキャンする直前に、N/2 のリーフの親ノードに遭遇しますが、それらは互いに参照していないため、個別に追跡する必要があります)。

反対に、NxN グリッドでフラッド フィルを行うには、そのピクセルがまだ色付けされていない場合、そのピクセルに色を付けてから隣接するピクセルをフラッド フィルする方法を使用すると、O(N) ピクセル座標をエンキューする必要があります。幅優先検索ですが、深さ優先を使用する場合は O(N^2) ピクセル座標。幅優先検索を使用すると、ペイントする形状に関係なく、ペイントが「広がる」ように見えます。深さ優先アルゴリズムを使用して長方形のらせんを描画する場合、各線は片側が直線で、反対側がギザギザになっています (どちらの側が直線でギザギザになるかは、使用する正確なアルゴリズムによって異なります)。直線部分はすべて描画されます。つまり、システムはすべてのギザギザの位置を個別に追跡する必要があります。