Lab 10: Depth-First Searching
Types of Searches
When you are traversing a graph (or a tree) structure, there are two typical ways
to step through each vertex (or node):
- Breadth First
- In a breadth-first search, the first vertices accessed are the ones adjacent to the starting vertex.
Next, the ones adjacent to the ones adjacent to the starting vertex, etc.
- You can think of a breadth-first search as accessing vertices in rings away from the
starting point like ripples from a drop of water.
- In order to keep track of the vertices as we traverse them, we use some sort of a queue
structure (possibly in the form of an array).
- Depth First
- In a depth-first search, the search begins at the starting vertex and steps through one
path of vertices as far as it can before backtracing.
- You can think of a depth-first search as accessing vertices the way a person walks through a
maze: go as far as you can until you reach a dead end, then back up and try another path.
- In order to keep track of the vertices as we traverse them, we use some sort of a stack structure
(often done with the runtime stack through recursion).
- Especially with Binary Search Trees, there are three (3) types of depth-first traversals:
- Preorder traversal: the work is done at the parent before the children.
- Inorder traversal: the work is done at the left child first, then the parent, then the right child.
(We use this one for printing a BST in sorted order.)
- Postorder traversal: the work is done at the children before the parent.
Given a randomly generated maze, do a (post-order) depth-first search using recursion to find and mark
the pathway out of the maze.
maze class (which uses the provided
disj_sets class) has methods for performing all necessary maze operations:
mark_path (for making a room part of the successful exit path),
is_open (for determining if a direction from the current room is
is_exit for determining if the current room is the
operator<< for printing the maze and any marked
- Copy the files from
/users/smatzko/212/public/ to your folder.
- Create a file
- Constructor: Initialize the maze to the
appropriate width and height passed in. (The
user specifies them to the main on the command line). OPTIONAL: Print out
the maze you created to confirm that it was successfully generated.
try_path: Recursively search the maze for the
path to the exit.
col specify the current room from which we are trying
to find a path to the exit.
maze::path paths specifies which directions to
search for a path to the exit. This variable prevents infinite loops.
(e.g. room 5, 1 to 4, 1 to 5, 1 to 4, 1 . . .).
- In the
paths variable, each compass direction is specified by
a different bit "flag." By using the bitwise &, you can determine
which directions are specified for searching.
(paths & maze::WEST) is true, try the west.
- If the current "room" is the exit, mark it as part of the path out
and return true.
- Otherwise, individually try each compass direction specified in the
- For each indicated direction, if the maze confirms that the path is open,
try that path. If the path is does indeed lead out (returns true), mark
the current room (using
mark_path) as part of the path to the exit.
- If all indicated paths fail, return false.
- When you try a path, search the three (3) compass
directions that are away from our current location.
e.g. If we are trying the room SOUTH of our current room,
call try_path on
row+1, col, for all paths
find_path: Begin the search for the path out of the maze,
starting at 0, 0.
Since the starting point is the upper left-hand corner, you can attempt
to traverse south (maze::SOUTH) and right (maze::EAST).
(maze::EAST | maze::SOUTH). If
try_path returns false, then there are no paths out of the maze.
(However, I guarantee there IS a path, so that means your search is broken.)
operator<<: output the maze.
Turn in all of the code, and the Makefile.
sendlab.212.302 10 *.o *.cpp *.h Makefile