BFS（幅優先探索）入門：最短経路・連結成分・二部グラフ判定まで網羅する実践ガイド
エバープレイ編集部BFSアルゴリズム とは
BFS（Breadth-First Search、幅優先探索）は、グラフや木を探索する基本アルゴリズムの一つで、ある始点（根）から同じ距離（辺の本数）にある頂点を順に訪問していく手法です。主に「最小辺数の経路（非負重・単位重みのグラフ）」を求める際に用いられ、キュー（FIFO）を用いることで探索順序を管理します。BFSは探索の単純さと計算量の良さから、さまざまな実世界の問題やアルゴリズムの基礎処理として広く使われています。
基本的な動作と直感
BFSは始点からスタートし、まず始点自身を訪問し、その次に始点に隣接する全頂点（距離1）を訪問、その次に距離2の頂点を訪問する、というように「距離（レベル）ごと」に広がっていきます。これを実現するためにキューを使い、発見した順に頂点をキューに入れ、先に入れたものから順に取り出して隣接頂点を調べます。訪問済みの判定（visited）を必ず行うことでループや重複訪問を防ぎます。
用途（代表例）
- 非負重（特に単位重み）グラフにおける最短経路の探索（最小辺数）
- 連結成分の発見（グラフが無向の場合）
- 各頂点の距離（レベル）付け：レベル分けは最小の辺数距離を意味する
- 二部グラフ判定（距離の偶奇で二色塗りできるかをチェック）
- 迷路探索（グリッドにおける最短道の発見）や、状態空間探索（ゲーム、パズルなど）
アルゴリズムの擬似コード
CLRS（Introduction to Algorithms）風の典型的な実装:
function BFS(G, s):
for each vertex u in G.V:
color[u] = WHITE
dist[u] = INF
parent[u] = NIL
color[s] = GRAY
dist[s] = 0
enqueue(Q, s)
while Q not empty:
u = dequeue(Q)
for each v in G.Adj[u]:
if color[v] == WHITE:
color[v] = GRAY
dist[v] = dist[u] + 1
parent[v] = u
enqueue(Q, v)
color[u] = BLACK
簡単な実装例（Python）
from collections import deque
def bfs(graph, start):
n = len(graph) # adjacency list: list of lists, 0..n-1
dist = [-1] * n
prev = [-1] * n
q = deque()
dist[start] = 0
q.append(start)
while q:
u = q.popleft()
for v in graph[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
prev[v] = u
q.append(v)
return dist, prev
計算量（時間・空間）
- 時間計算量（隣接リストを用いる場合）: O(V + E)
各頂点は一度だけキューに入れられ、各辺は探索中に一度だけ調べられるため。
- 時間計算量（隣接行列を用いる場合）: O(V^2)
各頂点の隣接チェックにO(V)がかかるため。典型的にはスパースグラフでは隣接リストが有利。
- 空間計算量: O(V)（訪問配列・距離配列・親配列・キューなど）
正当性（なぜ最短経路が得られるのか）
BFSは距離0→1→2…と順にレベルを拡張していくため、ある頂点を初めて発見したときの距離値は必ず始点からその頂点への最短の辺数に等しくなります。形式的には、発見順序が距離に対して非減少であることを帰納法で示せます。キューのFIFO性が「最短で発見した頂点から順に隣接を調べる」ことを担保する点が要です。
変種・発展
- マルチソースBFS: 複数の始点を同時にキューに入れて探索すれば、各頂点について「最も近い始点までの距離」を一回の探索で求められます。
- 双方向（Bidirectional）BFS: 始点と終点の双方からBFSを同時に行い、探索領域を半分程度に削減することで平均実行時間を大幅に短縮できます（最悪計算量のオーダーは変わらないが実用上高速）。
- 0-1 BFS: 辺の重みが 0 または 1 のグラフに対しては deque を使い、重み0の辺は前に、重み1は後ろに入れることで O(V + E) で最短距離を求められます（Dijkstraの特殊高速化）。
- Dijkstraとの違い: BFSは辺の重みが全て同じ（もしくは無視できる）場合に最短（最少辺数）を保障します。一般の正の重みがある場合はDijkstraが必要です。
実践上の注意点・最適化
- ノードIDが連続する整数（0..n-1）なら配列ベースの visited/dist を使うと高速。ハッシュセットは遅い場合がある。
- メモリ管理: 大規模グラフではキューと隣接リストのサイズがボトルネックになるので、必要最小限の情報だけ保持する（親配列はパス復元が不要なら省略）ことを検討。
- 再帰は使わない: BFSはキューベースなのでスタック深度問題は通常発生しないが、言語・実装でのオーバーヘッドに注意。
- 無向グラフでは辺を二度処理しないように visited チェックを必ず行う。
応用例（もう少し具体的に）
- 迷路で最短経路を見つける：グリッドをグラフにモデル化し、BFSで最短ステップ数と経路を取得。
- ソーシャル・ネットワーク解析：ある人物からの距離（友人→友人の距離）を計測。
- 幅優先探索木（BFSツリー）：各頂点の parent 情報から得られる木は、始点からの最短経路木になる。
- 二部グラフ判定：BFSでレベルを二色に割り当て、隣り合う頂点が同じ色になったら非二部。
よくある誤解
- 「BFSは最短経路を常に求める」は誤り：辺に重みがありそれが均一でない場合は最短距離（重み和）を保証しない。
- 「BFSが常に高速」は誤り：隣接行列を使うと O(V^2) になり、大規模ノード数では非効率になる。
まとめ
BFSはシンプルかつ強力なグラフ探索アルゴリズムで、非重みグラフでの最短経路（辺数）探索や連結性判定、二部判定など多数の用途を持ちます。キューを使ったレベルごとの拡張という特性により、正確な最短辺数と探索ツリーを効率的に構築できます。実装上は隣接リストを用いることで O(V + E) の計算量が得られ、状況に応じて双方向探索や0-1 BFSといった変種が役立ちます。
参考文献
- Breadth-first search - Wikipedia
- BFS — CP-Algorithms（競技プログラミング向け解説）
- Breadth First Search (BFS) — GeeksforGeeks
- Cormen et al., Introduction to Algorithms（書籍）
- Edward F. Moore — Wikipedia（BFS の起源に関する情報）
投稿者プロフィール
