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:
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.
this page for more information on DFS, and
this page for a graphical comparison of DFS and