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.