Java Reference
In-Depth Information
AbstractGraph.Tree
WeightedGraph.MST
-totalWeight: int
Total weight of the tree.
+MST(root: int, parent: int[], searchOrder:
List<Integer> totalWeight: int)
+getTotalWeight(): int
Constructs an MST with the specified root, parent array,
searchOrder,
and total weight for the tree.
Returns the
totalWeight
of the tree.
F
IGURE
29.8
The
MST
class extends the
Tree
class.
The refined version of the Prim's algoruthm greatly simplifies the implementation. The
getMinimumSpanningTree
method was implemented using the refined version of the
Prim's algorithm in lines 99-138 in Listing 29.2. The
getMinimumSpanningTree(int
startingVertex)
method sets
cost[startingVertex]
to
0
(line 105) and
cost[v]
to
infinity for all other verties (lines 102-104). The parent of
startingVertex
is set to
-1
(line
108).
T
is a list that stores the vertices added into the spanning tree (line 111). We use a list for
T
rather than a set in order to record the order of the vertices added to
T
.
Initially,
T
is empty. To expand
T
, the method performs the following operations:
1. Find the vertex
u
with the smallest
cost[u]
(lines 118-123 and add it into
T
(line 125).
2. After adding
u
in
T
, update
cost[v]
and
parent[v]
for each
v
adjacent to
u
in
V-T
if
cost[v] > w(u, v)
(lines 129-134).
After a new vertex is added to
T
,
totalWeight
is updated (line 126). Once all vertices are
added to
T
, an instance of
MST
is created (line 137). Note that the method will not work if the
graph is not connected. However, you can modify it to obtain a partial MST.
The
MST
class extends the
Tree
class (line 141). To create an instance of
MST
, pass
root
,
parent
,
T
, and
totalWeight
(lines 144-145). The data fields
root
,
parent
,
and
searchOrder
are defined in the
Tree
class, which is an inner class defined in
AbstractGraph
.
Note that testing whether a vertex
i
is in
T
by invoking
T.conatins(i)
takes
O(n)
time,
since
T
is a list. Therefore, the overall time complexity for this implemention is O(n
3
). Inter-
ested readers may see Programming Exercise 29.20 for improving the implementation and
reduce the complexity to O(n
2
).
Listing 29.6 gives a test program that displays minimum spanning trees for the graph in
Figure 29.1 and the graph in Figure 29.3a, respectively.
time complexity
L
ISTING
29.6
TestMinimumSpanningTree.java
1
public class
TestMinimumSpanningTree {
2
public static void
main(String[] args) {
3 String[] vertices = {
"Seattle"
,
"San Francisco"
,
"Los Angeles"
,
4
create vertices
"Denver"
,
"Kansas City"
,
"Chicago"
,
"Boston"
,
"New York"
,
5
"Atlanta"
,
"Miami"
,
"Dallas"
,
"Houston"
};
6
7
int
[][] edges = {
8 {
0
,
1
,
807
}, {
0
,
3
,
1331
}, {
0
,
5
,
2097
},
9 {
1
,
0
,
807
}, {
1
,
2
,
381
}, {
1
,
3
,
1267
},
10 {
2
,
1
,
381
}, {
2
,
3
,
1015
}, {
2
,
4
,
1663
}, {
2
,
10
,
1435
},
11 {
3
,
0
,
1331
}, {
3
,
1
,
1267
}, {
3
,
2
,
1015
}, {
3
,
4
,
599
},
create edges
Search WWH ::
Custom Search