Java Reference
In-Depth Information
***29.19
( Find u with smallest cost[u] efficiently ) The getShortestPath method
finds a u with the smallest cost[u] using a linear search, which takes O (
V
).
The search time can be reduced to O (log
) using an AVL tree. Modify the
method using an AVL tree to store the vertices in V - T . Use Listing 29.7,
TestShortestPath.java, to test your new implementation.
V
***29.20
( Test if a vertex u is in T efficiently ) Since T is implemented using a list
in  the getMinimumSpanningTree and getShortestPath methods in
Listing 29.2 WeightedGraph.java, testing whether a vertex u is in T by invoking
T.contains(u) takes O(n) time. Modify these two methods by introducing
an array named isInT. Set isInT[u] to true when a vertex u is added to T .
Testing whether a vertex u is in T can now be done in O(1) time. Write a test
program using the following code, where graph1 is created from Figure 29.1.
WeightedGraph<String> graph1 = new WeightedGraph<>(edges, vertices);
WeightedGraph<String>.MST tree1 = graph1.getMinimumSpanningTree();
System.out.println( "Total weight is " + tree1.getTotalWeight());
tree1.printTree();
WeightedGraph<String>.ShortestPathTree tree2 =
graph1.getShortestPath(graph1.getIndex( "Chicago" ));
tree2.printAllPaths();
 
 
Search WWH ::




Custom Search