幅優先探索（BFS）の基礎と実装ガイド｜最短経路・連結成分・グラフ分析を徹底解説

2025年11月20日 最終更新日時 : 2025年11月20日 エバープレイ編集部

幅優先トラバーサル（Breadth-First Traversal）とは

幅優先トラバーサル（BFS: Breadth-First Traversal／Breadth-First Search）は、グラフや木構造を探索する基本的なアルゴリズムの一つです。探索は「根（または開始ノード）から近い頂点を先に訪れる（広がりを優先する）」という方針で行われ、主に最短経路（辺数が最小）の算出、連結成分の検出、レベル（深さ）ごとの処理などに広く用いられます。

基本的な考え方と手順

BFSはキュー（FIFO）を用いて探索を行います。手順は簡潔に言うと次の通りです。

  • 開始ノードをキューに入れ、訪問済みとしてマークする（visited）。
  • キューから先頭ノードを取り出し、その隣接ノード（未訪問のもの）をすべてキューに追加し、訪問済みとする。
  • キューが空になるまで2を繰り返す。

この過程で各ノードに「親（parent）」や「距離（distance: 開始ノードからの辺数）」を記録していけば、最短経路復元やレベル別処理が可能です。

擬似コード（Python風）

from collections import deque

def bfs(graph, start):
    # graph: {node: [neighbour, ...], ...}
    visited = set()
    parent = {}
    distance = {}
    q = deque()

    visited.add(start)
    parent[start] = None
    distance[start] = 0
    q.append(start)

    while q:
        v = q.popleft()
        for w in graph[v]:
            if w not in visited:
                visited.add(w)
                parent[w] = v
                distance[w] = distance[v] + 1
                q.append(w)

    return parent, distance

計算量（時間・空間）

  • 時間計算量（隣接リストを用いる場合）: O(V + E)。各頂点は一度キューに入る（または一度処理される）程度で、各辺は隣接リストの走査で一度ずつ触れられるため。
  • 時間計算量（隣接行列を用いる場合）: O(V^2)。各頂点について全ての可能な隣接をチェックするため。
  • 空間計算量: O(V)。visited、distance、parent、そしてキューに最大で O(V) のノードが入る可能性があるため。

正当性（最短距離の保証）

BFSは「層（レベル）ごとに探索する」ため、開始ノードからの辺の数が少ないノードほど先にキューから取り出され、距離が確定します。したがって、無加重グラフ（各辺のコストが等しい）においては、BFSによって得られる distance は開始ノードからの最短経路（辺数最小）を示します。これは数学的には帰納法で示せます：開始ノードから距離 k のノードは、距離 k−1 のノードから直接到達されるため、距離が小さい順に確定されるからです。

ツリーとグラフの違い

  • 木（ツリー）ではサイクルがないため、単純に親子関係が成立し、レベル順（level-order）走査として扱われます。二分木なら「レベル順走査（level-order traversal）」と呼ばれることが多いです。
  • 一般グラフではサイクルが存在するため、visited（あるいは色分け：白・灰・黒）を用いて既訪問ノードを再度キューに入れないようにします。これにより無限ループを防ぎます。

代表的な応用例（IT分野）

  • 最短経路探索（無加重グラフ）: ネットワーク上のホップ数最小経路、迷路の最短ルートなど。
  • 連結成分の検出: 無向グラフである頂点集合がどの接続成分に属するかを判定。
  • 二部グラフ判定: BFSで各ノードに交互の色を割り当てて矛盾がないか確認することで二部性を判定できる。
  • レイヤー化・影響範囲の計算: ソーシャルグラフでの距離計算（友人の友人までの到達性など）、Webクローリングにおける「深さ優先ではなく幅優先で浅いページを優先取得」など。
  • AIの単純な経路探索（グリッド等）: 障害物を考えた最短（最少ステップ）経路探索。

BFSと他アルゴリズムの比較

  • BFS vs DFS（深さ優先探索）: DFSは深く潜る探索で経路復元やサイクル検出、トポロジカルソートの応用が得意。BFSは最短経路（辺数ベース）やレベル情報が必要な場合に有利。
  • BFS vs Dijkstra: Dijkstraは重み付きグラフ（非負重）での最短経路を求める。全ての辺重みが等しい（例えば1）の場合、DijkstraはBFSと等価だが、辺に重みがある場合はDijkstraを使う必要がある。
  • 単方向BFS vs 双方向（Bidirectional）BFS: 開始点と目標点の双方から同時にBFSを行うと探索空間を大幅に削減できる場合が多く、特に探索深さ（d）が大きい時に有効。

実装上のポイントと注意点

  • visitedのマークは「キューに入れる時点」で行うのが安全（複数回キューに入らないようにする）。
  • 大規模グラフではメモリが問題になる：隣接リストの表現、ビットセットや圧縮表現（CSR/CSR形式）を検討する。
  • 並列化（マルチスレッド／分散）でのBFSは技術的に難しく、フロント層（フロンティア）の同期や通信コストが課題になる。大規模グラフ処理専用のアルゴリズム（外部メモリBFS、分散BFS）も存在する。
  • 無限グラフ（オンザフライ生成）や状態空間探索では、状態表現とヒューリスティクスの有無により適切な手法を選択する（A*は重み付き・ヒューリスティック有りの場合の選択肢）。

最適化と実用技術

  • 早期終端: 目標ノードが固定なら見つかり次第探索を打ち切ることで平均時間を削減できる。
  • 隣接リストの走査順序: 実装により探索順が変わるが、性能には通常大きな影響はない。ただしメモリ局所性を改善すると実行速度が上がる場合がある。
  • 双方向BFS: 始点と終点のどちらか少ないノード数側から広げる、あるいは同時に両側から広げて衝突判定をする。
  • ビット演算やワード並列性を使ったフロント層操作: 大規模ビット集合での処理が可能な場合、複数ノードの探索をまとめて行える。

簡単な適用例：グリッド迷路の最短経路

幅優先探索は2次元グリッド（上下左右4方向移動）での最短ステップ探索にそのまま使えます。各セルをノード、隣接する通行可能セルを辺とみなしてBFSを行えば、壁を避けた最短ルートが得られます。実装上は訪問済み配列（もしくは距離配列）とキューを用います。

まとめ（実務的な選び方）

無加重グラフで最短経路やレイヤー情報が必要な場合、BFSは最も基本的かつ効率的な選択です。グラフ規模やメモリ制約、目的（最短経路、連結性確認、二部判定など）に応じて、隣接表現の選定、双方向探索や外部メモリ手法の採用を検討してください。重み付きグラフや巨大分散グラフのケースでは、より適切なアルゴリズムや実装設計が必要になります。

参考文献

カテゴリー
IT
前の記事
BFS（幅優先探索）入門：最短経路・連結成分・二部グラフ判定まで網羅する実践ガイドNew!!
2025年11月20日
次の記事
グラフ探索入門：BFS/DFSから最短経路アルゴリズムと実務応用まで徹底解説New!!
2025年11月20日