乗り換えの少ない行き方
地図アプリで駅Aから駅Fへ行く道を調べると、乗り換えの少ない行き方が出ます。道は何通りもあるのに、アプリはどう選んでいるのでしょう。
駅と線路を「点と線」で表したものが、グラフです。グラフの上で最短の道を探す手順があります。
このレッスンのゴール
メモ
幅優先探索を使って、グラフの上で最短の道の長さを求められる。
重要な言葉
| ことば | いみ |
|---|---|
| グラフ | 点と、点どうしをつなぐ線でできた図 |
| ノード | グラフの点で、駅や人にあたるもの |
| エッジ | ノードどうしをつなぐ線 |
| 隣接 | エッジで直接つながっていること |
| 幅優先探索 | 近いノードから順に、輪を広げて調べる探し方 |
学生が入力するセルは、このプレビューでは空白です。
グラフはノードとエッジでできている
駅がノード、駅と駅をつなぐ線路がエッジです。エッジでつながった二つのノードは、隣接していると言います。
Python では、ノードごとに、隣のノードのリストを持つ辞書で表せます。これを隣接リストと呼びます。
グラフを辞書で表す
# 駅ごとに、隣の駅のリストを持つ
graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D", "E"],
"D": ["B", "C", "F"],
"E": ["C", "F"],
"F": ["D", "E"],
}
print(graph["C"])
# "C" を "F" に変えて、隣の駅を確かめましょう
幅優先探索は輪を広げて調べる
池に石を投げると、波が輪になって広がります。幅優先探索も、出発点に近いノードから、輪を広げるように調べます。
調べる順番はキューで決めます。ノードを取り出し、まだ見ていない隣のノードを、キューの後ろに入れます。
例：Aから始める探索
| 取り出す駅 | 新しく入れる駅 | キューの中身 |
|---|---|---|
| A | B, C | B, C |
| B | D | C, D |
| C | E | D, E |
| D | F | E, F |
| E | なし | F |
| F | なし | 空 |
学生が入力するセルは、このプレビューでは空白です。
幅優先探索の訪問順を出す
docker exec jupyter python3 -c 'exec("graph = {\"A\": [\"B\", \"C\"], \"B\": [\"A\", \"D\"], \"C\": [\"A\", \"D\", \"E\"], \"D\": [\"B\", \"C\", \"F\"], \"E\": [\"C\", \"F\"], \"F\": [\"D\", \"E\"]}\nqueue = [\"A\"]\nseen = [\"A\"]\norder = []\nwhile len(queue) > 0:\n here = queue.pop(0)\n order.append(here)\n for next_stop in graph[here]:\n if next_stop not in seen:\n seen.append(next_stop)\n queue.append(next_stop)\nprint(\" \".join(order))")'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
見た駅を覚えておく理由
実行の結果は A B C D E F です。表と同じ順番で駅を調べています。
見た駅を seen に覚えておくのが大事です。覚えないと、AからBへ行って、またAへ戻るように、同じ駅を何度も回ってしまいます。
最短の道は、何本のエッジか
A から見ると、B と C は1本、D と E は2本、F は3本のエッジを通った先です。輪が広がるたびに、本数が1ずつ増えます。
幅優先探索は近い順に調べるので、初めて着いたときの本数が、最短です。乗り換えが少ない道が、これにあたります。
例：Aからの最短の本数
| 駅 | Aから何本か | 通る道の例 |
|---|---|---|
| A | 0 | A |
| B | 1 | A, B |
| D | 2 | A, B, D |
| F | 3 | A, B, D, F |
学生が入力するセルは、このプレビューでは空白です。
よくある間違い
注意
近いと思った駅から、一本の道をどこまでも進めばよいと考えがちです。それでは最短とは限りません。近いノードを順に全部調べるから、最初に着いたときの本数が最短だと言えます。