幅優先検索 (BFS) アルゴリズムと例
サラ・チェン
BFS アルゴリズム (幅優先検索) とは何ですか?
幅優先探索 (BFS) は、データをグラフ化したり、ツリーを検索したり、構造をトラバースしたりするために使用されるアルゴリズムです。BFS の完全な形式は、幅優先探索です。
このアルゴリズムは、グラフ内のすべての主要なノードを正確に幅方向に効率的に訪問してマークします。このアルゴリズムは、グラフ内の単一のノード (初期またはソース ポイント) を選択し、選択したノードに隣接するすべてのノードを訪問します。BFS はこれらのノードに 1 つずつアクセスすることに注意してください。
アルゴリズムが開始ノードを訪問してマークすると、最も近い未訪問のノードに向かって移動し、それらを分析します。訪問すると、すべてのノードがマークされます。これらの反復は、グラフのすべてのノードが正常に訪問され、マークされるまで続行されます。
グラフトラバーサルとは何ですか?
グラフ トラバーサルは、グラフ内の頂点の位置を特定するために一般的に使用される方法論です。 これは、訪問した頂点のシーケンスをマークするとともに、グラフを高速かつ正確に分析できる高度な検索アルゴリズムです。 このプロセスにより、無限ループに陥ることなく、グラフ内の各ノードにすばやくアクセスできるようになります。
BFSアルゴリズムのアーキテクチャ
- データのさまざまなレベルで、任意のノードを開始ノードまたは最初のノードとしてマークして、トラバースを開始できます。 BFS はノードを訪問し、訪問済みとしてマークし、キューに入れます。
- BFSは最も近い未訪問のノードを訪問し、マークします。これらの値もキューに追加されます。キューは FIFOモデル.
- 同様に、グラフ上の残りの最も近い未訪問ノードが分析され、マークされてキューに追加されます。これらの項目は受信時にキューから削除され、結果として印刷されます。
なぜ BFS アルゴリズムが必要なのでしょうか?
データセットの検索に BFS アルゴリズムを使用する理由は数多くあります。このアルゴリズムを第一の選択肢にする最も重要な側面のいくつかは次のとおりです。
- BFS は、グラフ内のノードを分析し、これらを通過する最短パスを構築するのに役立ちます。
- BFS は、最小の反復回数でグラフを横断できます。
- BFS アルゴリズムのアーキテクチャはシンプルで堅牢です。
- BFS アルゴリズムの結果は、他のアルゴリズムと比較して高いレベルの精度を保持します。
- BFS の反復はシームレスであり、このアルゴリズムが無限ループの問題に巻き込まれる可能性はありません。
BFS アルゴリズムはどのように機能しますか?
グラフトラバーサルでは、アルゴリズムがツリー状構造内の未訪問のノードをすべて訪問、チェック、および/または更新する必要があります。 グラフの走査は、グラフ上のノードを訪問する順序によって分類されます。
BFS アルゴリズムは、グラフ内の最初のノードまたは開始ノードから操作を開始し、徹底的に走査します。最初のノードの走査に成功すると、グラフ内の次の走査されていない頂点にアクセスしてマークします。
したがって、最初の反復では、現在の頂点に隣接するすべてのノードが訪問され、トラバースされると言えます。BFS アルゴリズムの動作を実装するために、単純なキュー手法が利用されており、次のステップで構成されます。
ステップ1）
グラフ内の各頂点またはノードは既知です。 たとえば、ノードを V としてマークできます。
ステップ2）
頂点 V がアクセスされていない場合は、頂点 V を BFS キューに追加します。
ステップ3）
BFS 検索を開始し、完了後、頂点 V を訪問済みとしてマークします。
ステップ4）
BFS キューはまだ空ではないため、グラフの頂点 V をキューから削除します。
ステップ5）
頂点 V に隣接するグラフ上の残りの頂点をすべて取得します。
ステップ6）
隣接する各頂点について、V1 としましょう。まだ訪問されていない場合は、V1 を BFS キューに追加します。
ステップ7）
BFS は V1 を訪問し、訪問済みとしてマークし、キューから削除します。
BFS アルゴリズムの例
ステップ1）
0 から 6 までの XNUMX つの数字のグラフがあります。
ステップ2）
0 またはゼロがルート ノードとしてマークされています。
ステップ3）
0 が参照され、マークされ、キュー データ構造に挿入されます。
ステップ4）
残りの 0 個の隣接ノードと未訪問ノードが訪問され、マークされ、キューに挿入されます。
ステップ5）
すべてのノードが訪問されるまで、走査の反復が繰り返されます。
BFS アルゴリズムのルール
BFS アルゴリズムを使用するための重要なルールを次に示します。
- キュー (FIFO-先入れ先出し) データ構造 BFS によって使用されます。
- グラフ内の任意のノードをルートとしてマークし、そこからデータの走査を開始します。
- BFS はグラフ内のすべてのノードを走査し、完了するとノードを削除し続けます。
- BFS は、隣接する未訪問のノードを訪問し、それを完了としてマークし、キューに挿入します。
- 隣接する頂点が見つからない場合は、前の頂点をキューから削除します。
- BFS アルゴリズムは、グラフ内のすべての頂点が正常に走査され、完了としてマークされるまで反復されます。
- どのノードからのデータの移動中にも、BFS によって発生するループは発生しません。
BFS アルゴリズムの応用
BFS アルゴリズムの実装が非常に効果的である実際のアプリケーションをいくつか見てみましょう。
- 重み付けされていないグラフ: BFS アルゴリズムは、グラフのすべての頂点を可能な限り短時間かつ高精度で訪問するための最短パスと最小スパニング ツリーを簡単に作成できます。
- P2P ネットワーク: BFS を実装すると、ピアツーピア ネットワーク内の最も近いノードまたは近隣ノードをすべて特定できます。これにより、必要なデータをより速く見つけることができます。
- ウェブ クローラー: 検索エンジンまたは Web クローラーは、BFS を採用することで複数レベルのインデックスを簡単に構築できます。 BFS の実装は、Web ページであるソースから開始され、次にそのソースからすべてのリンクにアクセスします。
- ナビゲーション システム: BFS は、メインまたはソースの場所からすべての近隣の場所を検索するのに役立ちます。
- ネットワークブロードキャスト: ブロードキャストされたパケットは、BFS アルゴリズムによってガイドされ、アドレスを持つすべてのノードを見つけて到達します。
製品概要
- グラフ トラバーサルは、アルゴリズムがツリー状構造内の未訪問のすべてのノードを訪問、チェック、および/または更新することを必要とする独自のプロセスです。 BFS アルゴリズムは同様の原理で動作します。
- このアルゴリズムは、グラフ内のノードを分析し、これらを通過する最短パスを構築するのに役立ちます。
- このアルゴリズムは、最小の反復回数と可能な限り短い時間でグラフを走査します。
- BFS は、グラフ内の単一のノード (初期点またはソース点) を選択し、選択したノードに隣接するすべてのノードを訪問します。 BFS はこれらのノードに XNUMX つずつアクセスします。
- 訪問されマークされたデータは、BFS によってキューに入れられます。 キューは先入れ先出し方式で機能します。 したがって、グラフに最初に配置された要素が最初に削除され、結果として出力されます。
- BFS アルゴリズムは無限ループに陥ることはありません。
- BFS は高精度で堅牢な実装により、P2P ネットワーク、Web クローラー、ネットワーク ブロードキャストなどの複数の現実のソリューションで使用されています。
