BFS-Specific

What is this?

BFS explores in rings: everything one step away, then everything two steps away. That ordering is the whole value — the first time you reach a node, you have reached it in the fewest possible steps, so the level number is the shortest distance and no further checking is needed.

The two problems here push on that in different directions. One needs to traverse edges the wrong way while still remembering which way they pointed. The other needs not one shortest path but every shortest path, which BFS alone cannot give you.

💡 Fun fact: Word Ladder II is a good demonstration that BFS finds a shortest path but not all of them. The fix is to run BFS level by level, recording for each word every predecessor that reached it at that level — not just the first — and to delete visited words only at the end of a level rather than on discovery. Two words on the same level can legitimately both lead to a third; removing a word as soon as it is seen silently discards entire valid paths.

🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

---

The one-line idea: BFS gives shortest distances for free because of the order it visits things. To get more than one shortest path, record parents during the walk instead of just distances, and finish each level before marking anything as consumed.

---

1. Traverse against direction, remember direction

Reorder Routes to Make All Paths Lead to the City Zero has n cities and n − 1 directed roads that form a tree if direction is ignored. You must reverse the fewest roads so every city can reach city 0.

The trick is to store each edge twice: once forward with a cost of 1, once backward with a cost of 0.

adj = defaultdict(list)
for a, b in connections:
    adj[a].append((b, 1))     # a → b costs 1 to traverse "the wrong way" from 0
    adj[b].append((a, 0))     # b → a is free

Now walk outward from city 0 through the undirected tree and add up the costs. An edge costing 1 is one that points away from the city 0 — exactly the ones needing reversal. The graph structure lets you ignore direction while the weights preserve it.

2. Record parents, not just distances

For all shortest paths, the BFS state changes shape:

parents = defaultdict(set)       # word -> every predecessor that reached it first
current = {beginWord}
while current and endWord not in parents:
    next_level = defaultdict(set)
    for word in current:
        for nxt in neighbours(word):
            if nxt not in visited:            # not seen in an EARLIER level
                next_level[nxt].add(word)
    visited |= set(next_level)                # remove only after the level completes
    for w, ps in next_level.items():
        parents[w] |= ps
    current = set(next_level)

Then a backwards DFS from endWord through parents enumerates every shortest sequence. The two disciplines that make it correct: delete visited words after the level, not during it, and stop expanding once the target appears — anything found later is by definition longer.

---

3. A 30-second worked example (Reorder Routes)

Roads 0→1, 1→3, 2→3, 4→0, 4→5:

Every edge is examined once, and its cost was decided when the adjacency list was built — the traversal itself needs no direction logic at all.

---

4. Where you'll actually meet this

• Network reconfiguration. Reorienting links so every node can reach a gateway is the routes problem exactly.
• Word games and spell-checking. Transformation ladders underpin "did you mean" suggestions built on edit-distance graphs.
• Social distance. Degrees of separation, and enumerating all shortest connection chains between two people.
• Routing protocols. Hop-count shortest paths, and equal-cost multi-path routing — which is literally "all shortest paths".
• Puzzle and game solvers. Minimum-move solutions where every move costs the same.

---

5. Problems in this chapter

▶ Reorder Routes to Make All Paths Lead to the City Zero

Reverse the fewest directed roads so every city reaches city 0. Store each edge twice with costs 1 and 0, then sum the costs on a walk outward from 0.
Pattern: undirected traversal with direction encoded in weights. Target: O(V + E) time, O(V + E) space.

▶ Word Ladder II

Find every shortest transformation sequence between two words. Level-by-level BFS recording all parents, then a backwards DFS to enumerate the paths.
Pattern: BFS parent graph + backward DFS. Target: O(N · L²) for the BFS with wildcard bucketing, plus output size for the enumeration.

---

6. Common pitfalls 🚫

• Marking words visited on discovery in Word Ladder II. Two words at the same level may both reach a third; removing it early discards valid paths.
• Continuing BFS past the target's level. Any path found afterwards is longer and must not be included.
• Generating neighbours by scanning the whole word list. Use wildcard buckets (h*t) so neighbour lookup is O(L) rather than O(N·L).
• Forgetting endWord may be absent from the dictionary — then no sequence exists and the answer is empty.
• Adding direction logic to the traversal in Reorder Routes. Encode it in the edge weight when building the adjacency list and the walk stays trivial.
• Treating the road network as directed for the traversal itself. It is a tree only when direction is ignored; that is what guarantees each city is reached exactly once.
• Using DFS for shortest paths on an unweighted graph. It finds a path, not the shortest one.

---

7. Key takeaways

1. First arrival is shortest arrival. That is what BFS buys, and why no relaxation step is needed.
2. Encode awkward semantics in the edge weights so the traversal itself stays simple.
3. Record parents to recover paths — distances alone can never reconstruct them.
4. Finish the level before marking anything consumed, or you lose alternative shortest paths.
5. Stop at the target's level. Later discoveries are strictly longer.
6. Bucket neighbours by wildcard when the graph is implicit rather than given.
7. Why interviewers like it: everyone can write BFS. Whether you can bend it to produce all optimal answers, and whether you know where the direction information should live, is the differentiator.

Order: Reorder Routes to Make All Paths Lead to the City Zero → Word Ladder II.