Breadth first and depth first: the same loop, a different container

One loop#

Every graph search is this:

put the start in the container
mark it seen
while the container is not empty:
    take something out
    for each neighbour:
        if it has not been seen:
            mark it seen
            put it in

Take from the back and it is depth first. Take from the front and it is breadth first. That is the entire difference, and it changes which questions the walk can answer.

What the container changes#

Depth first follows one route as far as it goes, then backs up and tries the next. It reaches everything reachable, and the order it arrives in tells you nothing about distance.

Breadth first settles everything one step away, then everything two steps away, and so on. So the first time it arrives anywhere, it has arrived by a shortest route.

If a question says shortest or fewest on a graph where every edge costs the same, it is breadth first. If edges have different costs, it is neither: that is Dijkstra, and it needs a heap instead of a queue.

The one line people get wrong#

Mark a node seen when you put it in, not when you take it out.

Mark on the way out and a node with three neighbours pointing at it gets queued three times. It still gives the right answer, and on a dense graph the queue grows enough to run out of memory. Worse, distances recorded on a later arrival overwrite the correct earlier one.

This is also the only real difference between walking a graph and walking a tree. A tree has exactly one route to each node, so nothing needs remembering. A graph can have many, and that set is what stops you going round for ever.

Starting everywhere at once#

Some questions have several starting points: rot spreading from every rotten orange, fire from every burning cell, distance to the nearest shop.

You do not need one search per source. Put all of them in the queue before the loop begins, all at distance zero. Breadth first then expands them together and each cell is reached first by whichever source is nearest, which is exactly what "nearest" means. One extra loop at the start, and the search itself is unchanged.

Counting groups#

The other everyday shape is counting connected components:

for each node:
    if it has not been seen:
        count += 1
        walk everything reachable from it

Either walk does, because you are only asking what is reachable. Number of islands and number of provinces are both this, one on a grid and one on an adjacency matrix.

A grid is a graph#

Nearly every grid question is a graph question in disguise. Each cell is a node, and each shared edge is a connection. You never build the graph: the neighbours of (r, c) are the four cells around it, worked out when you need them.

Once you see that, islands, rotting oranges, flood fill, shortest path through a maze and the knight's moves are all the same loop with a different rule for what counts as a neighbour.

Practice in order#

1. Number of provinces, counting components on an adjacency matrix.
2. Number of islands, the same count on a grid.
3. Rotting oranges, which is breadth first, multi-source, and a real use of distance.
4. Level order traversal, which is this walk on a tree, where the seen set is unnecessary.