Graph - Kruskal's Minimum Spanning Tree (MST)
Kruskal's algorithm finds the Minimum Spanning Tree (MST) of a connected, weighted, undirected graph: the subset of edges that connects all vertices with the minimum total edge weight and no cycles. It is a greedy algorithm that builds the MST by always picking the smallest available edge that does not form a cycle.
Contents
What is a Minimum Spanning Tree?
A Spanning Tree of a graph is a subgraph that includes all vertices and is a tree
(connected and acyclic). For a graph with VV - 1
A Minimum Spanning Tree (MST) is the spanning tree whose total edge weight is minimised.
MSTs are widely used in network design problems, for example, laying cables between cities with minimum cost, designing water pipeline networks, or building computer networks.
How Kruskal's algorithm works
Kruskal's algorithm follows a greedy approach:
- Sort all edges in the graph by weight in ascending order.
- Initialise a Union-Find data structure with each vertex as its own component.
- Iterate through the sorted edges. For each edge
(u, v) - If
uv - If they already belong to the same component, skip this edge (it would create a cycle).
- Stop when the MST contains exactly
V - 1
Union-Find (Disjoint Set Union)
Union-Find supports two operations efficiently:
- find(x): returns the representative (root) of the component containing
x - union(x, y): merges the components containing
xy
With path compression and union by rank, both operations run in near-constant time O(α(n)).
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; // each node is its own root
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // path compression
}
return parent[x];
}
boolean union(int x, int y) {
int px = find(x), py = find(y);
if (px == py) return false; // already in the same component — cycle!
// Union by rank: attach smaller tree under larger tree
if (rank[px] < rank[py]) { int tmp = px; px = py; py = tmp; }
parent[py] = px;
if (rank[px] == rank[py]) rank[px]++;
return true;
}
}Implementation
The class below shows the implementation. Key points are highlighted in the inline comments.
import java.util.*;
public class Kruskal {
static class Edge implements Comparable<Edge> {
int src, dest, weight;
Edge(int src, int dest, int weight) {
this.src = src; this.dest = dest; this.weight = weight;
}
public int compareTo(Edge other) { return this.weight - other.weight; }
}
/**
* Finds the MST using Kruskal's algorithm.
* @param V number of vertices
* @param edges list of all edges in the graph
* @return list of edges in the MST
*/
public List<Edge> kruskalMST(int V, List<Edge> edges) {
Collections.sort(edges); // Step 1: sort edges by weight
UnionFind uf = new UnionFind(V);
List<Edge> mst = new ArrayList<>();
for (Edge edge : edges) {
if (uf.union(edge.src, edge.dest)) { // Step 3: add edge if no cycle
mst.add(edge);
if (mst.size() == V - 1) break; // MST complete
}
}
return mst;
}
}Example usage:
List<Kruskal.Edge> edges = new ArrayList<>();
edges.add(new Kruskal.Edge(0, 1, 4));
edges.add(new Kruskal.Edge(0, 2, 3));
edges.add(new Kruskal.Edge(1, 2, 1));
edges.add(new Kruskal.Edge(1, 3, 2));
edges.add(new Kruskal.Edge(2, 3, 4));
edges.add(new Kruskal.Edge(3, 4, 2));
Kruskal k = new Kruskal();
List<Kruskal.Edge> mst = k.kruskalMST(5, edges);
int totalWeight = 0;
for (Kruskal.Edge e : mst) {
System.out.println(e.src + " -- " + e.dest + " : " + e.weight);
totalWeight += e.weight;
}
System.out.println("Total MST weight: " + totalWeight);
// Output:
// 1 -- 2 : 1
// 1 -- 3 : 2
// 3 -- 4 : 2
// 0 -- 2 : 3
// Total MST weight: 8Complexity Analysis
- Time complexity: O(E log E). Dominated by the edge sorting step. The Union-Find operations are nearly O(1) with path compression and union by rank.
- Space complexity: O(V + E). For the Union-Find arrays and the edge list.
Note: Kruskal's algorithm is efficient for sparse graphs (few edges). For dense graphs, Prim's algorithm may be more efficient.