Kruskal’s Algorithm

Kruskal’s algorithm (1956) builds the MST by processing edges in order of increasing weight. At each step it asks: does adding this edge create a cycle? If not, add it; if yes, skip it.

This is a direct application of the cut property. When Kruskal’s adds edge (u, v), the two connected components containing u and v form a natural cut. The edge being considered is the lightest crossing edge for that cut (since all cheaper edges were already processed). By the cut property, it’s safe.

The algorithm

Sort all edges by weight

E.g., for a graph with edges:

(A,B,4), (A,C,2), (B,C,1), (B,D,5), (C,E,8), (D,E,2), (D,F,6), (E,F,3)

Sorted: (B,C,1), (A,C,2), (D,E,2), (E,F,3), (A,B,4), (B,D,5), (D,F,6), (C,E,8)

Initialize Union-Find on all vertices

Each vertex starts in its own component.

Process edges in sorted order

For each edge (u, v, w):

If find(u) != find(v) → different components → adding (u,v) won’t form a cycle → add it, union(u, v).
If find(u) == find(v) → same component → adding (u,v) would form a cycle → skip.

Stop when n − 1 edges have been added

The MST is complete.

Worked example

Graph: 6 vertices A–F, edges as above.

Step	Edge	Weight	Action	MST edges
1	(B,C)	1	Add	B-C
2	(A,C)	2	Add	B-C, A-C
3	(D,E)	2	Add	B-C, A-C, D-E
4	(E,F)	3	Add	B-C, A-C, D-E, E-F
5	(A,B)	4	Skip — A and B are already connected via C	no change
6	(B,D)	5	Add — connects A-B-C to D-E-F	B-C, A-C, D-E, E-F, B-D
7	—	—	5 edges added, n−1=5, stop	MST complete

Total weight: 1 + 2 + 2 + 3 + 5 = 13.

MST edges highlighted (total weight 13) — {B-C, A-C, D-E, E-F, B-D}

6 nodes · 8 edges · weighted

Implementation

Correctness

At every step, the edge added by Kruskal’s satisfies the cut property:

Let S = the component containing u (before the union).
Let V − S = everything else (includes v’s component).
The edge (u, v) is the lightest crossing edge for this cut — all lighter edges were already processed, and since none of them connected u’s component to v’s component (they were either inside a single component or already added), (u, v) is cheapest.
By the cut property, (u, v) is in some MST. Since we greedily add the globally cheapest safe edge at each step, the result is the MST.

Complexity

Phase	Time	Space
Sort edges	O(E log E)	O(E)
Union-Find operations	O(E α(V)) ≈ O(E)	O(V)
Total	O(E log E)	O(V + E)

α is the inverse Ackermann function — effectively constant (≤ 5 for any realistic input). The sort dominates. Note that O(E log E) = O(E log V) because E ≤ V² so log E ≤ 2 log V.

When to use Kruskal’s

Kruskal’s is optimal for sparse graphs where E ≈ V:

Road networks (roughly planar — E ≈ 3V by Euler’s formula)
Network cable layout with a given list of possible connections
When edges are given as a list (not an adjacency matrix)

For dense graphs where E ≈ V², Prim’s with an adjacency matrix is faster: O(V²) vs Kruskal’s O(E log E) = O(V² log V).

⚠️

The disconnected-graph case. If the graph isn’t connected, no spanning tree exists. Kruskal’s will process all edges and end up with edgesAdded < n − 1. Always check this! In MST problems framed as “minimum cost to connect all nodes,” an impossible case means the graph has multiple connected components that can’t be bridged with the given edges.

Kruskal’s for minimum spanning forest

If the graph isn’t connected, Kruskal’s naturally builds a minimum spanning forest — one MST for each connected component. Just remove the edgesAdded == n - 1 early exit condition.

Quick check

In Kruskal's algorithm, why does Union-Find's 'find' operation correctly detect cycle formation?

Kruskal's processes edges sorted by weight. What happens if two edges have the same weight and we process them in either order?

Next: Prim’s algorithm — the priority-queue alternative that grows the MST vertex by vertex from a starting node.

Introduction Prim's Algorithm