1 歩ずつ動かす
- いま見ている頂点
- なし
- 見ている辺
- なし
- 訪れた順
- A
キュー (前から出て、最後に並ぶ)
- A
先頭から出る最後に並ぶ
出た頂点
- いま隣を見ている頂点
- 訪問済み (右上の数は訪れた順)
- まだの頂点
- いま見ている辺
隣が 2 つ以上あるときは、名前の順 (A、B、C…) に見ます。訪問済みにするのは、キューに入れるときです。
1 歩目 / 全 21 歩見た辺 0 本訪問済み 1 個キューの中 1 個
開始の頂点 A を訪問済みにして、キューに入れます。
いま動いている疑似コードの行
- 1開始の頂点 s を訪問済みにして、キューに入れる
- 2キューが空でないあいだ、次をくり返す
- 3u = キューの先頭から出す
- 4u の隣 v を、名前の順に 1 つずつ見る
- 5まだの v は、訪問済みにして並ばせる
- 6訪問済みの v は、何もしない
見本を変える
予想してみる
いまは 1 歩目です。
次にキューから出るのは、どの頂点でしょう。
今回わかること
- 開始の頂点から近い順に訪れる流れ
- キューを使うと近い順になる理由と、訪問済みの印が要る理由
前提
- キュー (先に入れた物から出る)
- グラフの頂点と辺
どんなたどり方か
幅優先探索 (BFS) は、開始の頂点から 1 本の辺で行ける頂点を全部訪れ、次に 2 本で行ける頂点、と近い順に広げていくたどり方です。
次に調べる頂点はキューに並ばせます。先に並んだ近い頂点から出るので、自然に近い順になります。一度訪れた頂点に印を付けておくと、輪のあるグラフでも同じ頂点を何度も調べません。
手順と具体例
- 1開始の頂点を訪問済みにして、キューに入れる
- 2キューの先頭から頂点を 1 つ出す
- 3その頂点の隣を見て、まだの頂点は訪問済みにしてキューの最後に入れる
- 4キューが空になるまで、2 と 3 をくり返す
| 出した頂点 | 新しく訪問済み | キュー (前から) |
|---|---|---|
| A | B、C | B、C |
| B | D、E | C、D、E |
| C | F、G | D、E、F、G |
| D | なし | E、F、G |
| E | なし | F、G |
| F | なし | G |
| G | なし | 空 |
見る回数と計算量
| 数えるもの | 回数 | 計算量 |
|---|---|---|
| キューから出す | 頂点 1 個につき 1 回 | O(V) |
| 辺を見る | 辺 1 本につき 2 回 (両側から) | O(E) |
| 合わせて | 頂点の数と辺の数の和に比例 | O(V + E) |
V は頂点の数、E は辺の数です。木の見本は頂点 7 個、辺 6 本なので、出すのが 7 回、辺を見るのが 12 回です。訪問済みかどうかは集合で持つので、1 回で分かります。リストで持って毎回探すと、この回数では収まりません。隣を名前の順に並べ替える手間は、図を追いやすくするための物で、ここでは数えていません。
使いどころ
向いているとき
- 辺の数で数えて、いちばん近い道を求めたいとき (迷路の最短の手数)
- ある頂点から行ける範囲を全部数えたいとき (つながっている塊の大きさ)
- 近い物から順に広げたいとき (知り合いの知り合い)
向いていないとき
- 辺ごとに長さが違うとき (ダイクストラ法を使う)
- 1 本の道を奥まで調べたいとき (深さ優先探索を使う)
コード
疑似コード
- 1開始の頂点 s を訪問済みにして、キューに入れる
- 2キューが空でないあいだ、次をくり返す
- 3u = キューの先頭から出す
- 4u の隣 v を、名前の順に 1 つずつ見る
- 5まだの v は、訪問済みにして並ばせる
- 6訪問済みの v は、何もしない
実際のコード
python実行可能
出力
▶ 実行ボタンを押すと結果がここに表示されます
Python と JavaScript は、書き換えて「実行」を押すと、その場で結果が出ます。Java は読むだけの欄です。
よくある疑問
- なぜキューから出すときではなく、入れるときに訪問済みにするのですか？
- 出すときに印を付けると、印が付く前に別の頂点からも同じ頂点を見つけ、キューに 2 度入れてしまいます。入れるときに付ければ、どの頂点も 1 回しか並びません。
- キューをスタックに変えると、どうなりますか？
- 最後に入れた頂点から出るので、1 本の道を奥へ進むたどり方になります。これは深さ優先探索の形です。近い順ではなくなります。
- つながっていない頂点も全部訪れたいときは？
- 全部の頂点を順に見て、まだ訪問済みでない頂点があれば、そこを開始の頂点にしてもう一度幅優先探索をします。何回やり直したかが、つながっている塊の数です。
