BFS（幅優先探索）の仕組みを解説

幅優先探索（BFS）

幅優先探索は、最も基本的なグラフ探索アルゴリズムの一つです。開始ノードのすべての隣接ノードを訪問してから次のレベルの隣接ノードに移動し、ソースから外側に「波紋」のように広がります。

BFSの動作原理

1. 初期化 — 開始ノードをキューに入れ、訪問済みとしてマークします。
2. デキュー — キューの先頭のノードを取り出します。これが現在のノードです。
3. 隣接ノードの探索 — 現在のノードの未訪問の隣接ノードそれぞれを訪問済みとしてマークし、キューに追加します。
4. 繰り返し — キューが空になるまで続けます。

Queue: [A]           → Aを訪問、B, Cをキューに追加
Queue: [B, C]        → Bを訪問、Dをキューに追加
Queue: [C, D]        → Cを訪問、Eをキューに追加
Queue: [D, E]        → Dを訪問
Queue: [E]           → Eを訪問
Queue: []            → 完了

時間・空間計算量

• 時間: O(V + E)（Vは頂点数、Eは辺数）
• 空間: O(V)（訪問済みセットとキュー用）

主な特性

BFSは重みなしグラフで最短経路を保証します。ソースからの距離順にノードを探索するため、距離dのすべてのノードが距離d+1のノードより先に訪問されます。

BFS vs DFS

BFSがキュー（FIFO）を使用するのに対し、DFSはスタック（LIFOまたは再帰）を使用します。BFSは重みなしグラフで最短経路を見つけます。DFSはサイクル検出やトポロジカルソートに適しています。