1. Kruskal's Algorithm

Kruskal's algorithm finds the minimum spanning tree (MST) of a connected, undirected, weighted graph $G = (V, E, w)$. It was published by Joseph Kruskal in 1956 ¹². The algorithm is beautifully simple: sort all edges by weight, then add each edge to the MST if and only if it does not create a cycle. The cycle-check is handled in near-$O(1)$ amortised time per edge using a Union-Find (disjoint-set) data structure.

1.1 Problem Statement

Given a connected undirected weighted graph $G = (V, E, w)$ with $w : E \to \mathbb{R}$, a spanning tree $T \subseteq E$ is a subset of edges that connects all $|V|$ vertices with exactly $|V| - 1$ edges and no cycles. The MST minimises total weight:

\[ \begin{equation} T^* = \operatorname{arg\,min}_{T \text{ spanning tree}} \sum_{e \in T} w(e) \label{eq:mst} \end{equation} \]

Variables

Symbol	Meaning
$G = (V, E, w)$	Weighted undirected graph
$T$	Set of edges in the spanning tree (grows from $\emptyset$)
$w(e)$	Weight of edge $e = (u, v)$
$\text{FIND}(v)$	Returns the representative of $v$'s component
$\text{UNION}(u, v)$	Merges the components containing $u$ and $v$
$n =	V

1.2 The Algorithm

KRUSKAL(G, w):
  T = ∅
  for each vertex v ∈ V:
    MAKE-SET(v)            // each vertex is its own component
  sort E in non-decreasing order of weight
  for each edge (u, v) ∈ E (in sorted order):
    if FIND(u) ≠ FIND(v):  // u and v are in different components
      T = T ∪ {(u, v)}
      UNION(u, v)
  return T

1.2.1 Union-Find Operations

A Union-Find (disjoint-set) data structure supports three operations:

MAKE-SET(v): creates a singleton set $\{v\}$.
FIND(v): returns the canonical representative of $v$'s set.
UNION(u, v): merges the sets containing $u$ and $v$.

With union by rank and path compression, the amortised cost per operation is $O(\alpha(n))$ where $\alpha$ is the inverse Ackermann function — effectively $O(1)$ for all practical $n < 10^{80}$ ¹.

1.3 Correctness: Cut Property

Kruskal's correctness rests on the cut property of MSTs:

Let $S \subset V$ be any strict subset of vertices and $(S, V \setminus S)$ the induced cut. If $e^* = (u, v)$ is the minimum-weight edge crossing the cut, then $e^*$ belongs to some MST.

Proof: suppose $e^*$ is not in MST $T$. Adding $e^*$ to $T$ creates a cycle; the cycle must contain another edge $e'$ crossing the cut. Since $w(e^*) \leq w(e')$, replacing $e'$ with $e^*$ gives a spanning tree of cost $\leq \text{cost}(T)$, so $T$ was not minimum — contradiction.

At each step Kruskal selects the minimum-weight edge that crosses some cut (the cut induced by the component containing $u$ vs. all other components). By the cut property this edge belongs to an MST.

1.4 Complexity

Step	Cost
Initialise Union-Find	$O(V)$
Sort edges	$O(E \log E)$
$E$ FIND/UNION operations	$O(E \alpha(V)) \approx O(E)$
Total	$O(E \log E)$

Since $E \leq V^2$, we have $\log E \leq 2 \log V$, so $O(E \log E) = O(E \log V)$.

For dense graphs ($E \approx V^2$), Prim's algorithm with an adjacency matrix runs in $O(V^2)$, which is better than Kruskal's $O(V^2 \log V)$ in that regime. For sparse graphs ($E \approx V$), both run in $O(V \log V)$.

1.5 Comparison with Prim's Algorithm

Property	Kruskal	Prim
Approach	Global edge selection	Local edge from current tree
Data structure	Union-Find + sorted edges	Priority queue
Best for	Sparse graphs ($E \ll V^2$)	Dense graphs ($E \approx V^2$)
Complexity	$O(E \log E)$	$O((V+E) \log V)$ binary heap
Parallelisable	Yes (parallel sorting)	Harder

1.6 MST Uniqueness

The MST is unique if and only if all edge weights are distinct. When some weights are equal, there may be multiple MSTs, but Kruskal's (and Prim's) find one of them.

1.7 Applications

Network design: minimum cost to connect all nodes (telephone, power grid)
Cluster analysis: delete the heaviest MST edge to split a data set into two clusters (single-linkage clustering)
Approximation algorithms: the MST is the backbone of the 2-approximation for TSP
Image segmentation: MST-based segmentation algorithms

1.8 Interactive Demo

The canvas below visualises Kruskal's algorithm on a complete graph with 12 vertices placed on a circle. Edges are considered in sorted order; accepted MST edges turn green, rejected (cycle-forming) edges turn red. Press Play or Step.

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms. MIT Press, 4th edition, 2022. ISBN 978-0-262-04630-5. ↩↩
Jon Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley, 1st edition, 2006. ISBN 978-0-321-29535-4. ↩

Symbol	Meaning
\(G = (V, E, w)\)	Weighted undirected graph
\(T\)	Set of edges in the spanning tree (grows from \(\emptyset\))
\(w(e)\)	Weight of edge \(e = (u, v)\)
\(\text{FIND}(v)\)	Returns the representative of \(v\)'s component
\(\text{UNION}(u, v)\)	Merges the components containing \(u\) and \(v\)
$n =	V

Step	Cost
Initialise Union-Find	\(O(V)\)
Sort edges	\(O(E \log E)\)
\(E\) FIND/UNION operations	\(O(E \alpha(V)) \approx O(E)\)
Total	\(O(E \log E)\)