Kruskal's Algorithm

Kruskal’s algorithm builds an MST by processing edges in non-decreasing weight order, adding an edge if it connects two different trees in the growing forest. It uses a disjoint-set data structure to track components efficiently.

Algorithm

KRUSKAL(G, w):
    A = empty set
    for each vertex v in G.V:
        MAKE-SET(v)
    sort edges of G.E into non-decreasing order by weight w
    for each edge (u, v) in sorted order:
        if FIND-SET(u) != FIND-SET(v):
            A = A union {(u, v)}
            UNION(u, v)
    return A

Each vertex starts in its own set. When an edge is selected, the two sets (trees) are merged via UNION. An edge is rejected if its endpoints are already in the same set (would create a cycle).

Correctness

At any iteration, $A$ is a forest. The cut $(C_u, V \setminus C_u)$, where $C_u$ is the component containing $u$, respects $A$. Since edges are processed in non-decreasing weight, $(u, v)$ is the lightest edge crossing this cut at the time of consideration (any lighter edge would have been processed earlier and either added or rejected because its endpoints were in different components then but the same component now). By the safe-edge theorem, $(u, v)$ is safe.

Running Time

• Initialisation of $|V|$ disjoint sets: $O(|V|)$
• Sorting edges: $O(|E| \log |E|) = O(|E| \log |V|)$, since $|E| \le |V|^2$ implies $\log |E| \le 2 \log |V|$
• Processing edges: $|E|$ calls to FIND-SET and at most $|V|-1$ calls to UNION. With union-by-rank and path compression, each near $O(\alpha(|V|))$, where $\alpha$ is the inverse Ackermann function (effectively constant, $\le 4$ for any practical input)

Total: $O(|E| \log |V|)$, dominated by sorting.

Kruskal is optimal for sparse graphs where $|E| = O(|V|)$.

Worked Example

Graph with vertices $\{A, B, C, D, E, F\}$ and edges (weight):

A-B: 4,  A-C: 1,  B-C: 3,  B-D: 2
C-D: 5,  C-E: 6,  D-E: 7,  D-F: 4,  E-F: 3

Sorted edges: $(A,C,1)$, $(B,D,2)$, $(B,C,3)$, $(E,F,3)$, $(A,B,4)$, $(D,F,4)$, $(C,D,5)$, $(C,E,6)$, $(D,E,7)$.

Processing:

1. $(A,C,1)$: different sets, add. Components: $\{A,C\}, \{B\}, \{D\}, \{E\}, \{F\}$
2. $(B,D,2)$: different sets, add. Components: $\{A,C\}, \{B,D\}, \{E\}, \{F\}$
3. $(B,C,3)$: different sets, add (connects $\{A,C\}$ and $\{B,D\}$). Components: $\{A,B,C,D\}, \{E\}, \{F\}$
4. $(E,F,3)$: different sets, add. Components: $\{A,B,C,D\}, \{E,F\}$
5. $(A,B,4)$: same set (both in $\{A,B,C,D\}$), skip
6. $(D,F,4)$: different sets, add. Components: $\{A,B,C,D,E,F\}$
7. $|A| = 5 = |V| - 1$, terminate. (Remaining edges skipped.)

MST edges: $(A,C)$, $(B,D)$, $(B,C)$, $(E,F)$, $(D,F)$. Total weight: $1 + 2 + 3 + 3 + 4 = 13$.

Comparison with Prim

Aspect	Kruskal	Prim
Strategy	Forest of trees, merge by edges	Single tree, grow by vertices
Data structure	Disjoint-set	Priority queue
Complexity	$O(\lvert E \rvert \log \lvert V \rvert)$	$O(\lvert E \rvert \log \lvert V \rvert)$ (binary heap)
Best for	Sparse graphs	Dense graphs
Edge sorting required	Yes	No

Summary

Step	Detail
Sort	$O(\lvert E \rvert \log \lvert E \rvert)$
Disjoint-set ops	$\sim O(1)$ amortised each (inverse Ackermann)
Edge selection	Greedy, always picks lightest safe edge
Total	$O(\lvert E \rvert \log \lvert V \rvert)$
Termination	Stop when $\lvert A \rvert = \lvert V \rvert - 1$

Past Tripos: y2024p2q7, y2023p1q9.