幅優先探索

ウィキペディア

幅優先探索

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2026/01/26 06:44 UTC 版)

探索 > 幅優先探索

幅優先探索
Order in which the nodes get expanded 探索順
一般的な情報
分類: 探索アルゴリズム データ構造: グラフ 時間計算量: $O(|E|)$ ドイツの都市間の接続を示した例 フランクフルトから幅優先検索を行った場合にできる木構造 幅優先探索（はばゆうせんたんさく、英: 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|はグラフ内のノードの数である。または、 $O(B^{M})$ということができる。Bは枝分かれの最大数で、Mは木の最長経路の長さ。指数関数故に、幅優先探索は大量の情報から探索する事に向かない根拠になる。 完全性 幅優先探索は完全である。つまり解が存在する場合はグラフの構造によらず、解をみつけることができる。しかしグラフが無限で探索対象の解が存在しない場合、幅優先探索は終了しない。 最適性 一般に幅優先探索は最適で、常に開始ノードと終了ノードの長さが最も少ない辺を返す。もしグラフが重みつきならば、最初のノードの隣のノードが最良のゴールとは限らないが、この問題は辺のコストを考慮に入れた均一コスト探索(Uniform cost search)で解決できる。 幅優先探索の応用 幅優先探索はグラフ理論における多くの問題を解くために使うことができる。以下は一例である。 グラフ内の全ての連結成分をみつける。幅優先探索で到達するノードの集合は初期ノードを含む最大の連結成分である。 1つの連結成分内の全てのノードをみつける。 辺の重みなしグラフの最小全域木を求める。 辺の重みなしグラフの単一始点最短経路問題を解く。 グラフが2部グラフ(Bipartite graph)かどうかテストする。もし幅優先探索の同じ段階のノード集合に存在するノードに合流する辺があるならば、グラフには奇数長の閉路が存在し2部グラフではない。 参照透過な関数型言語の場合 参照透過な関数型言語の場合は余再帰と遅延評価を使うと簡潔に書ける。下記はScalaの場合で、LazyListが遅延リストで、LazyList.unfoldが余再帰。 import scala.collection.immutable.Queue case class Tree[T](value: T, children: Seq[Tree[T]]) def breadthFirstSearch[T](root: Tree[T]): LazyList[T] = LazyList.unfold(Queue(root))(q => q.dequeueOption.map((tree, queue) => (tree.value, queue ++ tree.children))) 関連項目 深さ優先探索 外部リンク 『深さ優先探索と幅優先探索』 - 高校数学の美しい物語 C++ Boost Graph Library: Breadth-First Search Depth First and Breadth First Search: Explanation and Code

ウィキペディア小見出し辞書

幅優先探索

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/29 13:54 UTC 版)

「二分木」の記事における「幅優先探索」の解説

深さ優先探索と対照的に、未だに訪れていないノードを、根に近い方から探索する。

Weblio日本語例文用例辞書

「幅優先探索」の例文・使い方・用例・文例

• 幅優先探索という,人工知能における探索手法