🗺️ アルゴリズムクエスト
STAGE 6 ― キューと幅優先探索 ―
クリア 0 / 9
🧭 地図
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. 幅優先探索で、ある町に初めて書いた歩数が最少の歩数になる理由は?

Q3. 幅優先探索の計算量(町の数 V、道の数 E)は?