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