Graph BFS

Reader guide and study workflow · Complete course map

Build the state graph before naming the search

Suppose a machine changes one letter per action and every resulting word must be in an allowed dictionary. From cold it can reach cord, then card, then ward. What would a direct solver do? Enumerate action sequences until one ends at the target. Without remembering states, cold→cord→cold can expand forever. With depth-first search and one permanent visited set, the first route to a word might also be longer than a route discovered later.

Instead process all zero-action states, then all one-action states, then all two-action states. A FIFO queue implements that order. When a word is first enqueued from distance d, it receives distance d+1; any shorter predecessor would have been processed earlier. Marking it now prevents many same-layer parents from scheduling it repeatedly. This proof depends on every modeled edge having the same cost.

Draw a counterexample to that assumption: S→T costs 8, S→U costs 1, U→T costs 1. Fewest edges chooses the direct route, but least cost chooses two edges. FIFO order alone no longer establishes the desired optimum. Naming a queue is not a substitute for defining the quantity being minimized.

Measure the answer in the requested units

The chain cold→cord→card→ward has three changes and four words. Minimum Mutation reports changes; Word Ladder reports words. A one-cell open grid likewise contains one cell but needs zero moves. Write distance at start = ... with its unit before writing a loop. An invalid initial state cannot become valid merely because it equals the destination.

For a board with snakes and ladders, one edge is one die roll followed by at most one forced jump. The die landing is an intermediate detail, not the state to mark visited. If square 2 jumps to 8 and 8 has another jump to 9, a single roll to 2 ends at 8 under this contract. Automatically following both jumps solves a different problem.

Replace repeated searches with one simultaneous frontier

If two sources spread simultaneously, running a separate search from each repeats work. Initialize all sources at distance zero: each newly reached cell gets the minimum distance from any source. On a row [rotten,fresh,fresh,fresh,rotten], the three fresh cells receive distances [1,2,1], so completion takes 2 minutes, not their sum. An unreachable fresh cell makes completion impossible even if other cells finish. This derives multi-source BFS directly from the quantity we need.

Prerequisites and readiness

Know a FIFO queue, marking on enqueue, and the difference between vertex count and edge count. Be able to define a state and enumerate exactly the legal one-step transitions before coding a shortest-path loop.

Reasoning workshop: make one queue edge equal one unit of time

Distance is a modeling choice

Word Ladder counts words: hit->hot->dot->dog->cog has answer 5. Minimum Mutation counts changes, so the analogous four-edge path has answer 4. Shortest Path in Binary Matrix counts cells and starts at 1, while Snakes and Ladders starts at zero die rolls. No universal initialization is correct for all four. Write the units next to the initial distance.

The FIFO proof has two halves. Soundness: every generated transition is legal. Minimality: a newly discovered vertex at distance d+1 comes from layer d, and all possible shorter predecessor layers have already been processed. A fast queue cannot rescue an incorrect neighbor function.

Mark on discovery; freeze layer boundaries

When two vertices in the same layer both reach the same neighbor, marking on enqueue lets the first claim it. Marking only on dequeue can schedule it repeatedly. Capture the current queue length before processing a layer: appended children belong to the next layer. During the loop the queue can contain both layers; the single-distance invariant applies to the layer snapshot, not every instant of the queue's life.

For oranges [2,1,1,1,2], sources occupy positions 0 and 4 at minute zero. At minute one positions 1 and 3 rot; at minute two position 2 rots. It is one simultaneous process. With [2,0,1], the fresh orange is disconnected and the answer is -1. With no fresh oranges, the answer is 0 even if there are no sources.

Indexing rules are part of the graph

On a 3x3 Snakes and Ladders board, the bottom row is labels 1,2,3 from left to right, the middle row is 6,5,4, and the top row is 7,8,9. Compute the row from the bottom before applying parity. A die landing plus its one mandatory jump is one edge. Do not chain a second jump written on the destination, and do not mark only the pre-jump landing as the visited state.

For the binary matrix 01 / 10, the diagonal move is legal and the answer is 2. Borrowing four-direction neighbors from Number of Islands would incorrectly declare it unreachable. A more restrictive corner-cutting rule would also change the specified graph and is not part of this problem.

An adjacency index has construction costs

Word Ladder's wildcard buckets avoid comparing every pair of words. But each wildcard key is a newly built string, not a constant-size integer. With N words and byte length L, building NL keys can cost O(NL^2) time and key bytes. Clearing a bucket after its first full expansion prevents repeatedly scanning the same group; it does not eliminate string-construction cost. Mutation has fixed length eight and four allowed bases, so its neighbor generation is effectively constant per visited gene.

Finish by reconstructing the state tuple, starting distance, admissibility check, mark point, and unreachable sentinel for each problem. These five decisions are more important than memorizing one BFS template.

Reconstruction lab and answer key

Word Ladder

begin="cold", end="ward", dictionary=["cord","card","ward"]. Give the answer and its unit. What changes if "ward" is removed while the first two words remain?

Model answer

The path cold→cord→card→ward has four words, so return 4 although it has three transformations. Removing ward makes the destination unavailable and the answer 0 under this contract. Every changed-to word, including the destination, must belong to the dictionary.

Snakes and Ladders

On a 3×3 board, square 2 jumps to 8 and square 8 jumps to 9. A roll from 1 lands on 2. Which square is the resulting BFS state and why is neither 2 nor 9 correct?

Model answer

The resulting state is 8: apply the jump on the die landing exactly once. Square 2 is only the intermediate landing, and following the jump from 8 again would violate the single-jump-per-roll rule. Mark visited for destination 8. Reaching it costs one roll regardless of how many numeric labels were crossed.

Minimum Genetic Mutation

Evaluate start="AACCGGTT", end="AACCGGTT", bank=[]; then change end to "AACCGGTA" with the same empty bank. Why must the zero-change case precede a bank-membership rejection?

Model answer

The first answer is 0 because the valid starting state already is the target; no transition needs bank approval. The second answer is -1 because reaching a different target requires changing into a bank member and none exist. Checking end membership before equality would incorrectly reject the zero-change case.

Rotting Oranges

For the one-row grid [2,1,1,1,2], assign each initially fresh cell its earliest rot minute and give the completion time. Why does launching independent sequential spreads overcount?

Model answer

The three fresh cells get minutes 1,2,1, so all rot after 2 minutes. Both sources exist at minute 0 and spread concurrently; completion is the maximum nearest-source distance, not the sum of distances or time spent processing source searches. Enqueue all initial rotten cells together.

Shortest Path in Binary Matrix

For the 4×4 grid with zeros only on its main diagonal and ones elsewhere, give a shortest route and its reported length. What changes if moves are restricted to four directions?

Model answer

The diagonal route (0,0)→(1,1)→(2,2)→(3,3) uses four cells, so the answer is 4. With four-direction moves, the start has no open neighbor, so the destination is unreachable. The FIFO reasoning is unchanged but a different neighbor rule defines a different graph.

Problems in this module

• Word Ladder
• Snakes and Ladders
• Minimum Genetic Mutation
• Rotting Oranges
• Shortest Path in Binary Matrix

Interactive checkpoint

Open the Graph BFS quiz. The questions use exact, objectively gradeable answers. Work the reasoning drills above before opening their model answers.

Earlier-edition deep links

These anchors preserve links to headings from the original files. They do not reinstate superseded explanations.

Learner experience: how to make this topic stick

The moves to recognize

How to practice without turning it into grind

Debugging instincts to build

A small way to make it memorable