最小乗り換え問題とは？
地下鉄の路線図を思い浮かべてください。ある駅から別の駅へ行くとき、「通路（接続）に最低何回乗ればよいか？」を問うのが最小乗り換え（最小移動）問題です。
ポイントはすべての接続の長さが同じ（重みなし）であることです。すると「最小移動回数 = 最小の辺の数」となり、これはBFS（幅優先探索）でちょうど解けます。
なぜBFS？
BFSは出発駅から近い駅（レベル）から順に訪問します。
- •レベル0: 出発駅そのもの（移動0回）
- •レベル1: 通路1本でつながる駅（移動1回）
- •レベル2: そこからもう1回進んだ駅（移動2回）
同じレベルをすべて見てから次のレベルへ進むため、目的駅を最初にキューから取り出した時の距離がそのまま最小移動回数になります。DFSではこの最短性を保証できません。
動作原理
ステップ1. 隣接リストでグラフを構築します。通路は双方向なので、両駅に互いを追加します。
ステップ2. 距離配列 dist をすべて-1（未訪問）にし、出発駅だけ dist[s] = 0 にしてキューに入れます。
ステップ3. キューが空になるまで駅を1つ取り出します。それが目的駅なら距離をすぐに返します。
ステップ4. 取り出した駅の隣接のうち dist == -1（未訪問）のものに dist[next] = dist[cur] + 1 を記録してキューに入れます。
訪問表示（距離記録）はキューに入れる時に行い、同じ駅が2回入らないようにします。
グラフ探索の3つの分岐
各隣接を見るとき、次を区別します。
- •訪問済みの駅 —
dist != -1→ スキップ（重複・無限ループ防止） - •つながっていない駅 — そもそも隣接リストに無いので自然に除外
- •未訪問の駅 —
dist == -1→ 距離+1を記録してキューに追加
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 時間 | O(V + E) |
| 空間 | O(V) |
すべての駅(V)と通路(E)を最大1回だけ見るのでO(V + E)です。
よくあるミス
- •訪問表示を取り出す時にすると、同じ駅がキューに何度も入り非効率・誤答になります。入れる時に表示しましょう。
- •重みが異なるグラフ（通路ごとに時間が違う）にはBFSではなくダイクストラが必要です。
- •到達不可能な場合（-1）の返却を忘れないでください。
AlgoNoteで直接確認しましょう
キューがレベル順に埋まり、距離配列が1つずつ伸び、目的駅を取り出した瞬間に答えが確定する過程を、AlgoNoteで1ステップずつ見られます。