幅優先検索 (BFS) 基本的なものです グラフ走査アルゴリズム 。これには、グラフの接続されているすべてのノードをレベルごとに訪問することが含まれます。この記事では、 BFS そしてそれをグラフに効果的に適用する方法
目次
- グラフの幅優先検索または BFS
- グラフ用BFSとツリー用BFSの関係
- グラフ アルゴリズムの幅優先検索 (BFS)
- BFS アルゴリズムはどのように機能しますか?
- 隣接リストを使用したグラフ用の BFS の実装
- 幅優先検索 (BFS) アルゴリズムの複雑さ
- グラフにおける BFS の応用
- グラフの幅優先検索または BFS に関する問題
- グラフの幅優先検索 (BFS) に関する FAQ
グラフの幅優先検索 (BFS):
幅優先検索 (BFS) は、次の深さレベルの頂点に進む前に、現在の深さでグラフ内のすべての頂点を探索するグラフ トラバーサル アルゴリズムです。指定された頂点から開始し、次のレベルの近傍に進む前に、すべての近傍を訪問します。 BFS は、経路探索、接続コンポーネント、およびグラフの最短経路問題のアルゴリズムで一般的に使用されます。
グラフの BFS とツリーの BFS の関係:
グラフの幅優先トラバーサル (BFS) は、 ツリーの幅優先トラバース 。
ここでの唯一の落とし穴は、それとは異なります。 木 、 グラフ サイクルが含まれる可能性があるため、同じノードに再び到達する可能性があります。ノードを複数回処理することを避けるために、頂点を 2 つのカテゴリに分けます。
- 訪問して、
- 未訪問。
ブール値の訪問済み配列を使用して、訪問済みの頂点をマークします。簡単にするために、すべての頂点が開始頂点から到達可能であると仮定します。 BFS 用途 ある グラフ アルゴリズムの幅優先検索 (BFS):
BFS のアルゴリズムについて説明します。
BFのための何か
- 初期化: 開始ノードをキューに入れ、訪問済みとしてマークします。
- 探検: キューが空ではない場合:
- キューからノードをデキューし、そのノードにアクセスします (たとえば、その値を出力します)。
- デキューされたノードの未訪問の近隣ノードごとに、次のようになります。
- ネイバーをキューに入れます。
- 隣人を訪問者としてマークします。
- 終了： キューが空になるまでステップ 2 を繰り返します。
このアルゴリズムにより、グラフ内のすべてのノードが開始ノードから開始して幅優先方式でアクセスされることが保証されます。
BFS アルゴリズムはどのように機能しますか?
ルートから開始して、最初に特定のレベルのすべてのノードを訪問し、次にすべてのノードが訪問されるまで次のレベルのノードをたどります。
これを行うには、キューが使用されます。現在のレベルのすべての隣接する未訪問ノードがキューにプッシュされ、現在のレベルのノードは訪問済みとしてマークされ、キューからポップされます。
図：
次の例を使用して、アルゴリズムの動作を理解しましょう。
ステップ1： 最初はキューと訪問された配列は空です。
キューおよび訪問された配列は、最初は空です。
ステップ2： ノード 0 をキューにプッシュし、訪問済みとしてマークします。
ノード 0 をキューにプッシュし、訪問済みとしてマークします。
ステップ 3: キューの先頭からノード 0 を削除し、未訪問の近隣ノードを訪問してキューにプッシュします。
メソッドの部分文字列 Javaキューの先頭からノード 0 を削除し、未訪問の近隣ノードを訪問してキューにプッシュします。
ステップ 4: ノード 1 をキューの先頭から削除し、未訪問の近隣ノードを訪問してキューにプッシュします。
キューの先頭からノード 1 を削除し、未訪問の近隣ノードを訪問してプッシュします。
ステップ5: キューの先頭からノード 2 を削除し、未訪問の近隣ノードを訪問してキューにプッシュします。
カット・ティンプの純資産キューの先頭からノード 2 を削除し、未訪問の近隣ノードを訪問してキューにプッシュします。
ステップ6: キューの先頭からノード 3 を削除し、未訪問の近隣ノードを訪問してキューにプッシュします。
ノード 3 のすべての隣接ノードが訪問されていることがわかるため、キューの前にある次のノードに移動します。ノード 3 をキューの先頭から削除し、未訪問の近隣ノードを訪問してキューにプッシュします。
ステップ 7: キューの先頭からノード 4 を削除し、未訪問の近隣ノードを訪問してキューにプッシュします。
ノード 4 のすべての隣接ノードが訪問されていることがわかるため、キューの前にある次のノードに移動します。キューの先頭からノード 4 を削除し、未訪問の近隣ノードを訪問してキューにプッシュします。
Queue が空になったので、これらの繰り返しプロセスを終了します。
隣接リストを使用したグラフ用の BFS の実装:
C++ #include #include #include using namespace std; // Function to perform Breadth First Search on a graph // represented using adjacency list void bfs(vector>& adjList、int startNode、ベクトル & 訪問済み) { // BFS キューのキューを作成します q; // 現在のノードを訪問済みとしてマークし、訪問済みとしてキューに入れます[startNode] = true; q.push(startNode); // キューを反復処理します while (!q.empty()) { // キューから頂点をデキューして出力します int currentNode = q.front(); q.pop(); コート<< currentNode << ' '; // Get all adjacent vertices of the dequeued vertex // currentNode If an adjacent has not been visited, // then mark it visited and enqueue it for (int neighbor : adjList[currentNode]) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } } // Function to add an edge to the graph void addEdge(vector>& adjList, int u, int v) { adjList[u].push_back(v); } int main() { // グラフ内の頂点の数 int vertices = 5; // グラフベクトルの隣接リスト表現> adjList(頂点); // グラフにエッジを追加します addEdge(adjList, 0, 1); addEdge(adjList, 0, 2); addEdge(adjList, 1, 3); addEdge(adjList, 1, 4); addEdge(adjList, 2, 4); // すべての頂点を未訪問ベクトルとしてマークします 訪問済み(頂点、false); // 頂点 0 cout から開始して BFS トラバーサルを実行します<< 'Breadth First Traversal starting from vertex ' '0: '; bfs(adjList, 0, visited); return 0; }>
C #include #include #define MAX_VERTICES 100 // Structure to represent a node in adjacency list struct Node { int data; struct Node* next; }; // Function to create a new node struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->データ = データ; newNode->next = NULL; 新しいノードを返します。 } // グラフにエッジを追加する関数 void addEdge(struct Node* adjList[], int u, int v) { struct Node* newNode = createNode(v); newNode->next = adjList[u]; adjList[u] = 新しいノード; } // グラフ上で幅優先検索を実行する関数 // 隣接リストを使用して表現 void bfs(struct Node* adjList[], int vertices, int startNode, int Visited[]) { // BFS のキューを作成 int queue[ MAX_VERTICES]; int フロント = 0、リア = 0; // 現在のノードを訪問済みとしてマークし、それをキューに追加します。[startNode] = 1; キュー[リア++] = startNode; // キューを反復処理します while (front != Rear) { // 頂点をキューからデキューして出力します int currentNode = queue[front++]; printf('%d ', currentNode); // デキューされた頂点のすべての隣接する頂点を取得します。 // currentNode 隣接する頂点が訪問されていない場合、 // 訪問済みのマークを付けてキューに入れます。 struct Node* temp = adjList[currentNode]; while (temp != NULL) { int neighbors = temp->data; if (!visited[隣人]) {訪問者[隣人] = 1; キュー[リア++] = ネイバー; temp = temp->next; } } } int main() { // グラフ内の頂点の数 int vertices = 5; // グラフの隣接リスト表現 struct Node* adjList[vertices]; for (int i = 0; i< vertices; ++i) adjList[i] = NULL; // Add edges to the graph addEdge(adjList, 0, 1); addEdge(adjList, 0, 2); addEdge(adjList, 1, 3); addEdge(adjList, 1, 4); addEdge(adjList, 2, 4); // Mark all the vertices as not visited int visited[vertices]; for (int i = 0; i < vertices; ++i) visited[i] = 0; // Perform BFS traversal starting from vertex 0 printf( 'Breadth First Traversal starting from vertex 0: '); bfs(adjList, vertices, 0, visited); return 0; }> ジャワ import java.util.LinkedList; import java.util.Queue; // Class to represent a graph using adjacency list class Graph { int vertices; LinkedList [] adjList; @SuppressWarnings('unchecked') Graph(int vertices) { this.vertices = vertices; adjList = 新しい LinkedList[頂点]; for (int i = 0; i< vertices; ++i) adjList[i] = new LinkedList(); } // Function to add an edge to the graph void addEdge(int u, int v) { adjList[u].add(v); } // Function to perform Breadth First Search on a graph // represented using adjacency list void bfs(int startNode) { // Create a queue for BFS Queue キュー = 新しい LinkedList(); boolean[] 訪問 = 新しい boolean[頂点]; // 現在のノードを訪問済みとしてマークし、訪問済みとしてキューに入れます[startNode] = true; queue.add(startNode); // キューを反復処理します while (!queue.isEmpty()) { // キューから頂点をデキューして出力します int currentNode = queue.poll(); System.out.print(currentNode + ' '); // デキューされた頂点 currentNode のすべての隣接する頂点を取得します。 // 隣接する頂点が訪問されていない場合、 // 訪問済みとしてマークし、 // エンキューします (int neighbors : adjList[currentNode]) { if (!visited[neighbor] ) { 訪問者[隣人] = true; queue.add(ネイバー); } } } } } public class Main { public static void main(String[] args) { // グラフ内の頂点の数 int vertices = 5; // グラフを作成します Graph chart = new Graph(vertices); // グラフにエッジを追加します。graph.addEdge(0, 1); グラフ.addEdge(0, 2); グラフ.addEdge(1, 3); グラフ.addEdge(1, 4); グラフ.addEdge(2, 4); // 頂点 0 から開始する BFS トラバーサルを実行します。 System.out.print( '頂点 0 から開始する幅優先トラバーサル: '); グラフ.bfs(0); } }>> Python3 from collections import deque # Function to perform Breadth First Search on a graph # represented using adjacency list def bfs(adjList, startNode, visited): # Create a queue for BFS q = deque() # Mark the current node as visited and enqueue it visited[startNode] = True q.append(startNode) # Iterate over the queue while q: # Dequeue a vertex from queue and print it currentNode = q.popleft() print(currentNode, end=' ') # Get all adjacent vertices of the dequeued vertex # If an adjacent has not been visited, then mark it visited and enqueue it for neighbor in adjList[currentNode]: if not visited[neighbor]: visited[neighbor] = True q.append(neighbor) # Function to add an edge to the graph def addEdge(adjList, u, v): adjList[u].append(v) def main(): # Number of vertices in the graph vertices = 5 # Adjacency list representation of the graph adjList = [[] for _ in range(vertices)] # Add edges to the graph addEdge(adjList, 0, 1) addEdge(adjList, 0, 2) addEdge(adjList, 1, 3) addEdge(adjList, 1, 4) addEdge(adjList, 2, 4) # Mark all the vertices as not visited visited = [False] * vertices # Perform BFS traversal starting from vertex 0 print('Breadth First Traversal starting from vertex 0:', end=' ') bfs(adjList, 0, visited) if __name__ == '__main__': main()> C# using System; using System.Collections.Generic; // Class to represent a graph using adjacency list class Graph { int vertices; List [] adjList; public Graph(int vertices) { this.vertices = 頂点; adjList = 新しいリスト [ 頂点 ]; for (int i = 0; i< vertices; ++i) adjList[i] = new List (); } // グラフにエッジを追加する関数 public void AddEdge(int u, int v) { adjList[u].Add(v); } // グラフ上で幅優先検索を実行する関数 // 隣接リストを使用して表現 public void BFS(int startNode) { // BFS Queue のキューを作成 キュー = 新しいキュー (); bool[] 訪問 = 新しい bool[頂点]; // 現在のノードを訪問済みとしてマークし、訪問済みとしてキューに入れます[startNode] = true; queue.Enqueue(startNode); // キューを反復処理します while (queue.Count != 0) { // キューから頂点をデキューして出力します int currentNode = queue.Dequeue(); Console.Write(currentNode + ' '); // デキューされた頂点 currentNode のすべての隣接する頂点を取得します。 // 隣接する頂点が訪問されていない場合、 // 訪問済みとしてマークし、 // キューに入れます。 foreach(int neighbors in adjList[currentNode]) { if (!visited[neighbor] ) { 訪問者[隣人] = true; queue.Enqueue(ネイバー); } } } } } class MainClass { public static void Main(string[] args) { // グラフ内の頂点の数 int vertices = 5; // グラフを作成します Graph chart = new Graph(vertices); // グラフにエッジを追加します。graph.AddEdge(0, 1); グラフ.AddEdge(0, 2); グラフ.AddEdge(1, 3); グラフ.AddEdge(1, 4); グラフ.AddEdge(2, 4); // 頂点 0 から開始する BFS トラバーサルを実行します Console.Write( '頂点 0 から開始する幅優先トラバーサル: '); グラフ.BFS(0); } }>> JavaScript // Class to represent a graph using adjacency list class Graph { constructor() { this.adjList = {}; } // Function to add an edge to the graph addEdge(u, v) { if (!this.adjList[u]) this.adjList[u] = []; this.adjList[u].push(v); } // Function to perform Breadth First Search on a graph represented using adjacency list bfs(startNode) { // Create a queue for BFS const queue = []; const visited = new Array(Object.keys(this.adjList).length).fill(false); // Mark the current node as visited and enqueue it visited[startNode] = true; queue.push(startNode); // Iterate over the queue while (queue.length !== 0) { // Dequeue a vertex from queue and print it const currentNode = queue.shift(); console.log(currentNode + ' '); // Get all adjacent vertices of the dequeued vertex currentNode // If an adjacent has not been visited, then mark it visited and enqueue it for (const neighbor of this.adjList[currentNode] || []) { if (!visited[neighbor]) { visited[neighbor] = true; queue.push(neighbor); } } } } } // Create a graph const graph = new Graph(); // Add edges to the graph graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(1, 3); graph.addEdge(1, 4); graph.addEdge(2, 4); // Perform BFS traversal starting from vertex 0 console.log('Breadth First Traversal starting from vertex 0: '); graph.bfs(0);> 出力
Breadth First Traversal starting from vertex 0: 0 1 2 3 4>
時間計算量: O(V+E)。ここで、V はノードの数、E はエッジの数です。
補助スペース: O(V)
幅優先検索 (BFS) アルゴリズムの複雑さの分析:
BFS アルゴリズムの時間計算量: O(V + E)
- BFS は、グラフ内のすべての頂点とエッジを調査します。最悪の場合、すべての頂点とエッジを 1 回訪問します。したがって、BFS の時間計算量は O(V + E) です。ここで、V と E は、指定されたグラフ内の頂点とエッジの数です。
BFS アルゴリズムの空間複雑度: O(V)
- BFS はキューを使用して、アクセスする必要がある頂点を追跡します。最悪の場合、キューにはグラフ内のすべての頂点が含まれる可能性があります。したがって、BFS の空間複雑度は O(V) です。ここで、V と E は、指定されたグラフ内の頂点とエッジの数です。
グラフにおける BFS のアプリケーション:
BFS は、グラフ理論とコンピューター サイエンスにおいて次のようなさまざまな用途に使用できます。
- 最短パスの検索: BFS を使用すると、重み付けされていないグラフ内の 2 つのノード間の最短パスを見つけることができます。走査中に各ノードの親を追跡することにより、最短パスを再構築できます。
- サイクル検出: BFS を使用して、グラフ内のサイクルを検出できます。走査中にノードが 2 回訪問された場合は、サイクルが存在することを示します。
- 接続されたコンポーネント: BFS を使用すると、グラフ内の接続されたコンポーネントを識別できます。各接続コンポーネントは、相互に到達できるノードのセットです。
- トポロジカルソート: BFS を使用すると、有向非巡回グラフ (DAG) でトポロジカル ソートを実行できます。トポロジカル ソートでは、どのエッジ (u, v) についても、順序内で u が v の前に現れるように、ノードが線形順序で配置されます。
- 二分木のレベル順序走査: BFS を使用すると、バイナリ ツリーのレベル順序のトラバーサルを実行できます。この走査では、次のレベルに移動する前に、同じレベルにあるすべてのノードを訪問します。
- ネットワークルーティング: BFS を使用すると、ネットワーク内の 2 つのノード間の最短パスを見つけることができるため、ネットワーク プロトコルでのデータ パケットのルーティングに役立ちます。
グラフの幅優先検索または BFS に関する問題:
| はい・いいえ | 問題点 | 練習する |
|---|---|---|
| 1. | 無向グラフ内の特定のノードのレベルを見つける | リンク |
| 2. | 左上から右下までのパス内の隣接する最大の差を最小限に抑える | リンク |
| 10. | 指定された行列の宛先がセルの必要な値で到達可能かどうかを確認する | リンク |
グラフの幅優先検索 (BFS) に関する FAQ:
質問1： BFS とは何ですか?またどのように機能しますか?
答え： BFS は、次のレベルに進む前に、特定のレベルのすべての頂点を訪問することでグラフを体系的に探索するグラフ トラバーサル アルゴリズムです。開始頂点から開始し、それをキューに入れ、訪問済みとしてマークします。次に、キューから頂点をデキューし、その頂点にアクセスし、未訪問の隣接頂点をすべてキューにエンキューします。このプロセスは、キューが空になるまで続行されます。
質問2： BFS の用途は何ですか?
答え： BFS には、重み付けされていないグラフ内の最短パスの検索、グラフ内のサイクルの検出、有向非巡回グラフ (DAG) のトポロジカルなソート、グラフ内の連結成分の検索、迷路や数独などのパズルの解決など、さまざまな用途があります。
質問 3: BFS の時間計算量はどれくらいですか?
答え： BFS の時間計算量は O(V + E) です。ここで、V はグラフ内の頂点の数、E はエッジの数です。
質問4: BFS の空間の複雑さはどのくらいですか?
答え： BFS の空間複雑さは、キューを使用して訪問する必要のある頂点を追跡するため、O(V) です。
質問5: BFS を使用する利点は何ですか?
答え： BFS は実装が簡単で、重み付けされていないグラフで最短パスを見つけるのに効率的です。また、グラフ内のすべての頂点が訪問されることも保証されます。
関連記事：
配列cの文字列
- BFS に関する最近の記事
- 深さ優先トラバーサル
- 幅優先トラバーサルの応用
- 深さ優先検索の応用
- 幅優先検索 (BFS) の時間と空間の複雑さ