Kruskal's Algorithm and Union-Find
DSA · Graphs
Theory
Kruskal's algorithm builds a minimum spanning tree by sorting all edges by weight and adding each edge if it does not create a cycle. It uses a union-find (disjoint set) structure to check quickly whether two vertices are already connected: find returns a set's representative and union merges two sets. With path compression and union by rank, each union-find operation is almost O(1), so Kruskal runs in O(E log E), dominated by sorting.
Why we use it
Union-find answers "are these connected?" extremely fast, and Kruskal is simple and efficient for sparse graphs.
When to use it
Use union-find for connected components, cycle detection, network connectivity, merging accounts, and Kruskal's MST.
How it works
- Sort edges by weight
- Take the next cheapest edge (u, v)
- find(u) == find(v)? Yes: Skip (would form a cycle). No: union(u, v), add edge.
- Tree has V - 1 edges? Yes: Done. No: Next edge.
Syntax
parent[x] = x initially
find(x): follow parents to the root (compress path)
union(a, b): attach one root under the other
Kruskal: sort edges; for each (u, v, w):
if find(u) != find(v): union(u, v); take edgeExample
parent = {}
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path compression
x = parent[x]
return x
def union(a, b):
ra, rb = find(a), find(b)
if ra == rb:
return False
parent[ra] = rb
return True
edges = [(1, "B", "C"), (2, "A", "B"), (3, "A", "C"), (4, "B", "D"), (5, "C", "D")]
for _, u, v in edges:
parent.setdefault(u, u); parent.setdefault(v, v)
mst, total = [], 0
for w, u, v in sorted(edges):
if union(u, v):
mst.append((u, v, w)); total += w
print("Kruskal MST:", mst, "| cost:", total)Key points
- Sort edges, add if no cycle
- Union-find tracks connected groups
- Path compression keeps finds near O(1)
- Great for sparse graphs