Pattern 7: BFS (Breadth-First Search)

Deep Dive: BFS as Ripple Expansion

Word Ladder -- BFS for Shortest Transformation

begin="hit", end="cog", dict=["hot","dot","dog","lot","log","cog"]

Level 0: {hit}
Level 1: {hot}         (h->h, i->o: "hot" in dict)
Level 2: {dot, lot}    (hot->dot, hot->lot)
Level 3: {dog, log}    (dot->dog, lot->log)
Level 4: {cog}         (dog->cog, log->cog)

Shortest path = 5 (hit->hot->dot->dog->cog)

BFS guarantees the FIRST time you reach "cog" is via the shortest path. DFS might find hit->hot->lot->log->cog (also 5) but would explore many longer paths first.

---

Signal: Shortest path (unweighted), level-by-level, "minimum steps", multi-source spread Template: bfs() in templates.py

When to Use

• "Shortest path" in unweighted graph/grid
• "Level-order traversal"
• "Minimum steps to reach X"
• "Rotten oranges" / spreading from multiple sources

Re-solve from Phase 1-2 (TIMED)

Problem	Source	Target Time	Done?
Binary Tree Level Order Traversal	Phase 1.7	12 min	[ ]
Rotting Oranges	Phase 2.4	20 min	[ ]
Word Ladder	Phase 2.4	25 min	[ ]

New Practice Problems

Add problems to solutions/ and enrich as needed.

---

First-time Recognition Signals

When you read a brand-new problem statement, this pattern is the right tool if you see:

• "Shortest number of steps / minimum moves / fewest operations" in an unweighted graph or grid — BFS guarantees the shortest path the first time it touches a node.
• "Level order traversal" of a tree, or "process nodes level by level" — BFS is by definition level-by-level.
• "Spread from multiple sources at once" (Rotting Oranges, Walls and Gates, 0/1 Matrix) — multi-source BFS by seeding the queue with every source.
• "Word transformation / state-space search" where each state has a small set of neighbours and you want the shortest chain — BFS over the implicit graph of states.
• "Minimum knight / dice / jump moves to reach target" — same shape: each move is one edge of weight 1.

Anti-signals (looks like this pattern, isn't)

• "Shortest path with weighted edges" — plain BFS is wrong; use Dijkstra (or 0-1 BFS for 0/1 weights).
• "Find / count all paths from A to B" — BFS gives shortest only; use DFS / backtracking.
• "Connected components count" — either BFS or DFS works; DFS is usually shorter to write. Pick BFS only when recursion depth would blow the stack.