Lab 10: Depth-First Searching

Background

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):
  1. 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).
  2. 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:
      1. Preorder traversal: the work is done at the parent before the children.
      2. 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.)
      3. Postorder traversal: the work is done at the children before the parent.

Assignment

Goal

Given a randomly generated maze, do a (post-order) depth-first search using recursion to find and mark the pathway out of the maze.

Provided Code

The provided 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 not blocked), is_exit for determining if the current room is the exit, and operator<< for printing the maze and any marked paths.

Steps

  1. Copy the files from /users/smatzko/212/public/ to your folder.
  2. Create a file path_finder.cpp.
  3. 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.
  4. try_path: Recursively search the maze for the path to the exit.
    • Parameters row and col specify the current room from which we are trying to find a path to the exit.
    • Parameter 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.
      e.g. If (paths & maze::WEST) is true, try the west.
    1. If the current "room" is the exit, mark it as part of the path out and return true.
    2. Otherwise, individually try each compass direction specified in the maze::path parameter.
    3. 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.
    4. If all indicated paths fail, return false.
    5. 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 but north: maze::ALL-maze::NORTH.
  5. 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). e.g. (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.)
  6. operator<<: output the maze.

    Turn in

    Turn in all of the code, and the Makefile.
    Use sendlab.212.302 10 *.o *.cpp *.h Makefile