BFS（幅優先探索）とは：基本概念・擬似コード・実装例と応用・最適化ガイド
エバープレイ編集部BFS とは — 基本概念
BFS（Breadth-First Search、幅優先探索）は、グラフや木構造を探索する基本的なアルゴリズムの一つです。ルート（または任意の始点）から近い頂点を優先して探索し、「距離（辺の数）」が小さい頂点から順に訪問を行います。主にキュー（FIFO）を用いて実装され、最短経路（重みがすべて等しい場合）や連結成分の判定、レベル分け（層別探索）といった問題に適しています。
アルゴリズムの流れ（直感）
- 始点を訪問済みにしてキューに入れる。
- キューから頂点を1つ取り出し、その隣接頂点を順に調べる。
- 隣接頂点が未訪問なら訪問済みにしてキューに追加する。
- キューが空になるまでこれを繰り返す。
この方法により、始点からの距離が小さい順に頂点を取り出すことが保証されます（無向・有向ともに有効）。
擬似コード
function BFS(start):
queue = new Queue()
visited[start] = true
distance[start] = 0
queue.enqueue(start)
while not queue.empty():
v = queue.dequeue()
for each neighbor u of v:
if not visited[u]:
visited[u] = true
distance[u] = distance[v] + 1
parent[u] = v // 経路復元が必要なら
queue.enqueue(u)計算量（時間・空間）
- 時間計算量（隣接リストの場合）: O(V + E)。各頂点は一度だけキューに入るため O(V)、各辺は隣接リストを通じて一度だけ調べられるため O(E)。
- 時間計算量（隣接行列の場合）: O(V^2)。各頂点で行列の行を走査するため。
- 空間計算量: O(V)。訪問フラグや距離配列、キューが最大で頂点数に比例したサイズを取る。
主な性質と正当性
- 最短経路性: グラフの辺に重みがなく（または等しい重み）距離が辺の数で測られる場合、始点から各頂点への最短経路（辺数が最小）を見つける。
- レベル分け: BFSは各頂点に「レベル（始点からの距離）」を割り当てるため、層別処理が簡単にできる。
- 循環や無限グラフ: 有向無向にかかわらず、訪問した頂点を記録しないと無限ループに陥る可能性がある（特に無向グラフや自己ループがある場合）。
実用的な応用例
- 最短経路（重みが等しい場合）: マップ上の格子移動や単純なネットワークでの最短ホップ数。
- 連結成分の検出: 無向グラフの各連結成分の頂点集合を求める際に利用。
- 木のレベル順走査: 二分木のレベルオーダー（幅優先）走査。
- 最小ステップ問題: パズル（例: スライディングパズル）や最短手数問題で状態空間を幅優先に探索して解を得る。
- 二部グラフ判定: BFSのレベルを利用して二部分割が可能かをチェックする。
- Webクローリングやソーシャルネットワーク分析: 近傍を順に拡張して探索する場面。
実行例（簡単なグラフ）
例: 頂点 {A, B, C, D, E}、辺 {A-B, A-C, B-D, C-D, D-E} を始点 A から探索する。
- 初期: queue = [A], visited = {A}
- A を取り出す → 隣接 B, C を発見: queue = [B, C], visited = {A,B,C}, distance(B)=1, distance(C)=1
- B を取り出す → 隣接 D を発見: queue = [C, D], visited = {A,B,C,D}, distance(D)=2, parent(D)=B
- C を取り出す → 隣接 D（既訪問）を無視
- D を取り出す → 隣接 E を発見: queue = [E], visited = {A,B,C,D,E}, distance(E)=3
- E を取り出す → 隣接なし（終了）
派生・発展（バリエーションと最適化）
- 多始点（multi-source）BFS: 複数の始点を同時にキューへ入れて広げることで、各頂点への最短距離を各始点からの最短距離として同時に求められる（例: 複数の火元からの到達時間計算）。
- 双方向 BFS（bidirectional BFS）: 始点側と目標側から同時に探索して中央で出会わせることで探索量を大幅に削減できる（最短経路の検索に効果的）。
- 0-1 BFS: 辺の重みが0か1の場合に deque を用いて O(V+E) で最短距離を得るテクニック。
- 外部メモリや並列化: 非常に大きなグラフではメモリとI/Oの工夫や並列BFSが必要。レベル同期型の並列BFSや分散グラフ処理フレームワーク（GraphX, Pregel系）を利用する。
実装上の注意点・落とし穴
- 訪問フラグの管理: 頂点をキューに追加する時点で訪問済みにする（enqueue 時に visited=true）と二重追加を防げる。
- メモリ消費: 幅優先は最悪で一つのレベルに多くの頂点が集中するとキューが大きくなる。グラフ密度や最大幅を考慮する。
- 有向グラフの一方向性: 辺の向きに注意。無向グラフのコードを有向グラフにそのまま使うと誤った探索になる。
- 重み付きグラフ: 一般的な重み付きグラフの最短経路問題には BFS は適さない（Dijkstra や Bellman-Ford を用いる）。ただし重みが同じか 0/1 の特殊ケースは上述の通り例外。
よくある質問（FAQ）
- Q: DFS と BFS はどちらが良い？
A: 問題に依存する。局所解を深く掘るのが DFS、最短距離や層別情報が必要なら BFS。メモリと探索順も選択基準。 - Q: BFS は全ノードを訪れないと正確な最短経路が分からない？
A: 単一始点・単一終点の最短経路を見つけるときは、双方向 BFS や探索途中で目標に到達した時点で停止することができる（到達時点で最短であることが保証される）。
まとめ
BFS はシンプルで強力なグラフ探索アルゴリズムです。キューを用いて層ごとに探索を進めることで、無重みグラフにおける最短経路の発見や連結性、レベル分けといった多彩な用途に応用できます。実装は単純ながら、メモリ消費やグラフの特性に合わせた変種（双方向、0-1、並列化など）を選ぶことで、実用上の性能を大幅に向上させることが可能です。
参考文献
- Wikipedia（日本語）: 幅優先探索
- Wikipedia（英語）: Breadth-first search
- CP-Algorithms: Breadth-First Search (BFS)
- GeeksforGeeks: Breadth First Search (BFS) for a Graph
- MIT OpenCourseWare: Lecture — Graph search: Breadth-First Search
投稿者プロフィール
