What is BFS and DFS

Starting from one point

In the last lesson we looked at graphs: points are nodes, lines are edges, and a graph with no loops is a tree.
This time we'll walk on one. To walk, you first have to decide where to start.
Pick a point, and its directly connected neighbors come into view first.

Click a point to set the starting point. (start = blue · directly connected neighbors = lit up)

One step from the start reaches a neighbor, and one more step from there reaches a neighbor's neighbor.
Moving along the lines like this, stepping on points one at a time, is what walking on a graph means.

Nearest first: breadth-first

The first way of walking is a ripple. You step on everything right next to the start, then one layer farther out, then another.
Like rings spreading when you toss a stone into a pond, it spreads outward from the nearest places in order.

Each click spreads the ripple out by one layer. (visited points = colored · same layer = same distance)

While the ripple spreads, the points not yet visited wait in a line, and the ones that joined the line first get visited first.
So nearer points always come before farther ones. The layer is the distance.

All the way: depth-first

The second way of walking is exploring a maze. You pick one path and go as far as you can.
When there's nowhere left to go, you step back once and head down a side path you haven't tried.
Instead of spreading wide, it digs deep.

Each click goes down one path to the end, and backs up when it's blocked. (current point = blue · backtracked path = faded)

To remember where to come back to, you pile up the points you've passed.
You retrace from the top of the pile to look for side paths. That's why depth-first returns first to the place it visited most recently.

Breadth-first gives the shortest path

The ripple doesn't spread for nothing. Because it steps on the nearest layer first, the moment it first reaches a point is the fastest way there.
If every line is the same length, the layer at which you reach a point is its distance from the start, with no detours.

Click a point to compare the arrival distance for the two ways of walking. (breadth-first layer number = shortest distance)

Depth-first goes far quickly but may arrive by a roundabout way. So the shortest distance belongs to the ripple, that is, breadth-first.
For now, though, we've assumed every line has the same length. If the lines have different lengths, that's another story, and the next lesson takes it up.

Summary

We've seen two ways of walking on a graph. Breadth-first spreads out like a ripple, one layer at a time from the nearest places, while depth-first goes down one path to the end and then backs up.
Both step on every point, but in a different order. When distances are equal, breadth-first gives the shortest path.

Press each way of walking to turn on its shape. (breadth-first = ripple · depth-first = all the way)

Finding a route on a map, following friends of friends, getting out of a maze: walking on a graph is closer to everyday life than you might think.
In the next lesson, we'll find the fastest route on a graph where each line has a different length.