幅優先探索

1. 根ノードを空のキューに加える。
2. ノードをキューの先頭から取り出し、以下の処理を行う。
   • ノードが探索対象であれば、探索をやめ結果を返す。
   • そうでない場合、ノードの子で未探索のものを全てキューに追加する。
3. もしキューが空ならば、グラフ内の全てのノードに対して処理が行われたので、探索をやめ"not found"と結果を返す。
4. 2に戻る。

ノードの展開により得られる子ノードはキューに追加される。訪問済みの管理は配列やセットなどでも行える。

v は頂点。

function 幅優先探索(v)
    Q ← 空のキュー
    v に訪問済みの印を付ける
    v を Q に追加
    while Q が空ではない do
        v ← Q から取り出す
        v を処理する
        for each v に接続している頂点 i do
            if i が未訪問 then
                i に訪問済みの印を付ける
                i を Q に追加

最悪の場合、幅優先探索は全ての経路を考慮に入れる必要があるので、幅優先探索の時間計算量はO(|E|)である。ここで|E|はグラフ内の辺の数である。

見つかったノードを全て記録する必要があるので、幅優先探索の空間計算量はO(|V|)となる。ここで|V|はグラフ内のノードの数である。または、${\displaystyle O(B^{M})}$ということができる。Bは枝分かれの最大数で、Mは木の最長経路の長さ。指数関数故に、幅優先探索は大量の情報から探索する事に向かない根拠になる。

幅優先探索は完全である。つまり解が存在する場合はグラフの構造によらず、解をみつけることができる。しかしグラフが無限で探索対象の解が存在しない場合、幅優先探索は終了しない。

一般に幅優先探索は最適で、常に開始ノードと終了ノードの長さが最も少ない辺を返す。もしグラフが重みつきならば、最初のノードの隣のノードが最良のゴールとは限らないが、この問題は辺のコストを考慮に入れた均一コスト探索(Uniform cost search)で解決できる。

幅優先探索はグラフ理論における多くの問題を解くために使うことができる。以下は一例である。

• グラフ内の全ての連結成分をみつける。幅優先探索で到達するノードの集合は初期ノードを含む最大の連結成分である。
• 1つの連結成分内の全てのノードをみつける。
• 辺の重みなしグラフの最小全域木を求める。
• 辺の重みなしグラフの単一始点最短経路問題を解く。
• グラフが2部グラフ(Bipartite graph)かどうかテストする。もし幅優先探索の同じ段階のノード集合に存在するノードに合流する辺があるならば、グラフには奇数長の閉路が存在し2部グラフではない。

参照透過な関数型言語の場合は余再帰と遅延評価を使うと簡潔に書ける。下記はScalaの場合で、LazyListが遅延リストで、LazyList.unfoldが余再帰。

import scala.collection.immutable.Queue

case class Tree[T](value: T, children: Seq[Tree[T]])

def breadthFirstSearch[T](root: Tree[T]): LazyList[T] =
  LazyList.unfold(Queue(root))(q => q.dequeueOption.map((tree, queue) => (tree.value, queue ++ tree.children)))