## Recursive depth-first search (DFS)

Depth-first search (DFS) is an algorithm that traverses a graph in
search of one or more goal nodes. As we will discover in a few weeks, a
maze is a special instance of the mathematical object known as a "graph".
In the meantime, however, we will use "maze" and "graph"
interchangeably.

The defining characteristic of this search is that, whenever DFS visits
a maze cell *c*, it recursively searches the sub-maze whose origin is
*c*. This recursive behaviour can be simulated by an iterative
algorithm using a stack. A cell can have three states:

*Unvisited*. The cell has not yet been visited by DFS.
*Visit In Progress*. The cell has been discovered, but not
yet finished. Ie, the recursive search which begins at this node
has not yet terminated.
*Visited*. The cell has been discovered, and the submazes
which start at this node have been completely visited also.

The algorithm for DFS is thus:

**Depth-First-Search-Kickoff**( Maze *m* )
Depth-First-Search( *m*.StartCell )
**End procedure**
**Depth-First-Search**( MazeCell *c* )
If *c* is the goal
Exit
Else
Mark *c* "Visit In Progress"
Foreach neighbor *n* of *c*
If *n* "Unvisited"
Depth-First-Search( *n* )
Mark *c* "Visited"
**End procedure**

The end result is that DFS will follow some path through the maze as
far as it will go, until a dead end or previously visited location is
found. When this occurs, the search backtracks to try another path,
until it finds an exit.

**Note that this assignment asks you to modify the above algorithm to use an
iterative solution based on a stack.**

See
this page for more information on DFS, and
this page for a graphical comparison of DFS and
BFS.

CSE 326 Summer 2003 Homepage