幅優先探索 【BFS】 Breadth-First Search / 横型探索

概要

幅優先探索（BFS）とは、グラフや木構造を探索するためのアルゴリズムの一つで、探索を開始する頂点から近い順に探索する方式。

グラフや木はあるノードから複数のノードへ経路が伸びている場合があり、すべてのノードを探索したい場合にどのような順番で辿っていくかについていくつかの戦略が考えられる。

幅優先探索は探索を開始する頂点からの距離（深さ）が等しくなるように進んでいく方式で、出発点の隣接ノード（距離1）をすべて調べ、隣接ノードの隣接ノード（距離2）をすべて調べ、そのまた隣接ノード（距離3）を…という手順を終了まで繰り返す。

最初（最も過去）に追加された候補を優先的に探索するFIFO（First-In First-Out）方式で次に進むノードを決定するため、探索候補ノードの記録にキュー（queue）というデータ構造が適している。

もう一つの有力な探索アルゴリズムとして、それ以上先に進めない行き止まりのノードに出くわすまで経路を戻らずに隣接ノードを進んでいく方式があり、「深さ優先探索」（DFS：Depth-First Search）と呼ばれる。

(2021.5.10更新)

他の辞典による解説 （外部サイト）

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。
ホーム画面への追加方法
1.ブラウザの 共有ボタンのアイコン 共有ボタンをタップ
2.メニューの「ホーム画面に追加」をタップ
閉じる