Preliminaries Download the Graph interface, and the driver. Note The graph inter
ID: 665643 • Letter: P
Question
Preliminaries
Download the Graph interface, and the driver.
Note The graph interface is slightly modified from Lab 11, so you should redownload it
Objective
Create a class UndirectedGraph that is baseed on UndirectedUnweightedGraph, but accounting for edge weights. Your class should also implement breadth-first search over your graph.
Hints
Pay close attention to the javadoc comments of the interface.
As mentioned in class, a convenient way to implement the graph is as an adjacency list over Tuples. In this case, your Tuple class might look like:
Note that in order for hashsets over tuples to work properly, you must include the hashcode method
You are not required to implement a graph as an adjacency list, but keep in mind you will be using your graph to implement Prim's algorithm later on.
Graph Interface:
}
Driver:
Example Dialog
Notes
The graph used to test your implementation is given by the following diagram:
To better visualize the graph that is generated, the output is given in the 'dot' language implemented by graphviz You can visualize this by using the program 'dot' from GraphViz.
At the command prompt, type:
You can then open the graph.png file in any image viewer.
Explanation / Answer
This question contains lot of sub-parts, please post multiple questions
BFS Implementation
public SeqStructure getBFS(Object origin) {
resetVerticies();
SeqStructure toDo = new QueueAsList();
SeqStructure path = new QueueAsList();
Vertex originVertex = (Vertex)verticies.get(origin)
;
originVertex.visit();
toDo.put(originVertex);
path.put(originVertex);
while(!toDo.isEmpty()) {
Vertex currentVertex = (Vertex)toDo.get();
for (Iterator edges =
currentVertex.getEdgeIterator();
edges.hasNext(); ) {
Edge currentEdge = (Edge) edges.next();
Vertex nextVertex = currentEdge.getDest();
if(!nextVertex.isVisited()) {
nextVertex.visit();
toDo.put(nextVertex);
path.put(nextVertex);
}
}
}
return path;
}