Source code online books for professionals by professionals

Chapter 5
Traversal: The Skeleton Key of 
Algorithmics
You are in a narrow hallway. This continues for several metres and ends in a doorway. Halfway 
along the passage you can see an archway where some steps lead downwards. Will you go forwards 
to the door (turn to 5), or creep down the steps (turn to 344)?
— Steve Jackson, Citadel of Chaos
Graphs are a powerful mental (and mathematical) model of structure in general; if you can formulate a problem 
as one dealing with graphs, even if it doesn’t look like a graph problem, you are probably one step closer to solving 
it. It just so happens that there is a highly useful mental model for graph algorithms as well—a skeleton key, if you 
will.
1
 That skeleton key is traversal: discovering, and later visiting, all the nodes in a graph. And it’s not just about 
obvious graphs. Consider, for example, how painting applications such as GIMP or Adobe Photoshop can fill a region 
with a single color, so-called flood fill. That’s an application of what you’ll learn here (see Exercise 5-4). Or perhaps 
you want to serialize some complex data structure and need to make sure you examine all its constituent objects? 
That’s traversal. Listing all files and directories in a part of the file system? Manage dependencies between software 
packages? More traversal.
But traversal isn’t only useful directly; it’s a crucial component and underlying principle in many other 
algorithms, such as those in Chapters 9 and 10. For example, in Chapter 10, we’ll try to match n people with n jobs, 
where each person has skills that match only some of the jobs. The algorithm works by tentatively assigning people 
to jobs but then reassigning them if someone else needs to take over. This reassignment can then trigger another 
reassignment, possibly resulting in a cascade. As you’ll see, this cascade involves moving back and forth between 
people and jobs, in a sort of zig-zag pattern, starting with an idle person and ending with an available job. What’s 
going on here? You guessed it: traversal.
I’ll cover the idea from several angles and, in several versions, trying to tie the various strands together where possible. 
This means covering two of the most well-known basic traversal strategies, depth-first search and breadth-first search, 
building up to a slightly more complex traversal-based algorithm for finding so-called strongly connected components.
Traversal is useful in that it lets us build a layer abstraction on top of some basic induction. Consider the problem 
of finding the connected components of a graph (see Figure 
5-1
 for an example). As you may recall from Chapter 2, 
a graph is connected if there is a path from each node to each of the others and if the connected components are the 
maximal subgraphs that are (individually) connected. One way of finding a connected component would be to start 
at some place in the graph and gradually grow a larger connected subgraph until we can’t get any further. How can we 
be sure that we have then reconstructed an entire component?
1
I’ve “stolen” the subtitle for this chapter from Dudley Ernest Littlewood’s The Skeleton Key of Mathematics.

---

Chapter 5 
■
 traversal: the skeleton key of algorithmiCs
94
Let’s look at the following related problem. Show that you can order the nodes in a connected graph, v
1
, v
2
, . . . , v
n
, 
so that for any i = 1 . . . n, the subgraph over v
1
, . . . , v
i
 is connected. If we can show this and we can figure out how to do 
the ordering, we can go through all the nodes in a connected component and know when they’re all used up.
How do we do this? Thinking inductively, we need to get from i–1 to i. We know that the subgraph over the i–1  
first nodes is connected. What next? Well, because there are paths between any pair of nodes, consider a node u in the 
first i–1 nodes and a node v in the remainder. On the path from u to v, consider the last node that is in the component 
we’ve built so far, as well as the first node outside it. Let’s call them x and y. Clearly there must be an edge between them, 
so adding y to the nodes of our growing component keeps it connected, and we’ve shown what we set out to show.
I hope you can see how easy the resulting procedure actually is. It’s just a matter of adding nodes that are 
connected to the component, and we discover such nodes by following an edge. An interesting point is that as long 
as we keep connecting new nodes to our component in this way, we’re building a tree. This tree is called a traversal 
tree and is a spanning tree of the component we’re traversing. (For a directed graph, it would span only the nodes we 
could reach, of course.)
To implement this procedure, we need to keep track of these “fringe” or “frontier” nodes that are just one edge 
away. If we start with a single node, the frontier will simply be its neighbors. As we start exploring, the neighbors of 
newly visited nodes will form the new fringe, while those nodes we visit now fall inside it. In other words, we need 
to maintain the fringe as a collection of some sort, where we can remove the nodes we visit and add their neighbors, 
unless they’re already on the list or we’ve already visited them. It becomes a sort of to-do list of nodes we want to visit 
but haven’t gotten around to yet. You can think of the ones we have visited as being checked off.
For those of you who have played old-school role-playing games such as Dungeons & Dragons (or, indeed, many 
of today’s video games), Figure 
5-2
 might help clarify these ideas. It shows a typical dungeon map.
2
 Think of the rooms 
(and corridors) as nodes and the doors between them as edges. There are some multiple edges (doors) here, but that’s 
really not a problem. I’ve also added a “you are here” marker to the map, along with some tracks indicating how you 
got there.
a
b
c
d
e
f
g
h
i