What Is the Minimum Transfer Problem?
Picture a subway map. When traveling from one station to another, "what is the minimum number of corridors (connections) I must take?" — that is the minimum transfer (minimum moves) problem.
The key is that every connection has the same length (no weights). That means "minimum moves = minimum number of edges," which is solved exactly by BFS (Breadth-First Search).
Why BFS?
BFS visits stations from the start in order of nearest first (by level).
- •Level 0: the start station itself (0 moves)
- •Level 1: stations one corridor away (1 move)
- •Level 2: stations one more hop out (2 moves)
Because it finishes an entire level before moving on, the distance at the moment the destination is first dequeued is the minimum number of moves. DFS cannot guarantee this shortest property.
How It Works
Step 1. Build the graph with an adjacency list. Corridors are bidirectional, so add each station to the other's list.
Step 2. Set the distance array dist to -1 (unvisited) everywhere, set only the start to dist[s] = 0, and enqueue it.
Step 3. While the queue is not empty, dequeue one station. If it is the destination, return its distance immediately.
Step 4. For each neighbor with dist == -1 (not yet visited), record dist[next] = dist[cur] + 1 and enqueue it.
Mark visited (record distance) at enqueue time so the same station never enters the queue twice.
Three Branches in Graph Traversal
When inspecting each neighbor, distinguish:
- •Already visited —
dist != -1→ skip (prevents duplicates and infinite loops) - •Not connected — simply absent from the neighbor list, so excluded naturally
- •Unvisited —
dist == -1→ record distance + 1, then enqueue
Time and Space Complexity
| Complexity | |
|---|---|
| Time | O(V + E) |
| Space | O(V) |
Each station (V) and corridor (E) is examined at most once, giving O(V + E).
Common Mistakes
- •Marking visited at dequeue time lets the same station enter the queue multiple times — inefficient and buggy. Mark it at enqueue time.
- •For weighted graphs (different time per corridor), you need Dijkstra, not BFS.
- •Don't forget to return -1 for the unreachable case.
See It in Action on AlgoNote
Watch the queue fill up level by level, the distance array grow by one each step, and the answer lock in the instant the destination is dequeued — step by step on AlgoNote.