Suggestions and Clarifications for Project 2.2

• You need to turn in exactly these files: myGraph.java, experiments.java, and results. Make sure that your files have exactly these names. myGraph.java should contain the new, adjacency list based implementation of the myGraph class, including the breadth first traversal function. experiments.java should contain code to perform the two experiments, mentioned in the handout. results should contain a brief write-up associated with the experiments; it can be in MS Word format (results.doc) or pdf format (results.pdf). Please do not turn in wirelessNetwork.java. We will compile and execute your programs with the wirelessNetwork class that we made in our solution for Project 1.

• Implement the function for doing breadth first traversal so that it has exactly the same interface and functionality as the function for depth first traversal. Thus you should use the following function header. public void breadthFirstTraversal(String source) The purpose of this function is to construct a breadth first traversal tree, stored in an int array called BFTTree. As it says in the handout, your function should traverse all connected components of the graph.

• Implement a function in the myGraph class with the following header: public String[] shortestPath(String s, String t) This function should return a shortest path between vertex s and vertex t in an array of strings. If there is a path betwee the two vertices, then the first element of this array should be s and the last should be t. Otherwise, the function should return an empty array. This function should call the breadth first traversal function with source s and then consult BFTTree.

• You should start with the Lafore's implementation of the queue data structure and modify it to accomodate a queue of int, rather than a queue or long. This is the only modfication you should perform. Please do not submit this file. We will run your code with our copy of Lafore's queue data structure, similarly modified.