幅優先探索(BFS)

幅優先探索とは

幅優先探索(Breadth First Search: BFS)とは、始点 \(s\) から \(k+1\) の距離にある頂点を発見する前に、距離 \(k\) の頂点を全て発見するアルゴリズムである。始点から各頂点までの最短距離を順番に求めることができる。

【出典】
渡部有隆, Ozy, 秋葉拓哉他「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」282〜286頁