幅優先探索（はばゆうせんたんさく、）はグラフ理論()において木構造()やグラフ()の探索に用いられるアルゴリズム。アルゴリズムは根ノードで始まり隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。「横型探索」とも言われる。幅優先探索は解を探すために、グラフの全てのノードを網羅的に展開・検査する。最良優先探索とは異なり、ノード探索にヒューリスティクスを使わずに、グラフ全体を目的のノードがみつかるまで、目的のノードに接近しているかどうかなどは考慮せず探索する。ノードの展開により得られる子ノードはキューに追加される。訪問済みの管理は配列やセットなどでも行える。v は頂点。最悪の場合、幅優先探索は全ての経路を考慮に入れる必要があるので、幅優先探索の時間計算量はO(|E|)である。ここで|E|はグラフ内の辺の数である。見つかったノードを全て記録する必要があるので、幅優先探索の空間計算量はO(|V|)となる。ここで|V|はグラフ内のノードの数である。または、formula_1ということができる。ここでBは枝分かれの最大数でMは木の最長経路の長さである。この量の巨大さは幅優先探索が規模の大きな探索において非現実的な理由である。幅優先探索は完全である。つまり、解が存在する場合はグラフによらず解をみつけることができるということである。しかしながら、グラフが無限で探索対象の解が存在しない場合、幅優先探索は終了しない。一般に幅優先探索は最適で、常に開始ノードと終了ノードの長さが最も少ない辺を返す。もしグラフが重みつきならば、最初のノードの隣のノードが最良のゴールとは限らないが、この問題は辺のコストを考慮に入れた均一コスト探索()で解決できる。幅優先探索はグラフ理論における多くの問題を解くために使うことができる。以下は一例である。参照透過な関数型言語の場合は余再帰と遅延評価を使うと簡潔に書ける。下記は Scala の場合で、Scalaz の unfold が余再帰で、Stream が遅延リスト。import scala.collection.immutable.Queueimport scalaz.Scalaz.unfoldcase class Tree[T](value: T, children: Seq[Tree[T]])def breadthFirstSearch[T](root: Tree[T]): Stream[T] =

出典:wikipedia