Kruskal's Minimum Spanning Tree

Greedy MST formation by selecting safe edges in non-decreasing weight order validated through Disjoint Set Union cycle tests.

Overview

Kruskal's algorithm builds a minimum spanning tree by scanning edges in non-decreasing weight order and greedily adding those that do not form a cycle (detected via Disjoint Set Union). It treats the graph as a forest that gradually merges.

Core Steps

Sort all edges by non-decreasing weight.
Initialize each vertex as its own set (DSU).
Scan edges: if endpoints are in different sets, union and add edge.
Stop after (n−1) edges added (connected graph).

Why It Works

Cut Property: The lightest edge crossing any cut belongs to some MST.
Cycle Property: The heaviest edge in any cycle is never in an MST.
Each accepted edge is safe; DSU enforces forest growth without cycles.

Complexity

Sort

O(m log m)

DSU Ops

α(n) amort.

Total

O(m log n)

Sorting dominates. With union-find path compression + union by rank, per operation is almost constant (inverse Ackermann).

Comparison

Algorithm	Best For	Approach	Time
Prim (Heap)	Dense graphs	Grow tree	O(m log n)
Kruskal	Sparse / Edge-sorted reuse	Merge forests	O(m log n)
Borůvka	Parallelizable	Component merges	O(m log n)

Quick Facts

Inventor: Joseph Kruskal (1956)
Paradigm: Greedy (safe edges)
Key Tool: Disjoint Set Union
Result: Minimum spanning forest (MST if connected)
Tie Handling: Any safe order still MST

Next Steps

Learn the cut property and DSU mechanics, then watch edges accepted/rejected in order.

Theory Simulation All Graph Algorithms

Back: floyd-warshall Next:prim's