Source code online books for professionals by professionals

NODe COLOrS aND eDGe tYpeS
in describing traversal, i have distinguished between three kinds of nodes: those we don’t know about, those 
in our queue, and those we’ve visited (and whose neighbors are now in the queue). some books (such as 
Introduction to Algorithms, by Cormen et al., mentioned in Chapter 1) introduce a form of node coloring, which 
is especially important in Dfs. each node is considered white to begin with; they’re gray in the interval between 
their discover time and their finish time, and they’re black thereafter. you don’t really need this classification in 
order to implement Dfs, but it can be useful in understanding it (or, at least, it might be useful to know about it if 
you’re going to read a text that uses the coloring).
in terms of trémaux’s algorithm, gray intersections would be ones we’ve seen but have since avoided; black 
intersections would be the ones we’ve been forced to enter a second time (while backtracking).
these colors can also be used to classify the edges in the Dfs tree. if an edge uv is explored and the node v is 
white, the edge is a tree edge—that is, it’s part of the traversal tree. if v is gray, it’s a so-called back edge, one 
that goes back to an ancestor in the Dfs tree. finally, if v is black, the edge is either what is called a forward edge 
or a cross edge. a forward edge is an edge to a descendant in the traversal tree, while a cross edge is any other 
edge (that is, not a tree, back or forward edge).
note that you can classify the edges without actually using any explicit color labeling. let the time span of a 
node be the interval from its discover time to its finish time. a descendant will then have a time span contained 
in its ancestor’s, while nodes unrelated by ancestry will have nonoverlapping intervals. thus, you can use the 
timestamps to figure out whether something is, say, a back or forward edge. even with color labeling, you’d need 
to consult the timestamps to differentiate between forward and cross edges.
you probably won’t need this classification much, although it does have one important use. if you find a back 
edge, the graph contains a cycle, but if you don’t, it doesn’t. (exercise 5-10 asks you to show this.) in other words, 
you can use Dfs to check whether a graph is a Dag (or, for undirected graphs, a tree). exercise 5-11 asks you to 
consider how other traversal algorithms would work for this purpose.

---

Chapter 5 
■
 traversal: the skeleton key of algorithmiCs
106
Infinite Mazes and Shortest (Unweighted) Paths
Until now, the overeager behavior of DFS hasn’t been a problem. We let it loose in a maze (graph), and it veers off in 
some direction, as far as it can, before it starts backtracking. This can be problematic, though, if the maze is extremely 
large. Maybe what we’re looking for, such as an exit, is close to where we started; if DFS sets off in a different direction, 
it may not return for ages. And if the maze is infinite, it will never get back, even though a different traversal might have 
found the exit in a matter of minutes. Infinite mazes may sound far-fetched, but they’re actually a close analogy to an 
important type of traversal problem—that of looking for a solution in a state-space.
But getting lost by being over-eager, like DFS, isn’t only a problem in huge graphs. If we’re looking for the shortest 
paths (disregarding edge weights, for now) from our start node to all the others, DFS will, most likely, give us the wrong 
answer. Take a look at the example in Figure 
5-6
. What happens is that DFS, in its eagerness, keeps going until it reaches 
c via a detour, as it were. If we want to find the shortest paths to all other nodes (as illustrated in the figure on the right), 
we need to be more conservative. To avoid taking a detour and reaching a node “from behind,” we need to advance our 
traversal “fringe” one step at a time. First visit all nodes one step away and then all those two steps away, and so forth.
14
In other words, let’s think inductively.
15
IDDFS isn’t completely equivalent to Ore’s method because it doesn’t mark edges as closed in the same way. Adding that kind of 
marking is certainly possible and would be a form of pruning, discussed later in this chapter.
c
d
a
b
c
d
a
b
DFS tree from a
SP tree from a