Module 21
Breadth-First Search
Explore in rings: the BFS template, fewest-steps shortest paths, grids, multi-source BFS, implicit graphs and 0-1 BFS.
Breadth-first search visits everything one step away, then everything two steps away, and so on. That order is exactly what you need for the fewest-steps question on an unweighted graph: the first time BFS reaches a node, it has found a shortest path to it.
This module turns that into one reusable template, then applies it to grids, to many starting points at once (rotting oranges, distance to the nearest zero), to graphs you never build explicitly (word ladders, combination locks), and to 0-1 weights with a deque.
Best after: Graph Fundamentals
Part 1
Learn the ideas
- 21.1The BFS Template and Shortest PathsA queue and a visited array. Mark nodes when you add them, process level by level, and the level number is the distance.14 min
- 21.2Grids and Multi-Source BFSStart BFS from all sources at once by putting them all in the queue at distance 0. Each cell then gets its distance to the nearest source.12 min
- 21.3Implicit Graphs: States as NodesOften the graph isn't given. Each state (a word, a lock combination, a board) is a node, and each legal move is an edge, generated on the fly.10 min
- 21.40-1 BFS with a DequeWhen edges cost 0 or 1, push 0-cost neighbours to the front of a deque and 1-cost ones to the back. Nodes still come out in order of distance.10 min
Part 2
Solve the problems
In order of difficulty. Each one shows the pattern it teaches.
Multi-source BFS on a grid, counting levels as minutes.
Single-source BFS on a grid with 8-directional moves.
Multi-source BFS from every 0 gives each cell its distance to the nearest 0.
BFS over states you generate on the fly, with forbidden states pre-marked as visited.
Grid BFS with a goal test on the border (and the entrance excluded).
An implicit graph of words, with neighbours generated by changing one letter at a time.
0-1 BFS: entering an empty cell costs 0, entering an obstacle costs 1.