STAGE 6
キューと幅優先探索
近い順に広げる
🎯 ミッション
キューとスタックの違いと、幅優先探索で最短の歩数が求まる理由を説明できるようになろう。スタートから全部の町までの歩数を求め、確認クイズに全問正解すれば合格。
未達成

ねこ博士
ここからは「道を探す」問題だ。王国には町がいくつかあって、道でつながっている。町を点(頂点)、道を線(辺)として描いたものをグラフと呼ぶ。グラフといっても、折れ線グラフのグラフとは別物で、「つながり方の図」という意味だ。

うさ美
電車の路線図もグラフですね。駅が点で、線路が線。

ねこ博士
そう。今日の問題は、「スタートの町 S から、どの町へも、最少で何本の道を通れば行けるか」。道の長さはどれも同じとして、通る道の本数(歩数)だけを数える。

うさ美
S から1歩で行ける町は、S の隣の町。2歩で行ける町は、その隣の町の隣で、まだ行っていない町……。近いほうから順に広げていけばいいですね。

ねこ博士
その「近い順に」を正しく守るための道具がある。キュー(待ち行列)だ。お店の行列のように、先に並んだものから先に取り出す。First In First Out、略して FIFO と言う。

うさ美
スタックは後から積んだものを先に出す LIFO でした(『メモリのしくみクエスト』)。キューはその反対なんですね。

ねこ博士
そう。キューを使った手順はこうだ。これを幅優先探索(はばゆうせんたんさく、英語の頭文字で BFS)と呼ぶ。
① S に「0歩」と書いて、キューに入れる
② キューの先頭から町を1つ取り出す
③ その町の隣で、まだ歩数が書かれていない町に「取り出した町の歩数+1」と書き、キューの後ろに並べる
④ キューが空になるまで ②③ をくり返す

ねこ博士
なぜ、これで最少の歩数が求まるのか。キューの中の町の歩数は、どんな順に並んでいるかな。

うさ美
0歩の S を取り出したら、1歩の町が後ろに並ぶ。1歩の町を全部取り出し終わるまで、後ろに並ぶのは2歩の町だけ。だから、キューの中は歩数の小さい順に並んでいて、近い町から順に取り出されます。

ねこ博士
そう。だから、ある町に初めて歩数を書いた時点で、それより少ない歩数で来られる道は、もう全部調べ終わっている。初めて書いた歩数が、そのまま最少の歩数になるんだ。どの町へ、どの町から来たかを覚えておけば、ゴールから逆にたどって最短の道そのものも分かる。それぞれの町と道を1回ずつしか調べないので、計算量は、町の数を V、道の数を E として O(V+E) だ。

うさ美
キューの代わりにスタックを使ったらどうなりますか?

ねこ博士
後から入れた町を先に取り出すので、1つの道を行けるところまで深く進んでから、戻って別の道を試す動きになる。これを深さ優先探索(DFS)と呼ぶ。迷路の出口があるかどうかを調べるのには向いているけれど、最初に見つかった道が最短とは限らない。
キュー(先に入れたものから出す)→ 幅優先探索:近い順に広がる。歩数の最短が求まる
スタック(後に入れたものから出す)→ 深さ優先探索:1本の道を奥まで進む。最短とは限らない

うさ美
道の長さがばらばらだったら、幅優先探索では困りますね。1歩で行けても、その道がとても長いかもしれない。

ねこ博士
その通り。それが次のステージの問題だ。
確認クイズ
Q1. キューの性質として正しいのは?
正解! お店の行列と同じ。後に入れたものを先に出すのはスタック。
Q2. 幅優先探索で、ある町に初めて書いた歩数が最少の歩数になる理由は?
正解! キューのおかげで、k 歩の町を全部調べ終わってから k+1 歩の町に進む。だから初めて届いた歩数が最少。道の長さが同じ、は問題の前提で、理由そのものではない。
Q3. 幅優先探索の計算量(町の数 V、道の数 E)は?
正解! どの町もキューに入るのは1回、どの道も調べるのは(両端から)高々2回。だから町と道の数の和に比例する。