幅優先探索
幅優先探索（はばゆうせんたんさく、英: breadth first search）はグラフ理論(Graph theory)において木構造(tree 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|はグラフ内のノードの数である。または、 ということができる。Bは枝分かれの最大数で、Mは木の最長経路の長さ。指数関数故に、幅優先探索は大量の情報から探索する事に向かない根拠になる。
完全性
編集幅優先探索は完全である。つまり解が存在する場合はグラフの構造によらず、解をみつけることができる。しかしグラフが無限で探索対象の解が存在しない場合、幅優先探索は終了しない。
最適性
編集一般に幅優先探索は最適で、常に開始ノードと終了ノードの長さが最も少ない辺を返す。もしグラフが重みつきならば、最初のノードの隣のノードが最良のゴールとは限らないが、この問題は辺のコストを考慮に入れた均一コスト探索(Uniform cost search)で解決できる。
幅優先探索の応用
編集幅優先探索はグラフ理論における多くの問題を解くために使うことができる。以下は一例である。
- グラフ内の全ての連結成分をみつける。幅優先探索で到達するノードの集合は初期ノードを含む最大の連結成分である。
- 1つの連結成分内の全てのノードをみつける。
- 辺の重みなしグラフの最小全域木を求める。
- 辺の重みなしグラフの単一始点最短経路問題を解く。
- グラフが2部グラフ(Bipartite graph)かどうかテストする。もし幅優先探索の同じ段階のノード集合に存在するノードに合流する辺があるならば、グラフには奇数長の閉路が存在し2部グラフではない。
参照透過な関数型言語の場合
編集参照透過な関数型言語の場合は余再帰と遅延評価を使うと簡潔に書ける。下記は Scala の場合で、Scalaz の unfold が余再帰で、Stream が遅延リスト。
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) })
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を返す
Grid 描画
編集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()
幅優先による探索結果描画
編集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()