BFS と DFS – それらの違い

BFS と DFS の主な違い

BFS は宛先への最短パスを検索しますが、DFS はサブツリーの一番下に移動してから元に戻ります。
BFS の完全な形式は幅優先検索ですが、DFS の完全な形式は深さ優先検索です。
BFS はキューを使用して、次に訪問する場所を追跡します。一方、DFS はスタックを使用して、次に訪問する場所を追跡します。
BFS はツリーレベルに従ってトラバースしますが、DFS はツリーの深さに従ってトラバースします。
BFS は FIFO リストを使用して実装されます。一方、DFS は LIFO リストを使用して実装されます。
BFS では有限ループに陥ることはありませんが、DFS では無限ループに陥る可能性があります。

BFSとは？

BFS は、データのグラフ化、ツリーの検索、構造のトラバースに使用されるアルゴリズムです。このアルゴリズムは、グラフ内のすべての主要なノードを効率的に訪問し、正確に幅方向にマークします。

このアルゴリズムは、グラフ内の単一のノード (開始点またはソースポイント) を選択し、選択したノードに隣接するすべてのノードを訪問します。アルゴリズムが開始ノードを訪問してマークを付けると、最も近い未訪問のノードに向かって移動し、それらを分析します。

一度アクセスすると、すべてのノードがマークされます。これらの繰り返しは、グラフのすべてのノードが正常にアクセスされてマークされるまで続きます。 BFS の完全な形式は幅優先検索です。

DFSとは何ですか？

DFS は、グラフまたはツリーを深さ方向に検索または走査するためのアルゴリズムです。アルゴリズムの実行はルートノードから始まり、バックトラックする前に各ブランチを探索します。繰り返しの中で行き止まりが現れるたびに、スタックデータ構造を使用して記憶し、後続の頂点を取得し、検索を開始します。 DFS の完全な形式は深さ優先検索です。

BFS と DFS バイナリツリーの違い

BFS と DFS の重要な違いは次のとおりです。

BFS	DFS
BFS 目的地までの最短経路を見つけます。	DFS はサブツリーの一番下に移動し、その後バックトラックします。
BFS の完全な形式は幅優先検索です。	DFS の完全な形式は深さ優先検索です。
キューを使用して、次に訪問する場所を追跡します。	スタックを使用して、次に訪問する場所を追跡します。
BFS はツリーレベルに従ってトラバースします。	DFS はツリーの深さに応じてトラバースします。
FIFO リストを使用して実装されます。	LIFOリストを使用して実装されます。
DFS と比較してより多くのメモリが必要です。	BFS と比較して必要なメモリが少なくなります。
このアルゴリズムは、最も浅いパスの解決策を提供します。	このアルゴリズムは、最も浅いパスの解決策を保証するものではありません。
BFS ではバックトラックする必要はありません。	DFS ではバックトラッキングが必要です。
有限ループに陥ることは決してありません。	無限ループに陥ってしまう可能性があります。
目標が見つからない場合は、解決策が見つかるまでに多くのノードを拡張する必要がある場合があります。	ゴールが見つからない場合、リーフノードのバックトラッキングが発生する可能性があります。

BFSの例

次の BFS の例では、6 つの頂点を持つグラフを使用しています。

BFSの例

ステップ1）

0 から 6 までの XNUMX つの数字のグラフがあります。

ステップ2）

0 またはゼロがルートノードとしてマークされています。

ステップ3）

0 が参照され、マークされ、キューデータ構造に挿入されます。

ステップ4）

残りの 0 個の隣接ノードと未訪問ノードが訪問され、マークされ、キューに挿入されます。

ステップ5）

すべてのノードが訪問されるまで、走査の反復が繰り返されます。

DFSの例

次の DFS の例では、5 つの頂点を持つ無向グラフを使用しています。

ステップ1）

我々は頂点0から始めました。アルゴリズムはまずそれを訪問リストに入れ、同時にその隣接する頂点をすべてデータ構造スタックと呼ばれます。

ステップ2）

スタックの最上位にある要素 (たとえば 1) にアクセスし、その隣接ノードに移動します。すでに 0 件が訪問されているためです。したがって、頂点 2 を訪問します。

ステップ3）

頂点 2 には、4 の近くに未訪問の頂点があります。したがって、それをスタックに追加して、そこにアクセスします。

ステップ4）

最後に、最後の頂点 3 を訪問します。これには、未訪問の隣接ノードがありません。 DFS アルゴリズムを使用したグラフの走査が完了しました。

BFSの応用例

BFS のアプリケーションは次のとおりです。

重み付けされていないグラフ

BFS アルゴリズムは、グラフのすべての頂点を可能な限り短時間かつ高精度で訪問するための最短パスと最小スパニングツリーを簡単に作成できます。

P2Pネットワーク

BFS を実装すると、ピアツーピアネットワーク内の最も近いノードまたは近隣ノードをすべて特定できます。これにより、必要なデータをより速く見つけることができます。

ウェブクローラー

検索エンジンまたは、Web クローラーは BFS を採用することで、複数レベルのインデックスを簡単に構築できます。 BFS の実装は、Web ページであるソースから開始され、次にそのソースからすべてのリンクにアクセスします。

ネットワーク放送

ブロードキャストされたパケットは、BFS アルゴリズムによってガイドされ、アドレスを持つすべてのノードを見つけて到達します。

DFSの応用例

DFS の重要なアプリケーションは次のとおりです。

加重グラフ

重み付きグラフでは、DFS グラフトラバーサルにより最短パスツリーと最小スパニングツリーが生成されます。

グラフ内のサイクルの検出

DFS 中にバックエッジが見つかった場合、グラフにはサイクルがあります。したがって、グラフに対して DFS を実行し、バックエッジを確認する必要があります。

パスファインディング

DFS アルゴリズムに特化して XNUMX つの頂点間のパスを検索できます。

トポロジカルソート

これは主に、ジョブのグループ間の特定の依存関係からジョブをスケジュールするために使用されます。コンピューターサイエンスでは、命令のスケジュール、データのシリアル化、ロジック合成、コンパイルタスクの順序の決定に使用されます。

グラフの強く連結したコンポーネントの検索

これは、グラフ内の各頂点から他の残りの頂点へのパスがある場合に、DFS グラフで使用されます。

たった XNUMX つの解決策でパズルを解く

DFS アルゴリズムは、訪問セット内の既存のパス上のノードを含めることで、迷路のすべての解決策を検索するように簡単に適応できます。

よろしければ：