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

5. Add vertex 2 to T , since Edge(2, 6, 5) has the smallest weight among all edges
incident to a vertex in T , as shown in Figure 29.7d.

6. Add vertex 4 to T , since Edge(4, 6, 7) has the smallest weight among all edges
incident to a vertex in T , as shown in Figure 29.7e.

7. Add vertex 3 to T , since Edge(3, 2, 8 ) has the smallest weight among all edges
incident to a vertex in T , as shown in Figure 29.7f.

Note
A minimum spanning tree is not unique. For example, both (c) and (d) in Figure 29.5
are minimum spanning trees for the graph in Figure 29.5a. However, if the weights are
distinct, the graph has a unique minimum spanning tree.

unique tree?

Note
Assume that the graph is connected and undirected. If a graph is not connected or
directed, the algorithm will not work. You can modify the algorithm to find a spanning
forest for any undirected graph. A spanning forest is a graph in which each connected
component is a tree.

connected and undirected

29.4.2 Refining Prim's MST Algorithm
To make it easy to identify the next vertex to add into the tree, we use cost[v] to store the
cost of adding a vertex v to the spanning tree T . Initially cost[s] is 0 for a starting vertex
and assign infinity to cost[v] for all other vertices. The algorithm repeatedly finds a vertex
u in V - T with the smallest cost[u] and moves u to T . The refined version of the alogrithm
is given in Listing 29.5.

L ISTING 29.5

Refined Version of Prim's Algorithm
Input: A connected undirected weighted G = (V, E) with non-negative weights
Output: a minimum spanning tree with the starting vertex s as the root

1 MST getMinimumSpanngingTree(s) {
2 Let T be a set that contains the vertices in the spanning tree;
3 Initially T is empty;
4 Set cost[s] = 0 ; and cost[v] = infinity for all other vertices in V;
5
6 while (size of T < n) {
7 Find u not in T with the smallest cost[u];
8 Add u to T;
9 for (each v not in T and (u, v) in E)
10 if (cost[v] > w(u, v)) { // Adjust cost[v]
11 cost[v] = w(u, v); parent[v] = u;
12 }
13 }
14 }

find next vertex
add a vertex to T

adjust cost[v]

29.4.3 Implementation of the MST Algorithm
The getMinimumSpanningTree(int v) method is defined in the WeightedGraph class.
It returns an instance of the MST class, as shown in Figure 29.4. The MST class is defined
as an inner class in the WeightedGraph class, which extends the Tree class, as shown in
Figure 29.8. The Tree class was shown in Figure 28.11. The MST class was implemented in
lines 141-153 in Listing 29.2.

getMinimumSpanningTree()