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