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

概要

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

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

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

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

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