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 connects every vertex of a weighted connected graph. It has the smallest possible sum of edge weights.
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 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 edges
Time complexity: 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: with a priority queue Best for: dense graphs
The union-find data structure
Kruskal's algorithm uses union-find to detect cycles.
Union-find determines whether two elements belong to the same set and merges sets. The find operation locates the root and compresses the path. The union operation attaches the smaller tree to the larger one by rank to maintain balance.
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] += 1An example graph
graph LR
A((A)) ---|1| B((B))
B ---|2| C((C))
A ---|4| C
C ---|3| D((D))
B ---|5| D| 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
In weight order, the algorithm selects (2,3)=4 and (0,3)=5. It skips (0,2)=6 because vertices 0 and 2 already belong to the same set. Adding that edge would create a cycle. Finally, (0,1)=10 connects all four vertices.
Python implementation
The Python version sorts edges by weight and uses union-find to detect cycles.
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}") # 19Java implementation
The Java version makes Edge implement Comparable for sorting and puts the set operations in a UnionFind class.
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 implements union-find with a struct and pointer receivers. The union method returns a bool that indicates whether it merged the sets.
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 | Sparse graphs | |
| Prim | Dense graphs |
Union-find is the core of Kruskal's algorithm, and with path compression and union by rank it runs extremely fast.
Kruskal suits sparse graphs because sorting relatively few edges has a small cost. Prim suits dense graphs because it expands the tree vertex by vertex. Kruskal uses union-find for cycle detection. Path compression and union by rank give near-constant amortized operation time.
Both algorithms produce the same minimum total weight. Choose based on edge density and input format. Applications include network cost minimization, clustering, and circuit design.