Kruskal's Algorithm Theory

Problem

Given a connected, undirected, weighted graph, find a subset of edges forming a spanning tree of minimum total weight. For disconnected graphs, Kruskal yields a minimum spanning forest.

Cut Property

• For any partition (cut) of vertices, the minimum-weight edge crossing that cut is safe to add to some MST.
• Kruskal simulates picking globally safe edges by scanning weights in order.

Disjoint Set Union (DSU)

Efficiently maintains components as edges are added.

• make-set(x): Initialize singleton.
• find(x): Return representative (with path compression).
• union(a,b): Merge roots (union by rank/size).
• Amortized near-constant: α(n) (inverse Ackermann).

Pseudocode

1KRUSKAL(G=(V,E), w):
2  sort E by non-decreasing w
3  make-set(v) for each v in V
4  MST ← ∅
5  for each (u,v) in E (in order):
6    if find(u) ≠ find(v):
7      MST ← MST ∪ {(u,v)}
8      union(u,v)
9    // else discard (cycle)
10  return MST

Complexity

Since m ≤ n^2, log m = O(log n). Sorting dominates for typical implementations.

Correctness Sketch

• Invariant: chosen edges always form a forest.
• Each added edge is safe by cut property (it’s the minimum crossing some cut).
• When |T| = n−1 edges, forest is connected ⇒ an MST.

Edge Cases

• Disconnected: Produces minimum spanning forest (one per component).
• Duplicate Weights: Any order among equal weights still yields an MST.
• Negative Weights: Fully supported; sorting handles them.