Chapter 5
■
traversal: the skeleton key of algorithmiCs
101
Imagine that someone poked a hole through one of the walls in the maze so that the corresponding graph
suddenly had a cycle. Perhaps they busted through the wall just north of the dead end at node
e.
If you started your
walk at
e, walking north, you could keep left all you wanted, but you’d never traverse the entire maze—you’d keep
walking in circles.
8
This is a problem we face when traversing general graphs.
9
The general idea in Listing 5-1 gives us
a way out of this problem, but before I get into that, let’s see what our French telegraphic engineer came up with.
How to Stop Walking in Circles
Édouard Lucas describes Tremaux’s algorithm for traversing mazes in the first volume of his
Récréations
Mathématiques in 1891.
Lucas writes, in his introduction:
10
To completely traverse all the passages of a labyrinth twice, from any initial point, simply follow
the rules posed by Trémaux, marking each entry to or exit from an intersection. These rules may
be summarized as follows: When possible, avoid passing an intersection you have already visited,
and avoid taking passages you have already traversed. Is this not a prudent approach, which also
applies in everyday life?
Later in the book, he goes on to describe the method in much more detail, but it is really quite simple, and the
previous quote covers the main idea nicely. Instead of marking each entry or exit (say, with a piece of chalk), let’s just
say you have muddy boots, so you can see our own tracks (like in Figure
5-2
). Trémaux would then tell you to start
walking
in any direction, backtracking whenever you came to a dead end or an intersection you had already walked
through (to avoid cycles). You can’t traverse a passage more than twice (once forward and once backward), so if you’re
backtracking into an intersection, you walk forward into one of the unexplored passages, if there are any. If there
aren’t any, you keep backtracking (into some other passage with a single set of footprints).
11
And that’s the algorithm. One interesting observation to make is that although you can choose several passages
for
forward traversal, there will always be only
one available for backtracking. Do you see why that is? The only way
there could be
two (or more) would be if you had set off in another direction from an intersection
and then come back
to it without backtracking.
In this case, though, the rules state that you should
not enter the intersection but backtrack
immediately. (This is also the reason why you’ll never end up traversing a passage twice in the same direction.)
The reason I’ve used the “muddy boots” description here is to make the backtracking really clear; it’s exactly
like the one in the recursive tree traversal (which, again, was equivalent to the left-hand rule). In fact, if formulated
recursively, Trémaux’s algorithm is just like the tree walk, with the addition of a bit of memory. We know which
nodes we have already visited and pretend there’s a wall preventing
us from entering them, in effect simulating a tree
structure (which becomes our traversal tree).
See Listing 5-4 for a recursive version of Trémaux’s algorithm. In this formulation, it is commonly known as
depth-first search, and it is one of the most fundamental (and fundamentally important) traversal algorithms.
12
8
And just like that, a spelunker can turn troglodyte.
9
People seem to end up walking in circles when wandering in the wild as well. And research by the U.S. Army suggests that people
prefer going south, for some reason (as long as they have their bearings). Neither strategy is particularly helpful if you’re aiming for
a complete traversal, of course.
10
My translation.
11
You can perform the same procedure even if your boots aren’t muddy. Just make sure to clearly mark entries and exits (say,
with a piece of chalk). In this case, it’s important to make two marks when you come to an old intersection and immediately start
backtracking.
12
In fact, in some contexts, the term
backtracking is used as a synonym for recursive traversal, or depth-first search.
