A 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.

## Top comments (0)