幅優先探索（BFS）とは？仕組み・コード・計算量をわかりやすく解説

BFSが解く問題

多くの問題は、実はグラフとして表せます。Webページとリンク、SNSの友達関係、ゲーム盤のマス、パズルの状態などです。BFSは、そうしたグラフについての2つのよくある問いに答えます。開始ノードからどのノードに到達できるか、そしてそれぞれに到達するまでの最小ステップ数はいくつか、です。

BFSは距離が近い順に輪を広げるように探索するため、あるノードに初めて到達したときの経路は必ず辺の数が最も少ないものになります。そのため、すべての辺のコストが等しい場合の最短経路アルゴリズムとして標準的に使われます。

考え方を言葉で説明すると

1. 開始ノードをキューに入れ、訪問済みにします。
2. キューの先頭からノードを1つ取り出します。
3. まだ訪問していない隣接ノードごとに、訪問済みにしてキューの末尾に追加します。
4. キューが空になるまで、手順2と3を繰り返します。

ノードを訪問済みにするのは、キューから取り出すときではなく、キューに追加するときです。そうしないと、処理される前に同じノードが何度も追加されてしまいます。

具体例で一歩ずつ確認

次の無向グラフを考えます。A–B、A–C、B–D、C–D、C–E、D–F。A から始めて、隣接ノードはアルファベット順に訪問します。

訪問順は A, B, C, D, E, F です。D は B からも C からも到達できますが、その時点で訪問済みになるため、B から1回だけ発見されます。

Pythonでの実装

キューには collections.deque を使います。popleft() は O(1) ですが、list.pop(0) は O(n) です。グラフは、各ノードを隣接ノードのリストに対応づける辞書（隣接リスト）で表します。

from collections import deque
def bfs(graph, start):
    """Return the distance (number of edges) from start to each reachable node."""
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in dist:          # not visited yet
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist
graph = {
    "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
    "D": ["B", "C", "F"], "E": ["C"], "F": ["D"],
}
print(bfs(graph, "A"))  # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}

ここでは dist 辞書が訪問済み集合と答えの保存を兼ねています。実際の経路を復元するには、各ノードの親も記録しておき、ゴールから親をたどって戻ります。

def shortest_path(graph, start, goal):
    parent = {start: None}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            path = []
            while node is not None:
                path.append(node)
                node = parent[node]
            return path[::-1]
        for nxt in graph[node]:
            if nxt not in parent:
                parent[nxt] = node
                queue.append(nxt)
    return None  # goal not reachable
print(shortest_path(graph, "A", "F"))  # ['A', 'B', 'D', 'F']

時間計算量と空間計算量

V は頂点（ノード）の数、E は辺の数です。リストの代わりに隣接行列を使うと、ノードの隣接ノードを求めるのに O(V) かかるため、時間計算量は O(V²) になります。

バリエーションとよくある間違い

• グリッドBFS：各マスをノード、上下左右（または斜めを含む8方向）の隣のマスを辺とみなします。マスを追加する前に、範囲外や壁でないかを確認します。
• 多始点BFS：複数の開始ノードを距離 0 としてキューに入れます。迷路の最寄りの出口など、最も近い始点までの距離を求められます。
• 0-1 BFS：辺の重みが 0 か 1 だけの場合、両端キュー（deque）を使い、重み 0 の隣接ノードを先頭側に入れます。O(V + E) で最短経路が得られます。
• 双方向BFS：開始ノードとゴールの両方から同時に探索し、2つの探索範囲が出会ったところで終了します。探索するノード数を大幅に減らせることがよくあります。
• 階層ごとの処理：各ラウンドの開始時に len(queue) を記録し、その個数だけ取り出すと、1階層ずつ処理できます。

BFSを使う場面と実世界での用途

• コーディング面接の問題：迷路やグリッドの最短経路、単語はしご（word ladder）、腐ったオレンジ（多始点BFS）、二分木のレベル順走査、ナイトの最小手数など。
• ネットワーク：k ホップ以内のすべての機器の探索、P2Pネットワークでのブロードキャスト、SNSでの距離2の「知り合いかも」の表示など。
• シードとなるページからのリンク距離の順にページを巡回するWebクローラー。
• ガベージコレクタ（例：チェイニーのコピーGC）や、最少手数を求めるパズルソルバー。