幅優先探索（BFS）とは？最短経路の仕組み・時間・実装例・応用をわかりやすく解説
エバープレイ編集部幅優先探索（Breadth-First Search）とは
幅優先探索（BFS: Breadth-First Search）は、グラフや格子状の状態空間を層（深さ）ごとに幅広く探索していく基本的な探索アルゴリズムです。始点から到達可能なノードを、到達に必要な辺の数（距離）の小さい順に順に訪問していくため、非負の一様重み（すなわち「各辺の重みが等しい」＝普通のグラフの辺数で距離を計る場合）において最短経路を見つけるのに非常に有用です。
アルゴリズムの概要
BFSは次のような手順で動作します。
- キュー（FIFO）を用意し、始点をキューに入れる。
- キューからノードを取り出し、そのノードに隣接する未訪問ノードをすべてキューに追加する（訪問済みとしてマークする）。
- キューが空になるまで、もしくは目的ノードを見つけるまでこれを繰り返す。
「層」や「距離」は、始点からの辺の本数で表され、キューに入った順序によって必然的に短い距離から順に処理されます。
擬似コード
function BFS(graph, start):
create empty queue Q
mark start as visited
distance[start] = 0
parent[start] = null
enqueue Q <- start
while Q not empty:
v = dequeue Q
for each neighbor u of v:
if u is not visited:
mark u as visited
distance[u] = distance[v] + 1
parent[u] = v
enqueue Q <- u
時間計算量と空間計算量
- 時間計算量（隣接リストを使用した場合）：O(V + E)
各頂点は一度だけ訪問され、各辺も調べられるのは一度（有向グラフ）または両端で合計二度（無向グラフ）なので合計で O(V + E) になります。
- 時間計算量（隣接行列を使用した場合）：O(V^2)
各頂点に対して全頂点との隣接を確認するため、O(V^2) になります。
- 空間計算量：O(V)
訪問済み配列、距離配列、親配列、そしてキューが各頂点について情報を保持するため O(V)。ただしグラフの表現（隣接リストは O(V+E)、隣接行列は O(V^2)）も含めるとその分が追加されます。
BFSの性質と正当性
- 最短路性：無向グラフや重みが均一（各辺の重みが同じ）な有向グラフにおいて、BFSは始点から各頂点への最短経路（辺数が最小のもの）を保証します。これは、キューによって距離 d のノードがすべて処理されてから距離 d+1 のノードが処理されるためです。
- BFS木：BFSによって作られる親（parent）情報をたどると、始点を根とする「BFS木（または森林）」が得られます。これは最短路ツリーになります。
- 到達可能性：ある頂点が探索中に訪問されたか否かで、始点からその頂点に到達可能かを判断できます。
実用例と応用
BFSは多くの場面で役立ちます。代表的な用途を挙げます。
- 最短経路問題（無重みグラフ） — 迷路やグリッドでの最短ステップ数探索。
- 連結成分の検出 — 無向グラフの各連結成分を得る。
- 二部グラフ判定 — レベル（偶奇）に色分けして矛盾がないかチェックする。
- 最小時間（ステップ数）で到達可能な状態探索 — 状態空間検索、パズル、ゲームAIの単純な戦略。
- レイヤー分け・距離計算 — ネットワーク分析でノード間距離を測る。
- Webクローリングなどの幅優先探索的取得（深さを制限して探索する場合）
例：格子（迷路）での最短経路
4方向移動可能な二次元グリッド上で、障害物を避けながら始点から終点へ最短のステップ数を求める典型例を考えます。各セルを頂点、隣接する通行可能なセル間に辺を張ることでグラフモデルにできます。BFS を使えば、障害物がある状況でも最短経路（移動ステップ数）が得られます。
実装例（Python）
from collections import deque
def bfs_shortest_path(graph, start, goal):
# graph: adjacency list, graph[v] = list of neighbors
q = deque([start])
visited = {start}
parent = {start: None}
while q:
v = q.popleft()
if v == goal:
# reconstruct path
path = []
while v is not None:
path.append(v)
v = parent[v]
path.reverse()
return path
for u in graph[v]:
if u not in visited:
visited.add(u)
parent[u] = v
q.append(u)
return None # goal unreachable
上記は隣接リストで表現したグラフに対する典型的な実装です。距離だけが必要であれば parent を distance に置き換えてもよいでしょう。
派生・応用アルゴリズム
- 双方向幅優先探索（Bidirectional BFS）：始点側と目標側の双方から同時にBFSを行い、探索空間を大幅に削減する手法。特に深さ d の場合、探索量は概ね O(b^{d/2}) に抑えられることがある（b は分岐率）。
- 0-1 BFS：辺の重みが0か1だけの場合、デック（deque）を使うことで Dijkstra と同等の結果を O(V + E) で得られる工夫。
- Dijkstra との関係：BFS は各辺の重みが等しい（あるいは単に辺の数を距離とする）特別な場合の最短経路アルゴリズムと考えられ、非負重みの場合は Dijkstra を使う。
実装上の注意点・落とし穴
- 訪問済み判定：必ずノードをキューに入れると同時に visited にマークする（遅延マークにすると同じノードがキューに何度も入る可能性がある）。
- メモリ使用量：分岐率が高く、距離が深い場合、キューに大量のノードが溜まりメモリ不足を招く可能性がある。大規模グラフや無限状態空間（理論的な）には注意。
- 重みのあるグラフ：重みが均一でない場合は BFS は正しい最短解を保証しないため、Dijkstra や A* が必要。
- 有向グラフか無向グラフか：隣接リストの生成・辺の反復回数に注意。無向グラフでは各辺が双方のリストに存在する。
- 再現性：親ポインタから経路を復元する方式を考えると、最短経路自体の出力が簡単になる。
実践的なチューニング
- 隣接リストを使う：スパースグラフでは O(V + E) を活かせる。隣接行列は非常に大きいグラフには不向き。
- メモリ節約：訪問済みと親をビットや小さい型で管理する、不要なデータは保持しない。
- 早期終了：目的ノードがわかっているなら見つけた時点で探索を止める（全点探索は不要）。
- 並列化の注意：BFS はレベル単位で並列化しやすいが、実装の同期やメモリ競合に注意。
まとめ
幅優先探索は、グラフ探索の基本かつ強力な手法です。単純な構造ながら、最短経路の保証、連結性判定、二部グラフ判定など幅広い用途に使えます。適切なデータ構造（隣接リスト、キュー、visited配列）を用いれば、時間計算量 O(V + E)、空間計算量 O(V) で効率よく動作します。用途によっては双方向探索や 0-1 BFS といった派生手法も有効です。大規模データや重み付きグラフでは別のアルゴリズムの検討が必要ですが、まずは BFS を正確に理解しておくことが重要です。
参考文献
- 幅優先探索 - Wikipedia（日本語）
- Breadth-first search - Wikipedia（英語）
- アルゴリズム教科書（参考）：BFSに関する記述（講義ノート）
- BFS — CP-algorithms（実装と応用）
- MIT OpenCourseWare: Breadth-First Search（講義資料）
投稿者プロフィール
