Source code online books for professionals by professionals

Figure 5-2.  A partial traversal of a typical role-playing dungeon. Think of the rooms as nodes and the doors as edges. 
The traversal tree is defined by your tracks; the fringe (the traversal queue) consists of the neighboring rooms, the light 
ones without footprints. The remaining (darkened) rooms haven’t been discovered yet
3
I’ll be using dicts with adjacency sets as the default representation in the following, although many of the algorithms will work 
nicely with other representations from Chapter 2 as well. Usually, rewriting an algorithm to use a different representation isn’t too 
hard either.

---

Chapter 5 
■
 traversal: the skeleton key of algorithmiCs
96
Tip
 
■
  objects of the 
set
 type let you perform set operations on other types as well! for example, in listing 5-1, i use 
the dict 
P
 as if it were a set (of its keys) in the 
difference
 method. this works with other iterables too, such as 
list
 or 
deque
, for example, and with other set methods, such as 
update
.
A couple of things about this new code may not be immediately obvious. For example, what is the S parameter, 
and why am I using a dictionary to keep track of which nodes we have visited (rather than, say, a set)? The S parameter 
isn’t all that useful right now, but we’ll need it when we try to find strongly connected components (near the end of the 
chapter). Basically, it represents a “forbidden zone”—a set of nodes that we may not have visited during our traversal 
but that we have been told to avoid. As for the dictionary P, I’m using it to represent predecessors. Each time we add a 
new node to the queue, I set its predecessor; that is, I make sure I remember where I came from when I found it. These 
predecessors will, when taken together, form the traversal tree. If you don’t care about the tree, you’re certainly free to 
use a set of visited nodes instead (which I will do in some of my implementations later in this chapter).
Note
 
■
  Whether you add nodes to this sort of “visited” set at the same time as adding them to the queue or later,  
when you pop them from the queue, is generally not important. it does have consequences for where you need to add an 
“if visited ...” check, though. you’ll see several versions of the general traversal strategy in this chapter.
The walk function will traverse a single connected component (assuming the graph is undirected). To find all the 
components, you need to wrap it in a loop over the nodes, like in Listing 5-2.