Contents
- What is a Minimum Spanning Tree?
- How Kruskal's algorithm works
- Union-Find (Disjoint Set Union)
- Implementation
- Complexity Analysis
A Spanning Tree of a graph is a subgraph that includes all vertices and is a tree
(connected and acyclic). For a graph with V vertices, a spanning tree has exactly
V - 1 edges.
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.
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 u and v belong to different components (i.e. adding this edge does not create a cycle), add it to the MST and union the two components.
- If they already belong to the same component, skip this edge (it would create a cycle).
- Stop when the MST contains exactly V - 1 edges.
The key tool Kruskal's algorithm relies on is the Union-Find (Disjoint Set Union) data structure,
which efficiently answers "are two nodes in the same component?" and "merge two components".
Union-Find supports two operations efficiently:
- find(x) — returns the representative (root) of the component containing x.
- union(x, y) — merges the components containing x and y.
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;
}
}
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: 8
-
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.
Kruskal's algorithm is efficient for sparse graphs (few edges). For dense graphs,
Prim's algorithm may be more efficient.