BFSとは何ですか?
幅優先検索 (BFS) は、ルート ノードから開始して各ノードの隣接ノードをトラバーサル キューに追加することによるノードのトラバースに基づいています。グラフの BFS は、グラフにサイクルがあることを除いて、ツリーの BFS と似ています。深さ優先検索とは対照的に、次のレベルに進む前に、特定の深さにあるすべての隣接ノードが調査されます。
BFS アルゴリズム
幅優先検索を使用してグラフを探索する場合の手順は次のとおりです。
- グラフの隣接行列または隣接リストのデータを取得します。
- キューを作成し、アイテムを入れます。
- ルート ノードをアクティブ化します (キューの先頭でルート ノードを取得することを意味します)。
- キューの先頭 (または最初の要素) をデキューし、キューの近くにあるすべてのノードを左から右にエンキューします。ノードの近くに調査する必要のあるノードがない場合は、単純にヘッドをデキューして操作を再開します。 (注: 以前に調査された、またはキュー内にあるネイバーが出現した場合は、それをキューに入れず、スキップしてください。)
- キューが空になるまでこの方法を続けます。
BFS アプリケーション
アルゴリズムの柔軟性により、幅優先検索は現実の世界では非常に役立ちます。その一部を次に示します。
- ピアツーピア ネットワークでは、ピアノードが検出されます。 BitTorrent、uTorrent、qBittorent などのほとんどの torrent クライアントは、このプロセスを使用してネットワーク内の「シード」と「ピア」を見つけます。
- インデックスは、Web クローリングのグラフ トラバーサル技術を使用して構築されます。この手順は、ルート ノードとしてのソース ページから始まり、ソース ページにリンクされているすべての 2 次ページまで進みます (このプロセスは継続します)。再帰ツリーの深さが減少するため、ここでは幅優先検索に固有の利点があります。
- GPS ナビゲーション システムの使用では、GPS を使用して幅優先検索を実行し、近くの場所を見つけます。
- 幅優先検索の概念を採用したチェイニーの手法は、ガベージの収集に使用されます。
BFS トラバーサルの例
まず、簡単な例を見てみましょう。ルート ノードとして 0 から始めて、グラフを下に向かって進めていきます。
ステップ1： エンキュー(0)
列
| 0 |
ステップ2： デキュー(0)、エンキュー(1)、エンキュー(3)、エンキュー(4)
列
| 1 | 3 | 4 |
ステップ 3: デキュー(1)、エンキュー(2)
列
| 3 | 4 | 2 |
ステップ 4: デキュー(3)、エンキュー(5)。 0 はすでに探索されているため、キューに 1 を再度追加しません。
ダーツリスト
列
| 4 | 2 | 5 |
ステップ5: デキュー(4)
列
| 2 | 5 |
ステップ6: デキュー(2)
列
オペレーティングシステムの使用
| 5 |
ステップ 7: デキュー(5)
列
キューは空になったので、プロセスを停止します。
幅優先検索 Java プログラム
コードを処理するにはいくつかのアプローチがあります。ここでは主に、Java での幅優先検索の実装に関連する手順について説明します。隣接リストまたは隣接行列を使用してグラフを保存できます。どちらの方法でも構いません。隣接リストは、コード内でグラフを表すために使用されます。 Java で幅優先検索アルゴリズムを実装する場合、ノードがノードの先頭 (または先頭) からデキューされたら、各ノードに接続されているノードのリストを移動するだけで済むため、隣接リストの処理がはるかに簡単になります。列。
コードを示すために使用されるグラフは、前の例で使用されたものと同じです。
BFSTraversal.java
import java.io.*; import java.util.*; public class BFSTraversal { private int node; /* total number number of nodes in the graph */ private LinkedList adj[]; /* adjacency list */ private Queue que; /* maintaining a queue */ BFSTraversal(int v) { node = v; adj = new LinkedList[node]; for (int i=0; i<v; i++) { adj[i]="new" linkedlist(); } que="new" void insertedge(int v,int w) adj[v].add(w); * adding an edge to the adjacency list (edges are bidirectional in this example) bfs(int n) boolean nodes[]="new" boolean[node]; initialize array for holding data int a="0;" nodes[n]="true;" que.add(n); root node is added top of queue while (que.size() !="0)" n="que.poll();" remove element system.out.print(n+' '); print (int i="0;" < adj[n].size(); iterate through linked and push all neighbors into if (!nodes[a]) only insert nodes they have not been explored already nodes[a]="true;" que.add(a); public static main(string args[]) bfstraversal graph="new" bfstraversal(6); graph.insertedge(0, 1); 3); 4); graph.insertedge(4, 5); graph.insertedge(3, graph.insertedge(1, 2); 0); graph.insertedge(2, graph.insertedge(5, system.out.println('breadth first traversal is:'); graph.bfs(0); pre> <p> <strong>Output:</strong> </p> <pre> Breadth First Traversal for the graph is: 0 1 3 4 2 5 </pre> <hr></v;>