Demo: metro route finder with BFS

Written Explanation

Step 1: the map

Here is our metro, as one track per line in the form StationA-StationB:

Airport-Center
Center-Market
Market-Harbor
Harbor-Park
Park-Center
Stadium-Center
Stadium-University
University-Library
Island-Dock

Two things are worth noticing before we code. Center is the busy hub: it connects to Airport, Market, Park, and Stadium. Center, Market, Harbor, and Park form a loop. And Island and Dock are connected to each other but not to the rest of the map, so a rider cannot go from Airport to Dock.

We reuse edge from earlier lessons to add both directions of each track:

static Map<String, List<String>> g = new HashMap<>();

static void edge(String a, String b) {
    g.computeIfAbsent(a, k -> new ArrayList<>()).add(b);
    g.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
}

To load the lines, split each at the dash and call edge:

for (String line : lines) {
    String[] p = line.split("-");
    edge(p[0], p[1]);
}

(Station names with a dash inside them would break this format. Our names have none.)

Step 2: a first BFS that only visits

Start with plain BFS from one station, printing the order, exactly as in Lesson 3. On this map it visits Center's neighbors first and then works outward. The visited set is what keeps the loop Center, Market, Harbor, Park from running forever.

Step 3: the planned mistake

To see why the visited set matters, here is BFS without it, on the smallest possible loop: A and B linked to each other. I cap the loop at 8 steps so the demo ends instead of hanging your terminal.

Map<String, List<String>> g = new HashMap<>();
g.put("A", List.of("B")); g.put("B", List.of("A"));
Queue<String> q = new ArrayDeque<>();
q.add("A");
int steps = 0;
while (!q.isEmpty() && steps < 8) {
    String cur = q.poll();
    System.out.println("visit " + cur);
    for (String n : g.get(cur)) q.add(n);
    steps++;
}
System.out.println("stopped by step limit, queue size " + q.size());

Output:

visit A
visit B
visit A
visit B
visit A
visit B
visit A
visit B
stopped by step limit, queue size 1

A and B keep adding each other, so the queue is never empty. Without the steps < 8 guard the loop would never end. Real programs show this as a process stuck at full speed on one CPU core, and in some cases with growing memory use. The fix is the visited set, marking nodes when they are added to the queue.

Step 4: remember where we came from

BFS finds the nodes, but we want the route. The trick is to remember, for each station we discover, which station discovered it. This is the "came from" map: Map<String, String> from a station to its predecessor.

The map doubles as the visited structure: a station is visited exactly when it is a key. The start station has no predecessor, so we store null for it. (A HashMap accepts null values, so this is legal.) When BFS reaches the goal, we start at the goal and follow cameFrom back until we reach the start, collecting stations, then reverse the list.

static List<String> findRoute(String start, String goal) {
    if (!g.containsKey(start) || !g.containsKey(goal)) return List.of();
    Map<String, String> cameFrom = new HashMap<>();
    Queue<String> q = new ArrayDeque<>();
    q.add(start);
    cameFrom.put(start, null);
    while (!q.isEmpty()) {
        String cur = q.poll();
        if (cur.equals(goal)) break;
        for (String next : g.get(cur)) {
            if (!cameFrom.containsKey(next)) {
                cameFrom.put(next, cur);
                q.add(next);
            }
        }
    }
    if (!cameFrom.containsKey(goal)) return List.of();
    List<String> route = new ArrayList<>();
    for (String s = goal; s != null; s = cameFrom.get(s)) route.add(s);
    Collections.reverse(route);
    return route;
}

Read it in four parts:

1. Guard. If either station is not on the map, return an empty list right away.
2. Search. The BFS loop. Stopping early with break when the goal is taken from the queue is safe, because BFS has already recorded the shortest way to every station closer than or equal to the goal.
3. Not found. If the goal never became a key of cameFrom, it was unreachable, so return an empty list.
4. Rebuild. Walk from the goal to the start with cameFrom.get(s). The walk ends when s becomes null, which only the start's entry contains. Reverse to get start-to-goal order.

An empty list is the signal for "no route". The caller decides what to print. We chose an empty list over an exception because an unreachable station is a normal answer to a normal question, not a program error.

Step 5: print the answer

static void show(String a, String b) {
    List<String> r = findRoute(a, b);
    if (r.isEmpty()) System.out.println(a + " -> " + b + ": no route");
    else System.out.println(a + " -> " + b + ": " + String.join(" > ", r)
        + " (" + (r.size() - 1) + " stops)");
}

A route with n stations has n - 1 moves. When we say "stops" here, we count the moves, that is edges, as in the earlier lessons. The start-equals-goal case gives a one-station route and 0 stops.

Step 6: loading from a file

For the lab, the map comes from a text file. With Files.readAllLines it is a few lines (the path is up to you, and a relative path depends on the folder you run the program from):

static void load(Path file) throws IOException {
    for (String line : Files.readAllLines(file)) {
        if (line.isBlank()) continue;
        String[] p = line.trim().split("-");
        edge(p[0], p[1]);
    }
}

I tested this on a temporary file containing A-B, B-C, a blank line, and C-D; it built {A=[B], B=[A, C], C=[B, D], D=[C]} and skipped the blank line. It requires import java.nio.file.*; and import java.io.IOException;. A malformed line with no dash would throw an ArrayIndexOutOfBoundsException at p[1]. A production loader would check p.length first, and that check is a good addition for the lab.