Minimum Spanning Tree (MST) Algorithms

Two algorithms for connecting every vertex of a weighted graph at minimum cost: Kruskal and Prim.

Connecting every node in a graph at minimum cost shows up constantly in network design, clustering, and circuit design. Minimum spanning tree (MST) algorithms solve it efficiently. They apply equally to minimizing the cost of building a communication network and to clustering data points by similarity.

What is an MST?

A minimum spanning tree is the tree that connects every vertex of a weighted connected graph while keeping the sum of the edge weights as small as possible.

Conditions

Connects every vertex (spanning)
Contains no cycle (tree)
Has minimum total weight (minimum)

An MST is therefore a minimum-weight tree that connects every vertex using $V-1$ edges.

The two main algorithms

Kruskal's algorithm

Sort all edges by weight in ascending order
Starting from the lightest edge, add it to the MST if it does not create a cycle
Stop once the MST holds $V-1$ edges

Time complexity: $O(E \log E)$ Best for: sparse graphs

Prim's algorithm

Start from an arbitrary vertex
Pick the lightest edge among those connected to the current set
Repeatedly add the minimum edge crossing from the selected set to the unselected set

Time complexity: $O(E + V \log V)$ with a priority queue Best for: dense graphs

The union-find data structure

Union-find is the heart of Kruskal's algorithm, used for cycle detection.

Union-find determines whether two elements belong to the same set and merges two sets. The find operation locates the root node while compressing the path, and the union operation attaches the smaller tree to the larger one by rank to keep the structure balanced.

python

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # path compression
    return parent[x]
 
def union(a, b):
    root_a, root_b = find(a), find(b)
    if root_a != root_b:
        if rank[root_a] < rank[root_b]:
            parent[root_a] = root_b
        elif rank[root_a] > rank[root_b]:
            parent[root_b] = root_a
        else:
            parent[root_b] = root_a
            rank[root_a] += 1

An example graph

Edge	Weight
(0,1)	10
(0,2)	6
(0,3)	5
(1,3)	15
(2,3)	4

MST result: (2,3), (0,3), (0,1) with a total weight of 19

Taking edges in weight order picks (2,3)=4 and (0,3)=5, then skips (0,2)=6 because vertices 0 and 2 already belong to the same set and adding it would form a cycle. Adding (0,1)=10 last connects all four vertices.

Python implementation

The Python version sorts edges by weight and uses union-find to detect cycles.

python

def kruskal_mst(vertices, edges):
    """
    vertices: number of vertices
    edges: list of (weight, src, dest) tuples
    """
    edges.sort(key=lambda x: x[0])
 
    parent = list(range(vertices))
    rank = [0] * vertices
 
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
 
    def union(a, b):
        root_a, root_b = find(a), find(b)
        if root_a != root_b:
            if rank[root_a] < rank[root_b]:
                parent[root_a] = root_b
            elif rank[root_a] > rank[root_b]:
                parent[root_b] = root_a
            else:
                parent[root_b] = root_a
                rank[root_a] += 1
            return True
        return False
 
    mst_weight = 0
    mst_edges = []
 
    for w, s, d in edges:
        if union(s, d):
            mst_weight += w
            mst_edges.append((s, d, w))
 
    return mst_weight, mst_edges
 
 
# Run
edges = [(10, 0, 1), (6, 0, 2), (5, 0, 3), (15, 1, 3), (4, 2, 3)]
weight, mst = kruskal_mst(4, edges)
print(f"MST total weight: {weight}")  # 19

Java implementation

The Java version makes Edge implement Comparable for sorting and puts the set operations in a UnionFind class.

java

class Edge implements Comparable<Edge> {
    int src, dest, weight;
 
    Edge(int s, int d, int w) {
        this.src = s; this.dest = d; this.weight = w;
    }
 
    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}
 
class UnionFind {
    int[] parent, rank;
 
    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
 
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }
 
    void union(int a, int b) {
        int rootA = find(a), rootB = find(b);
        if (rootA != rootB) {
            if (rank[rootA] < rank[rootB]) parent[rootA] = rootB;
            else if (rank[rootA] > rank[rootB]) parent[rootB] = rootA;
            else { parent[rootB] = rootA; rank[rootA]++; }
        }
    }
}

Go implementation

The Go version builds union-find from a struct with pointer receivers, and the union method returns a bool indicating whether the merge happened.

type Edge struct {
    src, dest, weight int
}
 
type UnionFind struct {
    parent, rank []int
}
 
func NewUnionFind(n int) *UnionFind {
    uf := &UnionFind{
        parent: make([]int, n),
        rank:   make([]int, n),
    }
    for i := 0; i < n; i++ {
        uf.parent[i] = i
    }
    return uf
}
 
func (uf *UnionFind) find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.find(uf.parent[x])
    }
    return uf.parent[x]
}
 
func (uf *UnionFind) union(a, b int) bool {
    rootA, rootB := uf.find(a), uf.find(b)
    if rootA != rootB {
        if uf.rank[rootA] < uf.rank[rootB] {
            uf.parent[rootA] = rootB
        } else if uf.rank[rootA] > uf.rank[rootB] {
            uf.parent[rootB] = rootA
        } else {
            uf.parent[rootB] = rootA
            uf.rank[rootA]++
        }
        return true
    }
    return false
}

Summary

Algorithm	Time complexity	Suited to
Kruskal	$O(E \log E)$	Sparse graphs
Prim	$O(E + V \log V)$	Dense graphs

Union-find is the core of Kruskal's algorithm, and with path compression and union by rank it runs extremely fast.

On sparse graphs with few edges, Kruskal wins because the sorting cost is small; on dense graphs with many edges, Prim wins because it grows the tree vertex by vertex. When using Kruskal, union-find handles cycle detection, running in near-constant amortized time thanks to path compression and union by rank. Both algorithms produce the same minimum total weight, so the choice comes down to edge density and input format. Either one applies directly to problems that require connecting every vertex at minimum cost, such as minimizing network cost, clustering, and circuit design.