Paul NgugiA minimum spanning tree of a graph is a spanning tree with the minimum total weights.
A graph may have many spanning trees. Suppose that the edges are weighted. A minimum spanning tree has the minimum total weights. For example, the trees in Figures below b, c, d are spanning trees for the graph in Figure a. The trees in Figures c and d are minimum spanning trees.
The problem of finding a minimum spanning tree has many applications. Consider a company with branches in many cities. The company wants to lease telephone lines to connect all the branches together. The phone company charges different amounts of money to connect different pairs of cities. There are many ways to connect all branches together. The cheapest way is to find a spanning tree with the minimum total rates.
Minimum Spanning Tree Algorithms
How do you find a minimum spanning tree? There are several well-known algorithms for doing so. This section introduces Prim’s algorithm. Prim’s algorithm starts with a spanning tree T that contains an arbitrary vertex. The algorithm expands the tree by repeatedly adding a vertex with the lowest-cost edge incident to a vertex already in the tree. Prim’s algorithm is a greedy algorithm, and it is described in code below.
Input: A connected undirected weighted G = (V, E) with non-negative weights
Output: MST (a minimum spanning tree)
1 MST minimumSpanningTree() {
2 Let T be a set for the vertices in the spanning tree;
3 Initially, add the starting vertex to T;
4
5 while (size of T < n) {
6 Find u in T and v in V – T with the smallest weight
7 on the edge (u, v), as shown in Figure 29.6;
8 Add v to T and set parent[v] = u;
9 }
10 }
The algorithm starts by adding the starting vertex into T. It then continuously adds a vertex (say v) from V – T into T. v is the vertex that is adjacent to the vertex in T with the smallest weight on the edge. For example, there are five edges connecting vertices in T and V – T as shown in Figure below, and (u, v) is the one with the smallest weight.
Consider the graph in Figure below. The algorithm adds the vertices to T in this order:
- Add vertex 0 to T.
- Add vertex 5 to T, since Edge(5, 0, 5) has the smallest weight among all edges incident to a vertex in T, as shown in Figure a. The arrow line from 0 to 5 indicates that 0 is the parent of 5.
- Add vertex 1 to T, since Edge(1, 0, 6) has the smallest weight among all edges incident to a vertex in T, as shown in Figure b.
- Add vertex 6 to T, since Edge(6, 1, 7) has the smallest weight among all edges incident to a vertex in T, as shown in Figure c.
- 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 d.
- 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 e.
- 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 f.
A minimum spanning tree is not unique. For example, both (c) and (d) in Figure below are minimum spanning trees for the graph in Figure a. However, if the weights are distinct, the graph has a unique minimum spanning tree.
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.
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 code below.
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 }
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 below.
The MST class is defined as an inner class in the WeightedGraph class, which extends the Tree class, as shown in Figure below.
The Tree class was shown in Figure below. The MST class was implemented in lines 141–153 in WeightedGraph.java.
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 vertices (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:
- Find the vertex u with the smallest cost[u] (lines 118–123 and add it into T (line 125).
- 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.contains(i) takes O(n) time, since T is a list. Therefore, the overall time complexity for this implemention is O(n3).
The code below gives a test program that displays minimum spanning trees for the graph in Figure below and the graph in Figure below a, respectively.
package demo;
public class TestMinimumSpanningTree {
public static void main(String[] args) {
String[] vertices = {"Seattle", "San Francisco", "Los Angeles", "Denver", "Kansas City", "Chicago", "Boston", "New York", "Atlanta", "Miami", "Dallas", "Houston"};
int[][] edges = {
{0, 1, 807}, {0, 3, 1331}, {0, 5, 2097},
{1, 0, 807}, {1, 2, 381}, {1, 3, 1267},
{2, 1, 381}, {2, 3, 1015}, {2, 4, 1663}, {2, 10, 1435},
{3, 0, 1331}, {3, 1, 1267}, {3, 2, 1015}, {3, 4, 599}, {3, 5, 1003},
{4, 2, 1663}, {4, 3, 599}, {4, 5, 533}, {4, 7, 1260}, {4, 8, 864}, {4, 10, 496},
{5, 0, 2097}, {5, 3, 1003}, {5, 4, 533}, {5, 6, 983}, {5, 7, 787},
{6, 5, 983}, {6, 7, 214},
{7, 4, 1260}, {7, 5, 787}, {7, 6, 214}, {7, 8, 888},
{8, 4, 864}, {8, 7, 888}, {8, 9, 661}, {8, 10, 781}, {8, 11, 810},
{9, 8, 661}, {9, 11, 1187},
{10, 2, 1435}, {10, 4, 496}, {10, 8, 781}, {10, 11, 239},
{11, 8, 810}, {11, 9, 1187}, {11, 10, 239}
};
WeightedGraph<String> graph1 = new WeightedGraph<>(vertices, edges);
WeightedGraph<String>.MST tree1 = graph1.getMinimumSpanningTree();
System.out.println("Total weight is " + tree1.getTotalWeight());
tree1.printTree();
edges = new int[][]{
{0, 1, 2}, {0, 3, 8},
{1, 0, 2}, {1, 2, 7}, {1, 3, 3},
{2, 1, 7}, {2, 3, 4}, {2, 4, 5},
{3, 0, 8}, {3, 1, 3}, {3, 2, 4}, {3, 4, 6},
{4, 2, 5}, {4, 3, 6}
};
WeightedGraph<Integer> graph2 = new WeightedGraph<>(edges, 5);
WeightedGraph<Integer>.MST tree2 = graph2.getMinimumSpanningTree(1);
System.out.println("\nTotal weight is " + tree2.getTotalWeight());
tree2.printTree();
}
}
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 above in line 27. It then invokes getMinimumSpanningTree() (line 28) to return an MST that represents a minimum spanning 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 below. The vertices 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.
