Java Reference
In-Depth Information
12 {
3
,
5
,
1003
},
13 {
4
,
2
,
1663
}, {
4
,
3
,
599
}, {
4
,
5
,
533
}, {
4
,
7
,
1260
},
14 {
4
,
8
,
864
}, {
4
,
10
,
496
},
15 {
5
,
0
,
2097
}, {
5
,
3
,
1003
}, {
5
,
4
,
533
},
16 {
5
,
6
,
983
}, {
5
,
7
,
787
},
17 {
6
,
5
,
983
}, {
6
,
7
,
214
},
18 {
7
,
4
,
1260
}, {
7
,
5
,
787
}, {
7
,
6
,
214
}, {
7
,
8
,
888
},
19 {
8
,
4
,
864
}, {
8
,
7
,
888
}, {
8
,
9
,
661
},
20 {
8
,
10
,
781
}, {
8
,
11
,
810
},
21 {
9
,
8
,
661
}, {
9
,
11
,
1187
},
22 {
10
,
2
,
1435
}, {
10
,
4
,
496
}, {
10
,
8
,
781
}, {
10
,
11
,
239
},
23 {
11
,
8
,
810
}, {
11
,
9
,
1187
}, {
11
,
10
,
239
}
24 };
25
26 WeightedGraph<String> graph1 =
27
new
WeightedGraph<>(vertices, edges);
28 WeightedGraph<String>.MST tree1 = graph1.getMinimumSpanningTree();
29 System.out.println(
"Total weight is "
+ tree1.getTotalWeight());
30 tree1.printTree();
31
32 edges =
new int
[][]{
33 {
0
,
1
,
2
}, {
0
,
3
,
8
},
34 {
1
,
0
,
2
}, {
1
,
2
,
7
}, {
1
,
3
,
3
},
35 {
2
,
1
,
7
}, {
2
,
3
,
4
}, {
2
,
4
,
5
},
36 {
3
,
0
,
8
}, {
3
,
1
,
3
}, {
3
,
2
,
4
}, {
3
,
4
,
6
},
37 {
4
,
2
,
5
}, {
4
,
3
,
6
}
38 };
39
40 WeightedGraph<Integer> graph2 =
new
WeightedGraph<>(edges,
5
);
41 WeightedGraph<Integer>.MST tree2 =
42 graph2.getMinimumSpanningTree(
1
);
43 System.out.println(
"\nTotal weight is "
+ tree2.getTotalWeight());
44 tree2.printTree();
45 }
46 }
create
graph1
MST for
graph1
total weight
print tree
create edges
create
graph2
MST for
graph2
total weight
print tree
Total weight is 6513.0
Root is: Seattle
Edges: (Seattle, San Francisco) (San Francisco, Los Angeles)
(Los Angeles, Denver) (Denver, Kansas City) (Kansas City, Chicago)
(New York, Boston) (Chicago, New York) (Dallas, Atlanta)
(Atlanta, Miami) (Kansas City, Dallas) (Dallas, Houston)
Total weight is 14.0
Root is: 1
Edges: (1, 0) (3, 2) (1, 3) (2, 4)
The program creates a weighted graph for FigureĀ 29.1 in line 27. It then invokes
getMinimumSpanningTree()
(line 28) to return an
MST
that represents a minimum span-
ning tree for the graph. Invoking
printTree()
(line 30) on the
MST
object displays the
edges in the tree. Note that
MST
is a subclass of
Tree
. The
printTree()
method is defined
in the
Tree
class.
The graphical illustration of the minimum spanning tree is shown in FigureĀ 29.9. The ver-
tices are added to the tree in this order: Seattle, San Francisco, Los Angeles, Denver, Kansas
City, Dallas, Houston, Chicago, New York, Boston, Atlanta, and Miami.
graphical illustration
Search WWH ::
Custom Search