レベル順探索(BFS)とは何か？概要・実装・応用・最短経路の復元まで徹底解説
エバープレイ編集部レベル順探索とは — 概要
レベル順探索（レベルじゅんたんさく）とは、グラフや木構造に対する探索アルゴリズムの一種で、根（または出発点）からの距離（辺の本数）に従って、近いノードから順に訪問していく方法を指します。一般的には英語で「Breadth-First Search（BFS）」や「level-order traversal」と呼ばれるアルゴリズムが該当します。
基本的な考え方と手順
レベル順探索は幅優先に探索を進めるため、まず根ノード（起点）を訪問し、その隣接ノードを次にすべて訪問します。さらにその次に隣接するノード（つまり距離が2のノード）を訪問するといった具合に、距離の層（レベル）を順に広げていきます。これを実現するためにキュー（FIFO）構造を用いるのが一般的です。
- 起点をキューに入れて訪問済みにする。
- キューが空になるまで以下を繰り返す：キューからノードを取り出し、その未訪問の隣接ノードをすべてキューに入れて訪問済みにする。
擬似コード（典型例）
木とグラフでほぼ共通の実装パターンです。グラフではサイクル回避のために訪問フラグが必須です。
function BFS(start):
queue = new Queue()
visited = set()
parent = map() // 必要なら経路復元用
distance = map() // 必要なら距離保存用
enqueue(queue, start)
visited.add(start)
distance[start] = 0
while not queue.isEmpty():
v = dequeue(queue)
for each neighbor u of v:
if u not in visited:
visited.add(u)
parent[u] = v
distance[u] = distance[v] + 1
enqueue(queue, u)
計算量（時間・空間）
グラフ G(V, E) に対するレベル順探索の計算量は次のようになります。
- 時間計算量：O(|V| + |E|)。各頂点は一度だけキューに入れられ、各辺は探索中に少なくとも一度参照されます。
- 空間計算量：O(|V|)。訪問フラグやキュー、必要なら距離・親情報を保存するため、頂点数に比例したメモリが必要です。
探索対象が木や格子（幅 b、深さ d の完全木のような構造）で記述される場合、ノード数は O(b^d) のオーダーになるため、深さが増すとメモリ使用が急増します。
グラフ探索における注意点
- サイクルのあるグラフでは、同じノードを何度も訪問しないように「visited」集合を必ず使うこと。
- 有向グラフ・無向グラフのどちらでも利用可能。ただし辺の取り扱い（隣接リスト／行列）に注意。
- 重み付きグラフ（辺に重みがある場合）：各辺のコストが均一（またはすべて同じ重み）であれば最短パスとして機能しますが、重みが異なる場合はダイクストラ法やA*などを用いる必要があります。
用途・応用例
- 最短経路探索（非負でかつ単位重み、あるいは無重みのグラフ）：始点から各ノードへの最短距離（辺の本数）を求める。
- 連結成分の検出：未訪問のノードを起点にBFSを繰り返すことで連結成分を列挙できる。
- 二部グラフ判定：BFSで各ノードに「色」を割り当てて隣接ノードと異なる色にすることで二部性を検査できる。
- 最短経路の復元：探索中に親ノードを保存しておけば、目的ノードから親をたどることで最短経路を復元できる。
- ゲームAIやパズル：移動回数が最小となる解（例えばパズルの最短手数）を探索する際に用いられる。
- WebクローリングやSNSの距離計算：あるノードからの到達範囲や友達の距離（何次の関係か）を調べるのに便利。
- フローアルゴリズム（Edmonds–Karp）：増加パスの発見にBFSを用いることで計算量保証が得られる例がある。
BFSが優れている点と制約
優れている点：
- 単純で実装が容易。
- 非加重グラフにおいては最短経路（辺の本数）を保証する。
- 他のアルゴリズム（二部判定、最短路の復元など）と組み合わせやすい。
制約・注意点：
- メモリ消費が大きくなりがち：幅が広い探索空間ではキューに大量のノードが入る。
- 重み付きグラフ（重みが辺によって異なる）では最短経路を保証しない。
- 非常に大きな（あるいは無限の）状態空間では実用的でない場合がある。
実装上の工夫・バリエーション
- レベルごとの分離：キューの現在のサイズを取得して1レベルのノード数を把握し、レベル単位で処理を分けることで深さ（距離）ごとの処理を行いやすくする。
- 二重キュー法：現在のレベル用キューと次レベル用キューを使い分ける実装もある。
- 親情報と距離の保存：経路復元や階層情報が必要な場合は parent[]、distance[] を併用する。
- Bidirectional BFS（双方向BFS）：探索の起点と終点から同時にBFSを行い、その中間でぶつけることで探索量を大幅に削減できる（最短路探索に有効）。
- 有限幅・有限深さの最適化：探索深さに上限がある場合は深さ制限付きBFSで無駄な展開を抑える。
レベル順探索（木のレベル順）とBFSの関係
木構造における「レベル順探索」は、言葉通りノードの深さ（ルートからの深さ）順にノードを訪問することを意味します。これはまさにBFSの特別ケースです。二分木などでは「レベルオーダー」として実装され、各レベルを一行ずつ出力するような用途が典型的です。
具体例：2次元グリッド上の最短経路
マス目（グリッド）上で上下左右に移動できる場合、各マスをノード、隣接するマスを辺とみなすと、BFSで目的地までの最短手数（通過マス数）を効率よく求められます。壁や障害物がある場合はそれらのセルを未訪問扱いにしないだけで対応可能です。
他の探索法との比較
- 深さ優先探索（DFS）：メモリは小さく済む（再帰深さを除く）場合が多いが、最短路を保証しない。探索空間が深い場合に有利。
- ダイクストラ法：重みがある場合の最短路に有効。BFSは辺重みが均一の場合の特別解。
- A*探索：ヒューリスティックが使える場合に最短経路探索を効率化できる。状態空間が大きいときはBFSよりも有効なことが多い。
- IDDFS（反復深さ優先探索）：メモリ効率を重視しつつ最短解を見つけられるが、計算量が増えるトレードオフがある。
実務上のポイント
- 大規模なグラフを扱う場合、隣接リスト表現を使うことでメモリと時間の面で効率的。
- 外部記憶（ディスク）にまたがる巨大グラフでは、BFSのための特別な分散/外部アルゴリズムが必要になる。
- 探索の途中で途中停止（早期終了）できるかどうかを設計段階で検討する。目的ノードを見つけたら直ちに終了すると多くの無駄な展開を省ける。
- 並列化：レベル単位で独立に処理可能な部分もあるため、並列化により性能改善が期待できる場面もある。
まとめ（実践の心得）
レベル順探索（BFS）は、簡潔で理論的にも確立された探査法であり、特に非重みグラフにおける最短経路や階層構造の解析に強力です。一方で、探索幅が大きい場合のメモリ消費や、重み付き・巨大グラフへの適用に限界があるため、用途に応じてダイクストラ法・A*・IDDFS・双方向探索などと使い分けることが重要です。実務では、データ構造（隣接リスト・行列）やメモリ制約、早期終了条件などを考慮した実装設計が鍵となります。
参考文献
- Wikipedia: ブレッドファースト探索（日本語）
- Wikipedia: Breadth-first search (English)
- CP-Algorithms: Breadth First Search (BFS)
- GeeksforGeeks: Breadth First Search (BFS) for a Graph
- Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms（一般的なアルゴリズム教科書）
投稿者プロフィール
