Assignment #7 – Graph

 

Objectives:

 

The main objectives of this assignment is:

·      Understand Graph ADT

·      Implement Graph ADT using Adjacency List structure

 

The Assignment:


Implement
AdjListGraph.java

            You can implement the vertex’s adjacency list with a doubly linked list or a hash map. I encourage you to use the hashmap. The text book has some code using the hash map.

 

Important Notes:

·       Be sure to include Time Complexity annotation and TCJ comments for each method. Use n to represent the number of vertices and m to represent the number of edges in the graph. The cost can be expressed with more than one variables, expressions, functions, like O(n+m), O(m log n), O(deg(v)), etc.

 

Getting Started:

  1. Download and import the following zip file: Assignment7.zip. For Eclipse:
    1. Open Eclipse
    2. Choose "File → Import".
    3. Select the "General" category.
    4. Pick "Existing Projects into Workspace"
    5. Click on "Next"
    6. Select the button for "Select Archive File" and browse to/select the zip file.
    7. Click on "Finish"
  2. You will need to create your own classes (an implementation of Vertex and an implementation Edge, for example). You should feel free to copy over ANY data structures to this project that you have written during the semester. However, do NOT modify the net.datastructures package. Put all your extra classes in the cs2321 package.

 

Submission:

First, look at the following checklist:

 

If you have reviewed your code and all the criteria on the checklist are acceptable, follow the submission procedure.

 

Grading Criteria:

 

Q&A:

·      Do I get same points no matter which one (EdgeList, AdjacencyList/AjacencyMap, Adjcacency Matrix) I implement?

o   No. You will get 50% if you didn’t implement the Adjacency List/AjacencyMap.