1 基本概念
幅優先探索は、始点に近い頂点から順に調べていく探索手法である。木やグラフを層ごとに広がるように走査するため、ある頂点からの距離が短い順に候補を扱える。経路の有無を確かめたり、到達できる範囲を把握したりする場面で広く用いられる。
1.1 定義
幅優先探索は、ある頂点を出発点として、まずその隣接頂点をすべて登録し、次にそれらの隣接先へと順に探索を進める方法である。探索の進行は深さではなく距離の近さに基づく。
1.2 深さ優先探索との違い
深さ優先探索が1本の経路をできるだけ深く進むのに対し、幅優先探索は同じ深さにある頂点をまとめて処理する。前者は行き止まりまで掘り下げる性質が強く、後者は横方向へ広がる性質が強い。
1.3 探索の目的
この手法の目的は、探索対象を漏れなく調べることに加え、始点からの近さを保ったまま順序立てて処理する点にある。そのため、最短経路の発見、連結性の確認、層構造の把握に適している。
2 アルゴリズムの流れ
幅優先探索の基本的な流れは、始点を登録し、順に取り出し、未訪問の隣接頂点を追加していくという手順で構成される。登録と取り出しの順序を保つことで、距離の近い頂点から先に扱える。
2.1 初期化
まず始点を訪問済みとして扱い、待ち行列に入れる。必要に応じて距離配列や親頂点の記録も初期化し、探索の基準を整える。
2.2 頂点の取り出し
待ち行列の先頭にある頂点を取り出し、その頂点を現在の処理対象とする。これにより、先に登録された頂点が先に処理される。
2.3 隣接頂点の登録
取り出した頂点に隣接する各頂点を確認し、まだ訪問していないものを訪問済みにして待ち行列へ加える。距離や親を記録する実装では、この時点で値を更新する。
2.4 終了条件
待ち行列が空になれば探索は終了する。すべての到達可能な頂点が処理されたことを意味する。
3 データ構造
幅優先探索では、探索順の管理と重複防止のために、いくつかの補助構造を用いる。代表的なのは待ち行列、訪問済み管理、距離配列である。
3.1 待ち行列
待ち行列は先入れ先出しで要素を扱う構造で、幅優先探索の順序を支える中心的な要素である。新しく見つかった頂点を末尾に追加し、先に入ったものから順に処理する。
3.2 訪問済み管理
訪問済み管理は、同じ頂点を何度も処理しないために使う。配列や集合で実現されることが多く、探索の重複や循環による無限処理を防ぐ。
3.3 距離配列
距離配列は、始点から各頂点までの最短距離候補を保存するための仕組みである。無重みグラフでは、探索の層に応じて値が1ずつ増える形で記録される。
3.3.1 最短距離の記録
無重みグラフにおいては、初めて到達した時点の距離が最短距離になる。したがって、その時に記録した値を採用すればよい。
3.3.2 親頂点の記録
親頂点を記録すると、探索後に経路を復元しやすい。目的地から親をたどることで、始点までの道筋を逆向きに再構成できる。
4 性質と特徴
幅優先探索は、距離の近い頂点を優先する性質から、特定の条件下で強い保証を持つ。加えて、実装が比較的素直で、基礎アルゴリズムとして扱いやすい。
4.1 最短経路性
各辺の重みが等しい、または重みを考えない場合、幅優先探索は始点から各頂点への最短経路を与える。これは、より短い経路があれば必ず先に発見されるためである。
4.2 計算量
計算量は、頂点数と辺数に対してどの程度の資源を要するかを表す。幅優先探索は一般に効率がよく、基本的なグラフ走査として標準的な位置を占める。
4.2.1 時間計算量
隣接リストを用いる場合、各頂点と各辺を高々一定回数ずつ調べるため、時間計算量は概ねO(V+E)で表される。ここでVは頂点数、Eは辺数である。
4.2.2 空間計算量
空間計算量は、待ち行列と補助配列の大きさに左右される。最悪の場合、探索対象の多くを一時的に保持するため、必要容量は頂点数に比例する。
4.3 探索順序の性質
幅優先探索では、始点からの距離が小さい層から順に処理が進む。したがって、結果として得られる順序は、同じ距離内での細かな並びは実装依存でも、層の単位では一貫している。
5 実装
実装では、木かグラフか、さらに隣接表現が何かによって細部が変わる。もっとも基本的には、再帰を使わず待ち行列で管理する形が採用される。
5.1 木に対する実装
木では通常、親から子へと自然に展開できるため、循環対策が不要な場合が多い。根を始点として、各子を順番に登録していけばよい。
5.2 グラフに対する実装
グラフでは閉路や多重経路があるため、訪問済み管理が欠かせない。無向グラフでも有向グラフでも、再訪の制御が探索の安定性を左右する。
5.3 再帰を用いない実装
幅優先探索は待ち行列を使うため、通常は再帰を必要としない。これにより、呼び出しの深さに依存しにくく、比較的大きな構造にも対応しやすい。
5.4 典型的な疑似コード
典型例では、始点を待ち行列に入れ、空になるまで先頭を取り出して隣接頂点を確認する。未訪問の頂点があれば訪問済みにし、距離や親を更新して末尾へ追加する。
6 応用
幅優先探索は、単なる走査にとどまらず、多くの問題の基盤として使われる。最短性や層構造の把握が必要な場面では特に有効である。
6.1 最短経路問題
無重みグラフでは、始点から各頂点への最短経路を求める基本手段となる。経路の長さが辺数で測られる問題に向く。
6.2 連結成分の判定
ある頂点から探索して到達できる範囲を調べれば、同じ連結成分に属する頂点群を特定できる。未訪問の頂点を順に始点として用いれば、全成分の分割にも使える。
6.3 レベル順走査
木のレベル順走査では、根に近い層から順番に節点を処理する。幅優先探索はこの目的に自然に一致する。
6.4 パズル・迷路探索
迷路や状態空間の探索では、各状態を頂点、遷移を辺として扱える。手数の少ない解を求めたい場合に、幅優先探索は有力である。
7 変種
標準的な幅優先探索から派生した手法には、始点を複数にしたものや、両端から進めるものがある。重み付き問題に対応させるには、別の工夫が必要になる。
7.1 多始点探索
複数の始点を同時に待ち行列へ入れて開始する方法である。複数の出発点からの最短到達を一度に調べる場合に便利である。
7.2 双方向探索
始点側と終点側の両方から探索を進め、途中で合流を狙う方法である。探索範囲を抑えやすく、条件によっては効率が改善される。
7.3 重み付きグラフへの拡張
辺に重みがある場合、単純な幅優先探索では最短経路性が保たれないことがある。そのため、重みに応じた別の優先順序を導入する必要がある。
7.3.1 ダイクストラ法との関係
ダイクストラ法は、重み付きグラフに対して距離の小さい頂点から処理する点で、幅優先探索と発想が近い。ただし、取り出し順を待ち行列ではなく優先度付きの構造で管理する。
7.3.2 制約付き探索
重みや条件に制約がある場合、状態を拡張して探索することがある。距離だけでなく、使用回数や属性を組み込むことで、より複雑な問題に対応できる。
8 関連する概念
幅優先探索は、グラフ理論や木構造の基礎的な考え方と密接に結びついている。探索アルゴリズム全般の中でも、最初に学ばれる代表例の一つである。
8.1 グラフ理論
グラフ理論では、頂点と辺の関係を扱う。幅優先探索は、グラフの構造を層ごとに理解するための基本手段として位置づけられる。
8.2 木構造
木構造では、親子関係が明確で、層の概念を取り入れやすい。幅優先探索は、木の階層を順に見る処理と相性がよい。
8.3 探索アルゴリズム
探索アルゴリズムには、深さ優先探索や反復深化など、複数の系統がある。幅優先探索はその中で、距離の近さを重視する代表的な方法である。