Breadth-first search

ウィキペディア

幅優先探索

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

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方） 出典検索?: "幅優先探索" – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2015年10月）

探索 > 幅優先探索

幅優先探索
Order in which the nodes get expanded 探索順
一般的な情報
分類: 探索アルゴリズム データ構造: グラフ 時間計算量: ${\displaystyle 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|はグラフ内のノードの数である。または、${\displaystyle O(B^{M})}$ 急上昇のことば 国際通商裁判所 UEFAカンファレンスリーグ 武蔵野東高等専修学校 連続イニング無得点 唆され 英和和英テキスト翻訳 >> Weblio翻訳 英語⇒日本語日本語⇒英語    >> 「Breadth-first search」を含む用語の索引  Breadth-first searchのページへのリンク 辞書ショートカット 1 ウィキペディア カテゴリ一覧 全て ＋ ビジネス ＋ 業界用語 ＋ コンピュータ ＋ 電車 ＋ 自動車・バイク ＋ 船 ＋ 工学 ＋ 建築・不動産 ＋ 学問 ＋ 文化 ＋ 生活 ＋ ヘルスケア ＋ 趣味 ＋ スポーツ ＋ 生物 ＋ 食品 ＋ 人名 ＋ 方言 ＋ 辞書・百科事典 すべての辞書の索引 あいうえお かきくけこ さしすせそ たちつてと なにぬねの はひふへほ まみむめも やゆよ らりるれろ わをん がぎぐげご ざじずぜぞ だぢづでど ばびぶべぼ ぱぴぷぺぽ ＡＢＣＤＥ ＦＧＨＩＪ ＫＬＭＮＯ ＰＱＲＳＴ ＵＶＷＸＹ Ｚ １２３４５ ６７８９０ 記号 Weblioのサービス 英会話コラム Weblio英会話 英語の質問箱 語彙力診断 スピーキングテスト 「Breadth-first search」の関連用語 1 BFS 百科事典 36% ||||| 2 Perfect elimination とその効率的な導出 ウィキペディア小見出し辞書 30% ||||| 3 最良優先探索 百科事典 14% ||||| 4 幅優先探索 百科事典 12% ||||| 5 弦グラフ 百科事典 6% ||||| 6 ウッドブリッジ (ニュージャージー州) 百科事典 2% ||||| Breadth-first searchのお隣キーワード Bravo☆Bravo Brawlhalla Bray me Brazil R/S Brazzers Bread & Butter Breadth-first search Break Down Break Down/Break your name/Summer Revolution Break a leg! Break a spell Break and Cross the Walls I Break and Cross the Walls II 検索ランキング 英和和英テキスト翻訳 >> Weblio翻訳     英語⇒日本語 日本語⇒英語     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の元に提供されております。 ビジネス｜業界用語｜コンピュータ｜電車｜自動車・バイク｜船｜工学｜建築・不動産｜学問 文化｜生活｜ヘルスケア｜趣味｜スポーツ｜生物｜食品｜人名｜方言｜辞書・百科事典 ご利用にあたって ・Weblio辞書とは ・検索の仕方 ・ヘルプ ・利用規約 ・プライバシーポリシー ・サイトマップ 便利な機能 ・ウェブリオのアプリ ・画像から探す お問合せ・ご要望 ・お問い合わせ 会社概要 ・公式企業ページ ・会社情報 ・採用情報 ウェブリオのサービス ・Weblio 辞書 ・類語・対義語辞典 ・英和辞典・和英辞典 ・Weblio翻訳 ・日中中日辞典 ・日韓韓日辞典 ・フランス語辞典 ・インドネシア語辞典 ・タイ語辞典 ・ベトナム語辞典 ・古語辞典 ©2025 GRAS Group, Inc.RSS      ログイン ※半角英数字、6文字以上、32文字以内で入力してください ログイン パスワードを忘れた方はこちらから 別サービスのアカウントで登録・ログイン アカウントをお持ちでない方 新規会員登録（無料）