COSC 310 – Data Structures and Algorithms
Assignment 9 – Graphs
The objectives of this assignment are to:
1) Gain further experience with using interfaces.
2) Gain experience with implementation of a Graph.
3) Gain experience using Sets.
4) Gain further experience with recursions.
5) Gain experience with using graphs to solve problems.
6) Continue to practice good programming techniques.
Task:
Step 1:
Add to ALGraph.java an implementation of depthFirstSearch and bestSearch. Use the Dijkstra algorithm as the implementation for bestSearch.
Step 2:
Add to the graph in TestGraph an edge from Detroit to Pittsburgh with a distance of 400.
Modify the TestGraph to print the path results from breadthFirstSearch, depthFirstSearch, and bestSearch for paths from Philadelphia to Detroit and Fort Wayne to Toledo.
Step 3:
Create a new test program, TestGraph2, using the same graph of step 3, only use a Road object for edges. The Road object must have a distance and a speed limit attributes. Use the same distances, only use 80 as the speed on the path from Pittsburgh, Cleveland, Columbus, Indianapolis, Fort Wayne, to Chicago, and 25 for all other edges. Then find and print the breadthFirstSearch, depthFirstSearch, bestSearch using distance, and bestSearch using time for the path from Philadelphia to Chicago.
Step 4:
Create a new test program, TestGraph3 for the directed graph in Figure 10.26 (shown below). Then find and print the breadthFirstSearch, depthFirstSearch, bestSearch for paths from 0 to 4 and from 1 to 0.
Bonus 10 points
Provide an aStarSearch method. This method has the same arguments as the bestSearch except uses the A Star algorithm to determine the best path. For this problem a City class must be defined. A city will hold the city name along with coordinates. Use the straight line distance between two cities (based on the city coordinates – that is the square root of the sum of square of delta x and square of delta y) as the heuristic guiding the A Star algorithm. Use the coordinates on the following graph:
Run the aStarSearch for “Toledo” to “Fort Wayne”.
Deliverables:
1) A. zip file containing the sources and class files for ALGraph, Graph, and TestGraph, TestGraph2 and TestGraph3. The .zip file must be named [Your name]Asmt9.zip.
2) Files of your captured output from running the test programs.
