CSci 2101 Lab 11.

30 points

Due Wednesday, April 27th.

Work in pairs on this lab.

Your goal is to finish the graph implementation that we (barely) started in class.

Task 1. Finishing the graph methods

Implement all the methods except the traversals and the shortest path. Write tests as needed. Make sure to use equals method, and not ==, to test for equality of keys.

Task 2. Traversals.

Only implement the traversals if you have time. Traversals start with a vertex and return a collection of all vertices reachable (via edges) from that vertex. The breadth-first traversal visits a vertex, then all its neighbors, then the neighbors of the neighbors, etc. The depth-first traversal follows the edges as far as possible, and then jumps back to the starting point to visit the other parts of the graph, if any. The outline is as follows:

1. Start with a given vertex.
2. Keep track of which vertices you have already visited (an array list would do) to make sure that once the vertex is visited, it is never visited again.
3. Once you visit a vertex, add it to the result and to the visited list. Add its neighbors (vertices on its adjacency list) to either a queue (for breadth-first), or a stack (for depth-first)
4. Get the next vertex from the stack (pop) or the queue (offer), and repeat from step 3.
5. Once the stack or the queu is empty, stop.

Write JUnit tests for your methods, make sure the tests pass, and submit the tests with your code.

How to submit

Submit the java file(s) with your testing code by e-mail to me. The subject of the message must be 2101 Lab 11. Make sure to CC your group partners.

CSci 2101 course web site.