BFSとは？
BFS（Breadth-First Search、幅優先探索）は、グラフやツリーで近いノードから順番に探索するアルゴリズムです。開始ノードから一段階ずつ遠ざかりながら、すべてのノードを訪問します。
水に石を投げた時に波紋が同心円状に広がるように、BFSは開始点から距離1のノード→距離2のノード→距離3のノードの順で探索します。
なぜ重要か？
BFSはグラフアルゴリズムの基本であり、コーディングテストで非常に頻繁に出題されます。
- •最短経路保証: 重みなしグラフで最短経路を見つけられる
- •レベル別探索: ツリーのレベル順巡回、ネットワーク階層探索に活用
- •コーディングテスト必須: 迷路探索、トマト問題、最小移動回数など代表問題多数
動作原理
BFSはキュー（Queue）データ構造を使用します。
ステップ1. 開始ノードをキューに入れ、訪問済みとマークします。
ステップ2. キューからノードを一つ取り出します。
ステップ3. 取り出したノードの隣接ノードのうち、未訪問のものをすべてキューに入れ、訪問済みとマークします。
ステップ4. キューが空になるまでステップ2〜3を繰り返します。
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 時間 | O(V + E) |
| 空間 | O(V) |
Vは頂点数、Eは辺数です。すべてのノードを1回ずつ訪問し、すべての辺を1回ずつ確認するためO(V + E)です。
BFS vs DFS の違い
| 比較 | BFS | DFS |
|---|---|---|
| データ構造 | キュー（Queue） | スタック / 再帰 |
| 探索順序 | 近いノード優先 | 深いノード優先 |
| 最短経路 | 保証（重みなしグラフ） | 保証しない |
| メモリ | 幅広いグラフで多く使用 | 深いグラフで多く使用 |
| 主な活用 | 最短距離、レベル順巡回 | 経路探索、サイクル検出 |
最短経路が必要ならBFS、すべての経路を探索する必要があるならDFSを選びます。
代表的な活用問題
迷路探索 — 出発点から到着点までの最小移動回数を求める問題。BFSで解くと、最初に到着点に達した瞬間が最短経路です。
マルチソースBFS — 複数の開始点から同時にBFSを実行します。キューにすべての開始点を先に入れてから処理を開始します。
ネットワーク接続確認 — 2つのノードが同じネットワークに属するかを判定します。
よくあるミス
- •訪問チェックをキュー投入時ではなく取り出し時に行うと、同じノードが複数回キューに入る
- •2次元配列問題で範囲チェックを漏らし、インデックス超過エラー
- •マルチソースBFSで開始点を一つしか入れない間違い
AlgoNoteで直接確認しましょう
BFSがグラフでどのように波紋のように広がっていくか、AlgoNoteで一段階ずつ視覚的に確認できます。ノードと辺を自分で構成し、探索過程を観察してみてください。