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.