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