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