Kruskal's Algorithm

Definition

Kruskal's Algorithm

Let $G=(V,E)$ be a finite, connected, undirected graph with edge weights $w:E\to \mathbb{R}$. Kruskal’s algorithm is a greedy algorithm that constructs a minimum spanning tree: a tree spanning all vertices and minimising
$w(T)={\sum }_{e\in T}w(e).$

Starting with the forest $F=\varnothing$, scan the edges in non-decreasing weight order. For each edge $e=\{u,v\}$,

$$\text{accept }e⟺C_F(u)\ne C_F(v),$$

where $C_F(v)$ is the component containing $v$ in $(V,F)$. Accepting means adding $e$ to $F$: two trees merge into one. An edge within one tree is rejected because it would create a cycle.

Solid cyan edges belong to $F$; the dashed orange edge is under consideration.

Disconnected graphs and tied weights

On a disconnected network, the same procedure returns a minimum spanning forest: one minimum spanning tree per connected component. Equal-weight edges may be processed in any order; different orders can produce different optimal forests.

Algorithm

A union-find data structure stores the components of $(V,F)$. Its sets represent connectivity, not the actual edges of the output tree; those edges are stored separately in $F$.

Kruskal(V, E, w):
    F ← ∅
    for each vertex v in V:
        MakeSet(v)
 
    for each edge {u, v} in E, sorted by non-decreasing weight:
        ru ← Find(u)
        rv ← Find(v)
        if ru ≠ rv:
            F ← F ∪ {{u, v}}
            Union(ru, rv)
 
    return F

For a connected graph, the scan may stop as soon as $|F|=|V|-1$. Negative weights need no special treatment: only the order of weights matters.

Correctness

Forest invariant

After every processed edge, $F$ is acyclic and is contained in some minimum spanning tree of $G$. Consequently, on a connected graph, Kruskal’s algorithm returns a minimum spanning tree.

Proof

Initially, $F=\varnothing$ is contained in every spanning tree. Rejecting an edge leaves the invariant unchanged. Suppose the next accepted edge is $e=\{u,v\}$.

The accepted edge is cheapest across a component boundary

Let $S=C_F(u)$. Since $v\notin S$, adding $e$ merges two components and cannot create a cycle.

Every edge crossing from $S$ to $V\setminus S$ was also between different components earlier: components only merge. If such an edge had already been processed, it would have been accepted, contradicting the current boundary of $S$.

Therefore no crossing edge was processed before $e$. By the sorted order,
$w(e)\le w(f)\text{for every edge }f\text{ crossing this boundary}.$

Exchange an edge without increasing the weight

By the invariant, choose a minimum spanning tree $T$ containing $F$. If $e\in T$, nothing needs to be changed. Otherwise, the unique $u$–$v$ path in $T$ crosses the boundary of $S$ through some edge $f$.

The solid path illustrates the $u$–$v$ path in $T$. Adding $e$ closes a cycle; removing $f$ breaks that cycle while preserving connectivity. Moreover, $f\notin F$, since no edge of $F$ crosses its own component boundary. Hence

$$\begin{array}{rl}{T}^{\prime }& =(T\setminus \{f\})\cup \{e\},\\ F\cup \{e\}& \subseteq T^{\prime },\\ w(T^{\prime })& =w(T)-\underset{\text{removed}}{\underbrace{w(f)}}+\underset{\text{added}}{\underbrace{w(e)}}\le w(T).\end{array}$$

Since $T$ was already minimum, $T^{\prime }$ is minimum too. This preserves the invariant.

The final forest spans the graph

If two components remained after the scan, connectivity of $G$ would provide an edge between final components. Its endpoints were also separate when it was processed, so it would have been accepted: a contradiction.

Thus $F$ is a spanning tree. Since it is contained in a minimum spanning tree and both have $|V|-1$ edges, it is itself minimum. For disconnected graphs, the same argument applies separately to each connected component.

Complexity

Write $n=|V|$ and $m=|E|$. With comparison sorting and union-find using both path compression and union by rank or size:

Work	Time
Initialise $n$ singleton sets	$O(n)$
Sort $m$ edges	$O(m\log m)$
At most $2m$ finds and $n-1$ successful unions	$O(m\alpha (n))$ amortised

Here $\alpha$ is the inverse Ackermann function, which grows extremely slowly. The total is $O(n+m\log m+m\alpha (n))$, taking the sorting cost as zero for $m\le 1$.

For a connected simple graph with $n\ge 2$, $n-1\le m\le n(n-1)/2$, giving the usual $O(m\log n)$ bound. Union-find and the output forest need $O(n)$ space; storing the edge list needs $O(m)$ space, with additional sorting space depending on the implementation.

Kruskal is a natural choice for an edge-list representation, particularly for sparse graphs. It is not universally faster than Prim’s algorithm: the comparison depends on the graph representation and priority-queue implementation.

Example

Three accepted edges, then two cycle edges

Consider the edges in processing order:
$CD:1<AC:2<BC:3<AB:4<BD:5.$
Each panel shows the same graph after an acceptance. Orange edges belong to $F$; thin cyan edges have not been accepted.

The component partition changes as follows:

$$\begin{array}{rl}\text{Initially:}& \{A\},\{B\},\{C\},\{D\},\\ \text{After }CD:& \{A\},\{B\},\{C,D\},\\ \text{After }AC:& \{B\},\{A,C,D\},\\ \text{After }BC:& \{A,B,C,D\}.\end{array}$$

We may now stop: the three accepted edges form a spanning tree with total weight $1+2+3=6$.

If the scan continues, $AB$ is rejected because $A$ and $B$ are already joined by $A-C-B$. Likewise, $BD$ is rejected because the path $B-C-D$ already exists.

Further walkthrough: video explanation of Kruskal’s algorithm.