Algorithms in a Nutshell

Depth-First Search

Consider the maze shown on the left in Figure 6-7. After some practice, a child can rapidly find the path that stretches from the start box labeled s to the target box labeled t. One way to solve this problem is to make as much forward progress as possible and assume that you are not far from the target location. That is, randomly select a direction whenever a choice is possible and stridently set off in that direction, marking where you have come from. If you ever reach a dead end or you can make no further progress without revisiting ground you have already covered, then reverse until a non-traveled branch is found and set off in that direction. 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.

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

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.

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