Suggestions and Clarifications for Project 2.2
On this page we will post suggestions and clarifications
related to Project 2.2.
- You need to turn in exactly these files:
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
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.