البحث بالعرض أولاً (Breadth-first search)

Written Explanation

The idea: rings around the start

Starting at node S, BFS does this:

1. Visit S.
2. Visit all neighbors of S (one edge away).
3. Visit all neighbors of those nodes that are new (two edges away).
4. Continue until no new nodes remain.

The data structure that gives this order is a queue: first in, first out. Nodes that are discovered first are processed first, so all nodes one edge away are handled before any node two edges away. The queue always contains a mix of at most two neighboring rings.

The algorithm

Queue<String> q = new ArrayDeque<>();
Set<String> visited = new HashSet<>();
q.add(start);
visited.add(start);
while (!q.isEmpty()) {
    String cur = q.poll();
    for (String next : g.getOrDefault(cur, List.of())) {
        if (visited.add(next)) q.add(next);
    }
}

Walk through it in words:

• Put the start node in the queue and mark it visited.
• Repeatedly take the node at the front (poll). It is the one we process now.
• For each neighbor of that node, if we have not seen it before, mark it visited and add it to the back of the queue.

Set.add returns true only when the element was not already in the set. So visited.add(next) does two jobs at once: it asks "is this new?" and records it. The documentation for ArrayDeque says it has no capacity limit and that poll returns null on an empty deque, which is why the loop tests isEmpty() first. It also prohibits null elements, which is fine here because node names are never null.

Why the visited set is not optional

Look at a graph with a loop: A is linked to B and B to A. Without a visited set, processing A adds B, processing B adds A, processing A adds B again, and so on. The queue never empties and the program never ends. This is the module's most common mistake: forgetting the visited set. Every node must be marked the moment it is added to the queue, so it can never be added twice.

Mark visited when you add to the queue, not when you remove. Marking at removal time still gives correct answers if you skip nodes already seen, but a node can sit in the queue several times first, wasting memory.

Why BFS finds shortest paths

Think of the rings. Every node one edge from S is added to the queue before any node two edges away, because nodes two edges away are discovered only while processing nodes one edge away. By induction the queue is always in order of distance: all distance-1 nodes, then distance-2 nodes, and so on. A node is added the first time any neighbor reaches it, and that neighbor came from the earlier ring. So the first discovery is the shortest.

This holds when every edge counts equally, as in "stops on a metro line", which is what "unweighted" means. BFS counts edges, not kilometers or minutes. A standard algorithms reference states it the same way: the path BFS finds to any node is a shortest path in terms of edge count.

To record distances, store them in a map as you discover nodes. The distance of a new node is its discoverer's distance plus one. Using the map's keys as the visited set saves a separate set:

Map<String, Integer> dist = new LinkedHashMap<>();
dist.put(start, 0);
q.add(start);
while (!q.isEmpty()) {
    String cur = q.poll();
    for (String next : g.getOrDefault(cur, List.of())) {
        if (!dist.containsKey(next)) {
            dist.put(next, dist.get(cur) + 1);
            q.add(next);
        }
    }
}

LinkedHashMap keeps insertion order, so printing it also shows the visiting order.

Cost: O(V + E)

Each node is added to the queue at most once, thanks to the visited set, so the loop body runs at most V times. Over the whole run, each node's neighbor list is scanned once, and the lists together hold E entries (or 2 E for undirected graphs). The total work is proportional to V + E, written O(V + E). This is the cost for an adjacency list. It is the same figure that standard references give for BFS: linear in the number of nodes plus edges. With a matrix, finding each node's neighbors would cost V per node, giving O(V x V) instead.

Unreachable nodes and unknown starts

BFS visits only the nodes reachable from the start. If the graph has separate pieces, the other pieces are never touched, and their nodes do not appear in visited or dist. That is how BFS tells you "unreachable": the node is simply absent.

If the start node is not in the graph at all, getOrDefault makes the loop harmless but the start node itself still goes into the result. Check g.containsKey(start) first when an unknown name should be an error or an empty answer.