Minimum Spanning Tree
A Minimum Spanning Tree (MST) is a subset of edges in a connected, weighted, undirected graph that connects all vertices without any cycles and with the lowest total edge weight.
What is an MST?
A spanning tree of a graph is a subgraph that includes all vertices and is a tree (no cycles). If the graph has weighted edges, the minimum spanning tree is the one whose edges have the smallest possible total sum.
MSTs are heavily used in network design: routing protocols, laying out electrical grids, or building cost-efficient road networks.
- Must include all V vertices
- Must have exactly V-1 edges
- Total weight is minimized
The cut property
All MST algorithms rely on the 'cut property'. If you partition the vertices of a graph into two disjoint sets, the edge with the minimum weight crossing that cut must belong to the MST.
This greedy property guarantees that if we locally pick the cheapest edge bridging two unconnected components, we will arrive at a globally optimal MST.
- Partition graph into two sets
- Cheapest crossing edge is always in the MST
- Forms the mathematical basis for greedy approaches
Kruskal and Prim build an MST
edges = sorted([(1, 0, 2), (1, 3, 4), (2, 1, 2), (3, 0, 1), (4, 2, 4)])
parent = list(range(5))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
total = 0
for w, u, v in edges:
a, b = find(u), find(v)
if a != b:
parent[a] = b
total += w
print("MST weight:", total)#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;
int main()
{
vector<array<int,3>>e=
{
{
1,0,2
}
,
{
1,3,4
}
,
{
2,1,2
}
,
{
3,0,1
}
,
{
4,2,4
}
};
sort(e.begin(),e.end());
vector<int>p=
{
0,1,2,3,4
};
function<int(int)>f=[&](int x)
{
return p[x]==x?x:p[x]=f(p[x]);
};
int s=0;
for(auto a:e)
{
int u=f(a[1]),v=f(a[2]);
if(u!=v)p[u]=v,s+=a[0];
}
cout<<"MST weight: "<<s;
}import java.util.*;
class Main
{
static int[]p=
{
0,1,2,3,4
};
static int f(int x)
{
return p[x]==x?x:(p[x]=f(p[x]));
}
public static void main(String[]z)
{
int[][]e=
{
{
1,0,2
}
,
{
1,3,4
}
,
{
2,1,2
}
,
{
3,0,1
}
,
{
4,2,4
}
};
Arrays.sort(e,(a,b)->a[0]-b[0]);
int s=0;
for(int[]a:e)
{
int u=f(a[1]),v=f(a[2]);
if(u!=v)
{
p[u]=v;
s+=a[0];
}
}
System.out.print("MST weight: "+s);
}
}weighted graph A–EMST weight: 8Run the example step by step
Uniqueness
If all edge weights in a graph are unique, there is exactly one unique Minimum Spanning Tree.
If some edges have the same weight, there might be multiple valid MSTs, but they will all share the exact same minimum total weight.
- Unique if all edge weights are distinct
- Multiple MSTs possible if weights tie
- Total minimum weight is always identical
Primary algorithms
The two most famous algorithms for finding an MST are Kruskal's Algorithm and Prim's Algorithm.
Both algorithms are greedy. Kruskal's builds the tree by sorting and picking the cheapest global edges, while Prim's grows the tree outward from a single starting vertex.
- Kruskal's Algorithm (Global edge sorting)
- Prim's Algorithm (Local tree growth)
- Both are optimal greedy algorithms
The cut property explains both algorithms
For any partition of the vertices, a lightest edge crossing that cut is safe for some minimum spanning tree. Kruskal exposes a cut between its current components; Prim exposes the cut between the growing tree and everything outside. The same theorem therefore justifies two algorithms that look operationally different.
Kruskal sorts globally and uses disjoint-set roots to reject an edge whose endpoints are already connected. Prim chooses the cheapest frontier edge with a heap. On sparse edge lists Kruskal is often convenient; adjacency lists make heap-based Prim natural.
- Safe edges cross a cut minimally
- Kruskal grows a forest
- Prim grows one connected tree
Disconnected graphs, ties, and verification
A disconnected input has no spanning tree. Kruskal naturally returns a minimum spanning forest; Prim must restart from each unvisited component if that is the desired result. A connected MST contains exactly V−1 accepted edges, which is a useful implementation assertion.
Distinct weights guarantee a unique MST, but equal weights can admit several equally light trees. Do not reject equal-weight candidates merely because another equal edge was considered first; reject only edges that create a cycle. Sum weights in a type wide enough for V−1 edges.
- Connected MST has V−1 edges
- Ties can create multiple valid MSTs
- Cycle rejection preserves a tree
Validation and disconnected inputs
A finished spanning tree on V vertices must contain exactly V−1 accepted edges, connect every vertex, and contain no cycle. Kruskal can detect a disconnected input when the sorted edge list ends before V−1 unions; its result is then a minimum spanning forest. Prim likewise needs a restart in every unvisited component if a forest is desired, rather than silently returning only the component containing its starting vertex.
Negative edge weights are completely valid for an MST because the objective is a fixed set of V−1 edges, not an unrestricted walk that could repeat a negative cycle. Equal weights may produce several different trees with the same minimum cost. Test bridges, parallel edges, equal-weight ties, isolated vertices, and an edge that appears attractive but must be rejected because its endpoints already share a component. The rejected edge is the clearest visible proof of Kruskal's cycle invariant.
- Expect V−1 edges only when connected
- Negative weights are allowed
- Different trees may share the optimum cost