BFS-Specific Algorithms

What is this?

Drop a stone in a still pond and watch the ripples spread — first the ring one step out, then two steps, then three, never skipping ahead. Breadth-first search explores a graph exactly like that ripple, and because of it, the very first time the ripple touches a spot, it got there by the fewest possible steps. That makes BFS the go-to tool for "what's the smallest number of moves?" questions — even when the "map" is hidden, like word-change puzzles or a knight hopping around a chessboard.

💡 Fun fact: the "six degrees of separation" idea — that any two people on Earth are linked by a short chain of acquaintances — is really a breadth-first-search claim. When Facebook measured it in 2016 across 1.6 billion users, the average chain length was about 3.5 hops, even shorter than the legendary six.

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

The one-line idea: in an unweighted graph — every edge costs the same — the shortest path is found not by clever math but by fanning outward in rings of equal distance. That's Breadth-First Search: a queue, a visited set, and the guarantee that the first time you reach a node, you reached it by the fewest edges. Learn to see implicit graphs (words, board squares, configurations as nodes) and BFS turns a whole family of "minimum steps to…" problems into one reflex.

1. What "BFS for shortest path" really means

Picture dropping a stone into still water. The ripple reaches everything one unit away, then everything two units away, then three — never skipping a ring, never reaching a far point before a near one. BFS is that ripple over a graph. Starting from a source, it visits all nodes at distance 0, then all at distance 1, then distance 2, and so on:

Two pieces of machinery make the ripple work:

 QUEUE (FIFO)   — holds the current frontier; dequeue near before far,
                  so nodes come out in non-decreasing distance order.
 VISITED set    — mark a node the INSTANT you enqueue it, so it never
                  enters the queue twice and its distance is locked in.

Why first-reach = shortest: when a node leaves the queue, every node still ahead of it was enqueued no earlier, hence sits at the same distance or farther. So the distance recorded on first reach can never be beaten by a later route. This holds only when every edge has the same cost — the moment edges carry different weights, you need Dijkstra (or 0-1 BFS for the 0/1 special case), not plain BFS.

2. The implicit-graph leap

The problems in this chapter never hand you an adjacency list. The graph is implicit: nodes are states, and edges are legal single steps between them.

 explicit graph:  given nodes + edges, traverse them.
 implicit graph:  given a state and a rule for "next states",
                  GENERATE neighbours on the fly during BFS.

• A word is a node; its neighbours are all words differing by one letter.
• A board square (x, y) is a node; its neighbours are the squares one legal move away.
• A configuration (puzzle layout, migration state) is a node; its neighbours are the results of one legal change.

The skill is to recognize the hidden graph and write a neighbours(state) function — then drop it into the same BFS skeleton every time.

3. Where you'll actually meet this

BFS-for-shortest-path is a production primitive, not just a contest trick:

• Distributed systems. Minimum-hop reachability between services; crawling a dependency or service graph by depth (level k before level k+1); bounded state-space search to find the fewest safe transitions from one valid configuration to another.
• Networking. Fewest-hops routing in a mesh or regular topology; flood-style discovery that expands ring by ring.
• Games & robotics. Minimum-turns pathfinding for units with fixed move-sets; reachability ranges; planning the shortest sequence of discrete actions to a goal pose.
• Search & crawling. Breadth-limited web crawls; "pages within k links" queries; shortest connection paths in social graphs ("degrees of separation").
• Bioinformatics. Shortest mutation paths between sequences differing by one base, each intermediate valid.

If a problem says minimum moves / fewest steps / shortest transformation / nearest of several targets over uniform-cost transitions — this chapter's toolkit applies.

4. The BFS toolkit

1. Queue + visited-on-enqueue. The non-negotiable core. Mark a node visited the moment it enters the queue, never when it leaves — otherwise duplicates pile up and distances can inflate.
2. Level-by-level processing. Snapshot the queue size at the top of each round and drain exactly that many before incrementing the distance. This gives clean "ring number = distance" bookkeeping and is handy when you need all nodes at a depth.
3. Implicit graphs. States as nodes, a neighbours(state) generator as edges. Recognizing the hidden graph is most of the battle.
4. Bidirectional BFS. Search from both the start and the goal, always expanding the smaller frontier, and stop when the two frontiers meet. Roughly turns b^d work into 2·b^(d/2) — a large win on big, bushy graphs. Costs you a second visited set and meeting-point bookkeeping.
5. Symmetry & bounding. When the state space is symmetric (knight moves under reflection) or infinite, fold equivalent states together and clamp exploration to a finite region so BFS terminates and stays tight.
6. Multi-source BFS (forward reference). Seed the queue with many sources at distance 0 to compute, for every node, its distance to the nearest source in one sweep — covered in its own chapter.

5. A 30-second worked example

Fewest knight moves from (0,0) to (2,2) on an infinite board — fold to the first quadrant, then ripple outward:

The point isn't the exact number — it's that BFS computes it without you reasoning about parity at all. The queue + visited + first-reach machinery encodes every awkward fact (like "an orthogonally adjacent square costs 3 moves") for free. One ripple, and you read the answer off the ring where the target first appears.

6. Problems in this chapter

▶ Word Ladder

Find the shortest chain from a start word to a goal word, changing one letter per step with every intermediate a valid dictionary word (think: shortest "repair path" between valid CLI commands). Model words as nodes, one-letter-apart words as edges, and BFS the implicit graph. Speed neighbour-finding with wildcard-pattern buckets (h*t), and reach for bidirectional BFS on big lists.
Pattern: implicit-graph BFS + pattern-bucket adjacency. Target: O(N · L²) time, O(N · L²) space.

▶ Minimum Knight Moves

Fewest L-shaped knight moves from the origin to a target on an infinite board (think: minimum-turns scout pathing in a strategy game). BFS over (x, y) states; fold four quadrants into one via abs() and clamp the explored region so BFS stays finite and tight. Note A* as the escalation for far targets.
Pattern: state-space BFS + symmetry pruning. Target: O(R²) time/space, R = |x|+|y|.

7. Common pitfalls 🚫

• Marking visited at dequeue instead of enqueue. If you only mark a node when you pop it, the same node can be queued many times before its turn — bloating the frontier, wasting work, and in level-counting variants producing wrong distances. Mark the instant you enqueue.
• Using DFS for shortest unweighted path. DFS gives you a path, not the shortest — it can dive deep down a long route and "find" the goal far past where a short route existed. Uniform cost ⇒ BFS.
• Forgetting the implicit graph is implicit. Don't try to materialize all edges up front (e.g. comparing every pair of words). Generate neighbours on the fly inside BFS.
• Applying plain BFS to weighted edges. First-reach = shortest holds only for equal-cost edges. Different weights ⇒ Dijkstra; weights in {0,1} ⇒ 0-1 BFS with a deque.
• No bound on an infinite/huge space. Without a visited set and a region clamp (or symmetry fold), BFS over an unbounded board never terminates.
• Off-by-one in step counting. Decide up front whether the count includes the start node (Word Ladder counts it; Knight Moves counts jumps, so the start is 0).

8. Key takeaways

1. BFS = shortest path in unweighted graphs, found by expanding in rings of equal distance from the source.
2. First reach wins — because nodes leave the queue in non-decreasing distance order, the distance recorded on first arrival can't be beaten. This depends on uniform edge cost.
3. Queue + visited-on-enqueue is the whole engine; getting the visited timing right is the difference between correct and subtly wrong.
4. See the implicit graph. Words, board squares, and configurations are nodes; legal single steps are edges. Write neighbours(state) and reuse the same skeleton.
5. Escalate deliberately: bidirectional BFS for big bushy graphs, symmetry folds and region clamps for infinite/symmetric spaces, A* when goal-directed search pays off, multi-source BFS (next chapter) for nearest-of-many.
6. The same ripple powers real systems — min-hop routing, depth-bounded crawls, bounded state-space migration search — which is why interviewers lean so hard on this family.