幅優先探索のソースを表示

{| class="infobox" style="margin-left: 0.5em; border:1px #aaa solid; border-collapse: collapse;"
! style="background-color: #ffc0c0; border:1px #aaa solid;" |  幅優先探索
|-
| style="margin: 0 auto; text-align: center; font-size: smaller;"| [[ファイル:Breadth-first-tree.png|none|300px|Order in which the nodes get expanded]]<br />探索順
|-
! style="background-color: #ffc0c0; border:1px #aaa solid;" | '''General Data'''
|-
|
{| style="border: 0;" 
|-
| ''Class'': || [[探索|探索アルゴリズム]]
|-
| ''データ構造'': || [[グラフ (データ構造)|グラフ]]
|-
| ''時間計算量'': || <math>O(|V|+|E|)</math>
|-
| ''空間計算量'': || <math>O(|V|+|E|)</math>
|-
| ''Optimal'': || yes
|-
| ''Complete'': || yes
|-
|}
|-
|}
'''幅優先探索'''([[:en:breadth-first search|Breadth first search]])は[[グラフ理論]]([[:en:graph theory|Graph theory]])において[[木構造 (データ構造)|木構造]]([[:en:tree structure|tree structure]])や[[グラフ (データ構造)|グラフ]]([[:en:graph (data structure)|graph]])の探索に用いられる。アルゴリズムは根ノードで始まり隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。「'''横型探索'''」とも言われる。

== どう動作するか ==
形式としては、幅優先探索は解を探すために、グラフの全てのノードをシステマティックに展開・検査することを狙う方法である。つまり、グラフ全体を目的のノードがみつかるまで、目的のノードについて考慮せず徹底的に探索するのである。ノード探索に[[ヒューリスティクス]]([[:en:Heuristic (computer science)|heuristic]])は使われない。

[[アルゴリズム]]の観点からだと、ノードの展開により得られる子は[[キュー (コンピュータ)|キュー]]に追加される。典型的な実装の場合、未訪のノードは"open"と名づけられた(キューや[[連結リスト]]のような)コンテナに格納され、既訪のノードは"closed"と名づけられたコンテナに格納されることになる。

[[ファイル:MapGermanyGraph.svg|thumb|250px|ドイツの都市間の接続を示した例]]
[[ファイル:GermanyBFS.svg|thumb|250px|フランクフルトから幅優先検索を行った場合にできる木構造]]

== アルゴリズム ==

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

== 擬似コード ==
v は頂点。
 幅優先探索('''v''')
     v に訪問済みの印を付ける
     v をキューに追加
     while (キューに要素を含むなら)
         v ← キューから取り出す
         v を処理
         for each (v に接続していて かつ 未訪問の頂点 i)
             i に訪問済みの印を付ける
             i をキューに追加

== Common Lisp でのコード例 ==

 (defun bfs (node target)
   (do ((queue (list node)
 	      (append (cdr queue)
 		      (get (car queue) 'subnodes)))
        (ls nil (if (get (car queue) target)
 		   (cons (car queue) ls)
 		   ls)))
       ((null queue) (reverse ls))))

== アルゴリズムの特徴 ==

=== 空間計算量 ===

見つかったノードを全て記録する必要があるので、幅優先探索の空間計算量はO(|V| + |E|)となる。ここで|V|はグラフ内のノードの数で|E|は辺の数である。または、<math>O(B ^ M)</math>ということができる。ここでBは枝分かれの最大数でMは木の最長経路の長さである。この量の巨大さは幅優先探索が規模の大きな探索において非現実的な理由である。

=== 時間計算量 ===

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

=== 完全性 ===

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

=== 最適性 ===

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

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

== 関連項目 ==
* [[深さ優先探索]]

== 外部リンク ==
* [http://www.boost.org/libs/graph/doc/breadth_first_search.html C++ Boost Graph Library: Breadth-First Search]
* [http://www.kirupa.com/developer/actionscript/depth_breadth_search.htm Depth First and Breadth First Search: Explanation and Code]

{{デフォルトソート:ははゆうせんたんさく}}

[[Category:検索アルゴリズム]]
[[Category:アルゴリズム]]
[[Category:組合せ最適化]]
[[Category:数学に関する記事]]