Breadth-First Search II

On a grid, a graph, or a state space, many routes lead into the same vertex. BFS explores in waves of distance, so it still finds the fewest steps as long as no vertex is queued twice.

Substrate	What a vertex is	Neighbors
2D grid	A (row, col) cell	Four or eight offset steps
Explicit graph	A node index 0..n-1	Adjacency list built from edges
State space	A tuple like (cell, budget)	Next legal states

The rule that matters is marking a vertex visited when it enters the queue, not when it leaves. Wait until the pop and several neighbors can push the same vertex, so the queue fills with copies. Two seeding patterns come up constantly. Push every source before the first pop to measure distance to the nearest one, or run BFS twice, from any node and then from the farthest found, to get an unweighted tree's diameter.

Approach	Time	Extra space
Grid BFS, one or many sources	$O(RC)$	$O(RC)$
Graph BFS on an adjacency list	$O(V + E)$	$O(V)$
State-space BFS, $B$ budgets	$O(RC \cdot B)$	$O(RC \cdot B)$

Use it when every step costs one unit and you want the fewest steps from one start, the spread from many starts, or a shortest route that carries a small extra state.

The problems below start on grids with multi-source spread and knight moves, move to explicit graphs and two-pass tree distances, and end with a state-space walk over a cell plus a remaining budget.