幅優先探索

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
探索 > 幅優先探索
幅優先探索
Order in which the nodes get expanded

探索順
一般的な情報
分類: 探索アルゴリズム
データ構造: グラフ
時間計算量: O(|E|)
空間計算量: O(|V|)
最適: はい
完全: はい
ドイツの都市間の接続を示した例
フランクフルトから幅優先検索を行った場合にできる木構造

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

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

アルゴリズム[編集]

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

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

擬似コード[編集]

v は頂点。

function 幅優先探索(v)
    v に訪問済みの印を付ける
    v をキューに追加
    while キューに要素を含む do
        v ← キューから取り出す
        v を処理
        for each v に接続している頂点 i do
            if i が未訪問 then
                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(|E|)である。ここで|E|はグラフ内の辺の数である。

空間計算量[編集]

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

完全性[編集]

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

最適性[編集]

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

幅優先探索の応用[編集]

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

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

関連項目[編集]

外部リンク[編集]