WEIGHTED GRAPHS AND APPLICATIONS - Introduction to Java Programming: Comprehensive Version - page 1068

82 ", " + edge.v + ", " + ((WeightedEdge)edge).weight + ") " );

83 }
84 System.out.println();
85 }
86 }
87
88 /** Add edges to the weighted graph */

add edge

89 public boolean addEdge( int u, int v, double weight) {

90 return addEdge( new WeightedEdge(u, v, weight));

91 }
92
93

/** Get a minimum spanning tree rooted at vertex 0 */

94 public MST getMinimumSpanningTree() {

get an MST
start from vertex 0

95 return getMinimumSpanningTree( 0 );

96 }
97
98 /** Get a minimum spanning tree rooted at a specified vertex */
99 public MST getMinimumSpanningTree( int startingVertex) {
100 // cost[v] stores the cost by adding v to the tree
101 double [] cost = new double [getSize()];
102 for ( int i = 0 ; i < cost.length; i++) {
103 cost[i] = Double.POSITIVE_INFINITY; // Initial cost
104 }
105 cost[startingVertex] = 0 ; // Cost of source is 0
106
107 int [] parent = new int [getSize()]; // Parent of a vertex
108 parent[startingVertex] = -1 ; // startingVertex is the root
109

MST from a starting vertex

initialize cost

initialize parent

double totalWeight = 0 ; // Total weight of the tree thus far

110
111 List<Integer> T = new ArrayList<>(); minimum spanning tree

112
113 // Expand T

114 while (T.size() < getSize()) {

exapnd MST
update total cost

115 // Find smallest cost v in V - T

116 int u = -1 ; // Vertex to be determined

117 double currentMinCost = Double.POSITIVE_INFINITY;

118 for ( int i = 0 ; i < getSize(); i++) {

119 if (!T.contains(i) && cost[i] < currentMinCost) {

120 currentMinCost = cost[i];

121 u = i; vertex with smallest coust

122 }
123 }
124
125

T.add(u); // Add a new vertex to T

add to tree

126 totalWeight += cost[u]; // Add cost[u] to the tree

127
128 // Adjust cost[v] for v that is adjacent to u and v in V - T

129 for (Edge e : neighbors.get(u)) {

adjust cost

130 if (!T.contains(e.v) && cost[e.v] > ((WeightedEdge)e).weight) {

131 cost[e.v] = ((WeightedEdge)e).weight;

132 parent[e.v] = u;

133 }
134 }
135 } // End of while
136
137

create an MST

return new MST(startingVertex, parent, T, totalWeight);

138 }
139
140

/** MST is an inner class in WeightedGraph */

141 public class MST extends Tree {

MST inner class