Initialize Union-Find: each vertex is its own component
MST = empty set
for each edge (u,v,w) in E' (sorted order):
if FIND(u) != FIND(v): // different components
MST.add((u,v,w))
UNION(u, v) // merge components
if |MST| == V-1: break // MST complete
return MST // V-1 edges, minimum total weight
§2 — The Idea, Step by Step
Start — the cheapest way to connect everything. Imagine you must wire up several houses on a street with internet cable, or pave roads so every town can reach every other town. You don't need a cable between every single pair — you just need everything connected, and you're on a budget, so you want the least total length of cable. That cheapest "everything-is-connected, no wasted loops" network is called a Minimum Spanning Tree (MST). Kruskal's algorithm is a wonderfully simple recipe for finding it: always grab the cheapest leftover cable that connects two parts not already joined.
Build — name the pieces and try a number. Picture the map as a graph: each town is a vertex (there are $V$ of them), each possible road is an edge with a weight $w$ (its cost or length), and there are $E$ edges in all. A spanning tree links all $V$ towns using exactly $V-1$ roads and no loops. Kruskal's recipe: sort every road cheapest-first, then walk down the list and keep a road only if it joins two towns not yet connected. Worked example with towns A, B, C and roads A–B$=4$, B–C$=2$, A–C$=5$. Sorted: $2, 4, 5$. Take B–C ($2$); take A–B ($4$) — now all three are connected with $V-1=2$ edges, total $6$. Skip A–C ($5$): A and C are already linked, so adding it would just make a wasteful loop. MST cost $=6$, beating $2+5=7$ or $4+5=9$.
Deepen — why greedy is safe, and how fast. The guarantee is the Cut Property: split the vertices into any two groups; the cheapest edge crossing that split belongs to some MST. Every time Kruskal adds the globally cheapest edge joining two still-separate components, it is picking exactly such a safe edge. The "already connected?" test is answered by a Union-Find (disjoint-set) structure: $\text{FIND}(u)\neq\text{FIND}(v)$ means different components, then $\text{UNION}$ merges them — amortized nearly $O(1)$ with path compression and union by rank. So the running time is dominated by the initial sort: $O(E \log E)$, which equals $O(E \log V)$ since $E \le V^2$. If the graph is disconnected, you get a spanning forest — one tree per component, with fewer than $V-1$ edges total.
Try this in the sim above. The animation shows Kruskal's first and most expensive step — sorting the edge weights. Pick the Reverse preset and press Play: watch the weights climb into non-decreasing order, exactly the order Kruskal then scans. Drag n higher and compare the Comparisons counter — more edges cost more to sort, which is why $O(E \log E)$ dominates. Then choose the Sorted preset: the list is already cheapest-first, so almost no swaps happen and the scan can sweep through in one pass.
§3 — Algorithm Analysis & Derivation
Symbol
Meaning
n
Input size (vertices V, edges E, or array length)
T(n)
Time complexity function
W(n)
Worst-case complexity
A(n)
Average-case complexity
h
Height or depth of structure
k
Number of distinct values / items
Step 1 -- Greedy Strategy. Process edges in non-decreasing weight order. Add edge if and only if it does not create a cycle (i.e., endpoints in different components). This greedy choice is justified by the Cut Property: the minimum weight edge crossing any cut belongs to some MST.
Step 2 -- Correctness via Cut Property. The Cut Property: for any cut (S, V-S) of the graph, the minimum weight edge crossing the cut is in some MST. Kruskal's algorithm always adds the minimum weight edge that connects two previously separate components -- exactly the Cut Property.
Step 3 -- Time Complexity. Sorting E edges: O(E log E). E Union-Find operations: O(E alpha(V)) ~ O(E). Total: O(E log E). Since E <= V^2, log E <= 2 log V, so O(E log E) = O(E log V).
Step 4 -- Union-Find with Path Compression + Union by Rank. FIND with path compression: amortized O(alpha(V)) per operation where alpha is inverse Ackermann (essentially O(1)). UNION by rank: merge smaller tree under larger. Together: nearly-O(1) per operation.
Step 5 -- Output. MST has exactly V-1 edges (a tree). Total weight is minimum among all spanning trees. If graph is disconnected, algorithm finds Minimum Spanning Forest (one tree per connected component).
Step 6 -- vs Prim's Algorithm. Kruskal: sort edges globally, better for sparse graphs O(E log E). Prim: grow tree from a start vertex, better for dense graphs O(V^2) with array or O(E log V) with heap. Both give MST. Kruskal naturally parallelizes better.
§4 — Frequently Asked Questions
What is a Minimum Spanning Tree? concept+
A spanning tree of a connected graph connects all V vertices with V-1 edges and no cycles. The MST is the spanning tree with minimum total edge weight. May not be unique (if edge weights are not distinct). Used for network design, clustering, approximation algorithms.
Why does the greedy approach work for MST? concept+
The Cut Property guarantees it. For any partition of vertices into two sets S and V-S, the cheapest edge crossing the cut belongs to some MST. Kruskal always picks the globally cheapest safe edge -- safe meaning it doesn't create a cycle within an existing component.
Where is MST used in practice? applied+
Network design (cheapest cable layout connecting cities). Cluster analysis (cut heaviest MST edges to find clusters). Approximation algorithms (MST-based 2-approximation for TSP). Image segmentation. Circuit design. Distributed systems minimum communication trees.
What is the Union-Find data structure? concept+
Union-Find (Disjoint Set Union) maintains a partition of elements into disjoint sets. FIND(x): find the root/representative of x's set. UNION(x,y): merge the sets containing x and y. With path compression + union by rank: amortized O(alpha(n)) per operation, essentially O(1).
What if the graph has equal weight edges? nonobv+
If multiple edges have the same weight, different tie-breaking can produce different MSTs (all valid). If you need a UNIQUE MST, add small perturbations. Kruskal handles ties correctly -- any tie-breaking gives a valid MST.
How does Kruskal's relate to cycle detection? deep+
Kruskal's is essentially: sort edges, add edge if it doesn't create a cycle. Union-Find is used to detect cycles in O(alpha(V)) per check. Alternative: use DFS for cycle detection but that's O(V) per edge = O(EV) total -- much worse. Union-Find makes Kruskal efficient.
§5 — Common Misconceptions & Errors
Conceptual Misconceptions
✗ Kruskal's MST is unique.
✓ MST is unique only if all edge weights are distinct. Equal weights can give multiple valid MSTs.
✗ Kruskal always selects V edges for a V-vertex graph.
✓ MST has exactly V-1 edges (one less than vertices). The algorithm terminates when V-1 edges are added.
✗ Kruskal works on directed graphs.
✓ Kruskal (and Prim) find Minimum Spanning TREES, defined for undirected graphs. For directed graphs, the problem is Minimum Spanning Arborescence, solved by Edmonds' algorithm (Chu-Liu/Edmonds).
Implementation Errors
✗ Using DFS for cycle detection instead of Union-Find.
✓ DFS cycle check: O(V) per edge = O(EV) total. Union-Find: O(E alpha(V)). For E=10^5, V=10^4: DFS is 10^9 operations, Union-Find is ~5*10^5. Always use Union-Find in Kruskal.
✗ Sorting edges by weight is optional.
✓ Sorting is ESSENTIAL. Processing edges in wrong order may add heavy edges when lighter options exist for the same connection.
✗ Forgetting to check if graph is connected before claiming MST.
✓ If graph is disconnected, Kruskal produces a Minimum Spanning FOREST (one tree per component), not a single MST. Check if |MST edges| == V-1; if not, graph is disconnected.