Minimum Spanning Tree (MST)

Prerequisite Concepts

What is a Spanning Tree?

A Spanning Tree is a tree formed from a connected graph that contains all the vertices of the original graph but only enough edges to keep them connected.

If a graph contains V vertices, every spanning tree contains exactly:

A spanning tree must satisfy two important conditions:

• It must contain all vertices.
• It must not contain any cycle.

A connected graph can have more than one spanning tree. When edge weights are present, these different spanning trees may have different total costs.

Spanning Tree Illustration

The following figure shows the difference between a weighted graph, a spanning tree, and a minimum spanning tree.

Figure 1: Graph, Spanning Tree and Minimum Spanning Tree

Understanding Spanning Tree with a Simple Example

Consider a graph containing four vertices:

Suppose the graph has the following edges:

Since there are 4 vertices, a spanning tree must contain:

For example, the following three edges form a spanning tree:

All four vertices are connected and no cycle is formed. Therefore, these three edges form a spanning tree.

What is a Minimum Spanning Tree?

A graph may contain several different spanning trees. The Minimum Spanning Tree is the spanning tree whose total edge weight is minimum among all possible spanning trees of the graph.

For a graph having V vertices, an MST contains exactly V − 1 edges.

Spanning Tree vs Minimum Spanning Tree

Important Properties of MST

Why Can We Not Simply Select the Smallest Edges?

We cannot simply select the smallest edges without checking whether they create a cycle.

For example, suppose the three smallest edges are:

Selecting all three edges creates the cycle:

Therefore, the third edge must be rejected because a tree cannot contain a cycle.

How is an MST Constructed?

A Minimum Spanning Tree can be constructed using greedy algorithms.

The two most important algorithms used for constructing an MST are:

1. Prim's Algorithm
2. Kruskal's Algorithm

Prim's Algorithm

Prim's Algorithm is a greedy algorithm that starts with one vertex and gradually grows a single tree until all vertices are included.

At every step, Prim's Algorithm selects the minimum-weight edge that connects a vertex already inside the tree to a vertex outside the tree.

Basic Idea of Prim's Algorithm

1. Choose any starting vertex.
2. Put the starting vertex into the MST.
3. Look at all edges going from the current MST to unvisited vertices.
4. Select the edge having the smallest weight.
5. Add the selected vertex and edge to the MST.
6. Repeat until all vertices are included.

Prim's Algorithm — Step-by-Step Example

Consider the following weighted graph:

Step 1: Start with A

Start Prim's Algorithm from vertex A.

The minimum edge is A − C = 2.

Select A − C.

Step 2: Current MST = {A, C}

The smallest edge is C − D = 1.

Select C − D.

Step 3: Current MST = {A, C, D}

The smallest available edge is D − E = 2.

Select D − E.

Step 4: Add B

The remaining unvisited vertex is B.

The smallest edge is C − B = 3.

Select C − B.

Final MST using Prim's Algorithm

Figure 2: Prim's Algorithm — Step-by-Step Selection

Prim's Algorithm Pseudocode

Prim(G):

1. Choose any starting vertex
2. Mark the starting vertex as visited

3. Repeat until V - 1 edges are selected:

       Find the minimum-weight edge
       connecting a visited vertex
       to an unvisited vertex

       Add that edge to MST
       Mark the new vertex as visited

4. Return MST

Kruskal's Algorithm

Kruskal's Algorithm is another greedy algorithm used to find a Minimum Spanning Tree.

Unlike Prim's Algorithm, Kruskal's Algorithm does not start from a particular vertex. Instead, it considers edges in increasing order of their weights.

Basic Idea of Kruskal's Algorithm

1. List all edges of the graph.
2. Sort the edges in increasing order of weight.
3. Select the smallest edge.
4. Check whether adding the edge creates a cycle.
5. If no cycle is formed, add the edge to the MST.
6. If a cycle is formed, reject the edge.
7. Continue until V − 1 edges have been selected.

Kruskal's Algorithm — Step-by-Step Example

Consider the following graph:

Step 1: Sort All Edges

Step 2: Select A − D

The smallest edge is A − D = 1. No cycle is possible because this is the first selected edge.

Selected.

Step 3: Select A − C

The next smallest edge is A − C = 2. Adding it does not create a cycle.

Selected.

Step 4: Check C − D

The next edge is C − D = 3.

But A, C and D are already connected through:

A → C → D → A

Therefore, adding C − D would create a cycle.

Step 5: Select A − B

The next edge is A − B = 4. B is not yet connected to the existing tree, so adding this edge does not create a cycle.

Selected.

Now all four vertices are connected and the MST contains:

V − 1 = 4 − 1 = 3 edges

Final MST using Kruskal's Algorithm

Figure 3: Kruskal's Algorithm — Edge Selection and Cycle Rejection

Kruskal's Algorithm Pseudocode

Kruskal(G):

1. Sort all edges in increasing order of weight

2. Initialize MST as an empty set

3. For each edge (u, v) in sorted order:

       If adding (u, v) does not create a cycle:
            Add (u, v) to MST

       If MST contains V - 1 edges:
            Stop

4. Return MST

Cycle Detection in Kruskal's Algorithm

The main challenge in Kruskal's Algorithm is determining whether adding an edge will create a cycle.

The standard data structure used for this purpose is called Disjoint Set Union (DSU), also known as Union-Find.

If both endpoints of an edge already belong to the same component, adding that edge would create a cycle, so the edge is rejected.

Complete Solved Example — MST

Consider the following weighted graph:

Sorted Edge Table

Step-by-Step Selection

Now all five vertices are connected and the MST contains exactly four edges.

Cut Property of MST

The Cut Property is an important theoretical property of Minimum Spanning Trees.

Suppose the vertices of a graph are divided into two groups. This division is called a cut. Among the edges crossing the cut, a minimum-weight edge is a safe choice for constructing an MST.

Cycle Property of MST

The Cycle Property states that a strictly heaviest edge in a cycle cannot belong to an MST.

This principle helps explain why Kruskal's Algorithm rejects an edge when adding it would produce a cycle and a lower-weight connection is already available.

Can an MST be Unique?

Yes. An MST can be unique.

If all edge weights in a connected graph are distinct, the MST is unique.

If some edge weights are equal, a graph may have multiple different MSTs with the same minimum total weight.

Number of Edges in MST

Time Complexity

Space Complexity

Applications of Minimum Spanning Tree

Advantages of MST

• Minimizes the total cost of connecting all vertices.
• Connects every vertex.
• Does not contain unnecessary cycles.
• Provides an efficient structure for network design.
• Prim's and Kruskal's algorithms can construct MST efficiently.

Limitations of MST

• A standard MST requires an undirected weighted graph.
• A single MST exists only when the graph is connected.
• MST minimizes total edge cost but does not automatically optimize other factors such as traffic, latency or reliability.
• A change in edge weights can change the resulting MST.

Prim's Algorithm vs Kruskal's Algorithm

Summary

A Minimum Spanning Tree is a spanning tree of a connected weighted undirected graph with the minimum possible total edge weight. It contains all vertices, exactly V − 1 edges, and no cycle.

The two most important algorithms for finding an MST are Prim's Algorithm and Kruskal's Algorithm. Prim's Algorithm starts from a vertex and continuously expands a single tree by selecting the minimum-weight edge connecting the tree to a new vertex. Kruskal's Algorithm sorts all edges by weight and adds the smallest edge whenever it does not create a cycle.