Two ways to walk a graph
Here's a graph made of dots and lines. To start at one dot and visit the whole thing, how should you walk? You could spread out like a ripple, nearest first, or follow one path to the end and come back. Same graph, two gaits.
Starting from one dot
Last time we saw a graph.
Dots are nodes, lines are edges,
and a graph with no loops is a tree.
This time, let's walk on it.
To walk, first
we pick where to start.
Choose one dot,
and its directly linked neighbors show up.
Click a dot to set the start. (Start = blue · directly linked neighbors = lit up)
One step from the start
reaches a neighbor.
Another step from there
is the neighbor's neighbor.
Moving your feet
along the lines like this,
touching dots one by one,
is walking on a graph.
Nearest first, breadth-first
The first gait is a ripple.
Touch everything right next to the start,
then one layer farther,
then one more layer.
Like a stone in a pond
spreading rings,
from near to far in turn,
it fans outward.
Each click spreads one layer like a ripple. (Touched dots = colored · same layer is same distance)
While the ripple spreads,
dots not yet reached
wait in a line.
The ones who lined up first
get visited first, in turn.
So a nearer dot
always comes before a farther one.
The layer is the distance.
To the end, depth-first
The second gait is maze exploring.
Pick one path
and go as far as you can.
When there's nowhere left,
step back once
and go down an untried side path.
Instead of spreading wide,
it digs deep.
Click to go one path to the end, then backtrack when stuck. (Current dot = blue · backtracked path = dimmed)
To not forget to come back,
stack up the dots you passed.
From the stacked pile,
retrace from the top one
to find a side path.
So depth-first
goes back first
to the most recently visited place.
Breadth-first gives the shortest
The ripple doesn't spread for nothing.
Since it touches the near layer first,
the moment you first reach a dot
is the quickest route to it.
If every line is the same distance,
which layer you reach it in
is the distance from the start.
There's no detour.
Click to compare the arrival order of the two gaits. (Breadth-first layer number = the shortest distance)
Depth-first goes far fast,
but it can arrive the long way around.
So the shortest distance
belongs to the ripple, breadth-first.
For now, though, we treated
every line as the same distance.
When lines differ in distance
it's another story, and that's for next time.
Recap
We saw two ways to walk a graph.
Breadth-first spreads like a ripple,
layer by layer from the near,
and depth-first follows one path
to the end, then backtracks.
Both touch every dot,
just in a different order.
With equal distance, breadth-first is shortest.
Tap the two gaits to turn them on. (Breadth-first = ripple · depth-first = to the end)
Finding a route on a map,
following friends of friends,
getting out of a maze.
Walking on a graph
is closer than you'd think.
Next, we'll talk about finding
the fastest route on a graph
where lines differ in distance.