Breadth-First Search II

Part I ran BFS on a binary tree, where one path reaches every node. On a grid, an explicit graph, or a state space there are many routes into the same vertex, so the one rule that matters is this: mark a vertex visited when it enters the queue, not when it leaves. Marking on the way out lets the same vertex be queued several times and the layer count stops being a distance.

The queue invariant never changes, but the code around it does. On a grid the neighbors are implicit: four offsets, bounds-checked. On an explicit graph you build an adjacency list from the edge list first. In a state space the vertex is a tuple such as (cell, budget left), and the visited structure is keyed by the whole tuple rather than by the cell.

Two seeding tricks cover most of the rest. Push every source into the queue before the first pop and the layer count becomes the distance to the nearest source. Run BFS twice, from any node and then from the farthest node it found, and the second run measures the longest path in an unweighted tree.

The problems below start on grids with multi-source spread and knight moves, move to explicit graphs and repeated BFS, and end with a state-space walk where the vertex is a cell plus a budget.