幅優先探索（BFS）
グラフを層ごとに調べます。次の頂点はキューで決まるので、いつも近い頂点から先に訪問します。
- O(V + E)
- メモリ O(V)
- キュー
V と E: 頂点の数と辺の数。O(V + E) は、どの頂点もどの辺も決まった回数だけ処理されるという意味です。
キュー: 先に入れたものが先に出ます。BFS はいつも一番長く待っている頂点を取り出します。
このページのほかの用語
- 頂点: グラフの点。ここでは文字の入った円で描いています。
- 辺: 2つの頂点を結ぶ線。ここではどちら向きにもたどれます。
- 隣の頂点: ある頂点と辺で結ばれた頂点。アルファベット順に調べます。
0 / 60 ステップ
試してみましょう: 2つの部分に分かれたグラフを選んでください。始点とつながっていない頂点には、最後までたどり着きません。
仕組み
BFS は始点をキューに入れます。そして、キューの先頭の頂点を取り出し、その新しい隣の頂点を末尾に加える、という作業を繰り返します。キューは来た順に処理するので、辺1本で届く頂点はすべて、辺2本で届く頂点より先に完了します。頂点の横の数字は始点からの距離、つまりそこへ着くのに必要な辺の最少本数です。
向いている場面
ステップ数で最短の道が必要なときに BFS を使います。パズルの最少手数、ネットワークの最少ホップ数、知り合いの知り合いまでの範囲にいる人などです。大きなグラフでは、1つの層をまるごと抱えるのでキューが長くなることがあります。