CSCI-C 243 Lab 6
Graphs

Due date: 2012 Dec 3
64 points

Instructions

Last chance to turn in for credit: 2012 Dec 10.

  1. Complete the Vertex and Graph classes in the provided file Graph.java to make an adjacency-list graph representation.
  2. The main method of the Graph class tests basic graph operations. Sketch* the graph that it constructs. Run the program and capture its output.
  3. Combine the completed Graph.java with the provided files DepthFirst.java and SearchTest.java. The main method of SearchTests constructs a graph for some searches. Sketch* the graph.
  4. Compile and run the program SearchTest to solve the search problems. Capture the output. Determine whether the search results are correct, based on your previous sketch of the search graph.

You will need to use some collection classes, and I recommend using those of the Java Collections Framework found in the java.util package.

*Sketching: You may either sketch the graph on a sheet of paper and scan it, or sketch it using a computer drawing program such as GIMP or Inkscape. PDF, PNG, and JPEG files are acceptable. Do not turn in any files in a proprietary format. Ask the instructor if you are in doubt.

Provided code

Files:

You'll need to modify the file Graph.java. The other two files should not need any changes.

What to Turn in

  1. Source listing Graph.java with completed constructors and methods.
  2. Test output from Graph.main.
  3. Sketches of the test graphs built in Graph.main and SearchTest.main.
  4. Test output from SearchTest.main, with each search result marked as correct or incorrect.

Grading