Exploring in rings
Breadth first search visits a graph or grid outward from a start, finishing all nodes at one distance before moving to the next. That ring by ring order makes it the natural tool for shortest paths in unweighted graphs, level order traversals, and spreading processes like flood fill.
Queue and visited set
The template rests on two structures.
- A queue holds the frontier of nodes waiting to be explored, in first in first out order.
- A visited set marks nodes already enqueued so none is processed twice.
Seed the queue with the start node and mark it visited. Then repeatedly remove the front node, examine its neighbors, and enqueue each unvisited neighbor while marking it. The first in first out order guarantees nearer nodes leave the queue before farther ones.
Tracking levels
To know the distance of each node, process the queue one level at a time. Record how many nodes are in the current frontier, drain exactly that many, and increment a depth counter before starting the next ring. This level loop yields shortest distances and level order groupings together.
Key idea
A queue plus a visited set explores a graph ring by ring, and because nearer nodes leave the queue first, BFS finds shortest paths in unweighted graphs.