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

{{出典の明記|date=2015年10月9日 (金) 06:19 (UTC)}}
{{pathnav|探索|frame=1}}
{| 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.svg|none|300px|Order in which the nodes get expanded]]<br />探索順
|-
! style="background-color: #ffc0c0; border:1px #aaa solid;" | '''一般的な情報'''
|-
|
{| style="border: 0;" 
|-
| ''分類'': || [[探索|探索アルゴリズム]]
|-
| ''データ構造'': || [[グラフ (データ構造)|グラフ]]
|-
| ''時間計算量'': || <math>O(|E|)</math>
|-
| ''空間計算量'': || <math>O(|V|)</math>
|-
| ''最適'': || はい
|-
| ''完全'': || はい
|-
|}
|-
|}
[[ファイル:MapGermanyGraph.svg|thumb|250px|ドイツの都市間の接続を示した例]]
[[ファイル:GermanyBFS.svg|thumb|250px|フランクフルトから幅優先検索を行った場合にできる木構造]]

'''幅優先探索'''（はばゆうせんたんさく、{{lang-en-short|breadth first search}}）は[[グラフ理論]]([[:en:graph theory|Graph theory]])において[[木構造 (データ構造)|木構造]]([[:en:tree structure|tree structure]])や[[グラフ (データ構造)|グラフ]]([[:en:graph (data structure)|graph]])の[[探索的研究|探索]]に用いられる[[アルゴリズム]]。アルゴリズムは根ノードで始まり隣接した全てのノードを探索する。それからこれらの最も近いノードのそれぞれに対して同様のことを繰り返して探索対象ノードをみつける。「'''横型探索'''」とも言われる。

幅優先探索は解を探すために、グラフの全てのノードを網羅的に展開・検査する。[[最良優先探索]]とは異なり、ノード探索に[[ヒューリスティクス]]を使わずに、グラフ全体を目的のノードがみつかるまで、目的のノードに接近しているかどうかなどは考慮せず探索する。

== アルゴリズム ==
# 根ノードを空のキューに加える。
# ノードをキューの先頭から取り出し、以下の処理を行う。
#* ノードが探索対象であれば、探索をやめ結果を返す。
#* そうでない場合、ノードの子で未探索のものを全てキューに追加する。
# もしキューが空ならば、グラフ内の全てのノードに対して処理が行われたので、探索をやめ"not found"と結果を返す。
# 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|はグラフ内のノードの数である。または、<math>O(B ^ M)</math>ということができる。Bは枝分かれの最大数で、Mは木の最長経路の長さ。指数関数故に、幅優先探索は大量の情報から探索する事に向かない根拠になる。

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

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

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

== 参照透過な関数型言語の場合 ==
[[参照透過性|参照透過]]な[[関数型言語]]の場合は余再帰と[[遅延評価]]を使うと簡潔に書ける。下記は [[Scala]] の場合で、Scalaz の unfold が余再帰で、Stream が遅延リスト。
<syntaxhighlight lang="scala">
import scala.collection.immutable.Queue
import scalaz.Scalaz.unfold

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

def breadthFirstSearch[T](root: Tree[T]): Stream[T] =
  unfold(Queue(root))(_.dequeueOption.map { case (tree, queue) => (tree.value, queue ++ tree.children) })
</syntaxhighlight>

== Pythonによる幅優先探索アルゴリズムの実装 ==
<syntaxhighlight lang="python">
 import networkx as nx
 import collections 

 # グラフGの最小全域木Tを返す関数
 def bfs(G):
     V = [ v for v in G.nodes() ]
     Q = collections.deque([V[0]])    
     explored = { v: False for v in G.nodes() } 
     explored[V[0]] = True
     T_edges = [] # Tに含まれる辺に対応するtupleを記録するlist
     while len(Q) != 0:
         v = Q.popleft()        
         unexplored_neighbors = [ i for i in G.neighbors(v) if not explored[i] ]
         for i in unexplored_neighbors:
              Q.append(i)
              T_edges += [ (v, i) ] # iに初めて到達した場合に限り辺をlistに加える
              explored[i] = True
     return G.edge_subgraph(T_edges).copy() # Gの部分グラフとしてTを返す
</syntaxhighlight>

=== Grid 描画 ===
<syntaxhighlight lang="python">
G = nx.grid_2d_graph(4,3)
p = { v: v for v in G.nodes() }
nx.draw_networkx(G, pos=p, node_color='lightgray', node_size=1300, with_labels=True)
plt.axis('off')
plt.show()
</syntaxhighlight>

=== 幅優先による探索結果描画 ===
<syntaxhighlight lang="python">
p = { v: v for v in G.nodes() }
V = [ v for v in G.nodes() ]
bfst = bfs(G)
DG = nx.DiGraph()
DG.add_edges_from(bfst)
nx.draw_networkx(DG, edgelist=bfst, pos=p, node_color='lightgray', node_size=1500, with_labels=True)
plt.axis('off')
plt.show()
</syntaxhighlight>

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

== 外部リンク ==
* {{高校数学の美しい物語|1247|深さ優先探索と幅優先探索}}
* [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]

{{アルゴリズム}}
{{DEFAULTSORT:ははゆうせんたんさく}}
[[Category:検索アルゴリズム]]
[[Category:アルゴリズム]]
[[Category:組合せ最適化]]
[[Category:数学に関する記事]]