Algorithms in a Nutshell

Depth-First Search | 143

Graph

Algorithms

The numbers on the right side of Figure 6-7 reflect the branching points of one

such solution; in fact, every square in the maze is visited in this solution.

We can represent the maze in Figure 6-7 by creating a graph consisting of vertices

and edges. A vertex is created for each branching point in the maze (labeled by

numbers on the right in Figure 6-7), as well as “dead ends.” An edge exists only if

there is a direct path in the maze between the two vertices where no choice in

direction can be made. The undirected graph representation of the maze from

Figure 6-7 is shown in Figure 6-8; each vertex has a unique identifier.

To solve the maze, we need only ask whether a path exists in the graphG=(V,E)

of Figure 6-7 from the vertexsto the target vertex,t. In this example, all edges are

undirected, but one could easily consider directed edges if the maze imposed such

restrictions.

The fact sheet in Figure 6-9 contains pseudocode describing DEPTH-FIRSTSEARCH.

The heart of DEPTH-FIRSTSEARCHis a recursivedfs_visit(u)operation, which

visits a vertexuthat previously has not been visited before.dfs_visit(u)records its

progress by coloring vertices one of three colors:

Figure 6-7. A small maze to get from s to t

Figure 6-8. Graph representation of maze from Figure 6-7

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use