breadth first searchとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > breadth first searchの意味・解説 

幅優先探索

(breadth first search から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/06/20 02:29 UTC 版)

探索 > 幅優先探索
幅優先探索
Order in which the nodes get expanded

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

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

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

アルゴリズム

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



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「breadth first search」の関連用語

breadth first searchのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



breadth first searchのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの幅優先探索 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS