Homework 6 

Out: Tue 11 November 1997
Due: Tue 18 November 1997

Programming Assignment

Write a program which uses depth first search to find a route through a maze. Mazes are corriodors and doors that have a route from entry to exit, but the route is hard to find. A maze can be modeled as a graph where the nodes are places along the maze and the edges indicate which places are immediately accessible to each other. For instance, this maze: 

      +-------+---+
      |       |   |
      |    +--+   |
           |  
      |    |   ---+
      |           |
      + ----------+
Can be drawn as this graph: 


        F---G   J
        |       |
    A---B   H---I---K
        |   |
        C---D---E
Using DFS to find a route in the graph from A to K gives a path through the maze.

Use the AdjList.C code that we wrote in class to represent the graph. The input will be a file of vertices and the answer is a printout of a path from vertex 0 to vertex (n-1), where there are n vertices in the graph. The format for the input file describes the graph with an initial line giving the number of vertices in the graph and then one line per edge, each line having two integers giving the vertices in the edge. Sample inputs to try are:

  1. An 11 node graph.
  2. A 27 node graph.
Note that the first sample is the graph drawn above, with 0 for A, 1 for B, etc.

Submitting Homework:

Call your program GraphSearch.C, and use the command 

   PostIt GraphSearch.C
to submit your homework on or before midnight of the due date.