Kruskal's algorithm

Kruskal's algorithm constructs a minimum spanning tree of a finite connected graph with undirected edges and real edge weights. Start with all vertices and no edges, a forest of isolated vertices. Sort the edges by nondecreasing weight, then accept an edge exactly when its endpoints belong to different current connected components of a graph. Otherwise reject it: the existing graph path between its endpoints would close a graph cycle. Each acceptance merges two connected components of a graph. Stop after $|V|-1$ acceptances, when the forest has become one spanning tree.

This is a greedy algorithm for economical network connection: only the next affordable connection and the current connected components of a graph matter. Unlike Prim's algorithm, which grows one reached tree, Kruskal's algorithm can grow several separate trees before joining them. The essential safeguard is avoiding a graph cycle, rather than simply buying the cheapest fixed number of edges.

Joseph Bernard Kruskal described this rule as Construction A on page 49 of his February 1956 paper, On the shortest spanning subtree of a graph and the traveling salesman problem; page 50 gives an exchange argument for distinct weights.^[ref]

Consider this original connected graph on vertices $A,B,C,D,E$. Its undirected edges, already in increasing weight order, areHere $AB$ means the unordered pair $\{A,B\}$; the weights are dimensionless costs. Accept $AB$ and $BC$, with total $3$. Reject $AC$: its endpoints already have the graph path $A,B,C$, so it would close the graph cycle $A,B,C,A$. Accept $CD$ and $DE$, reaching all five vertices with four edges. The resulting minimum spanning tree isStop here: $CE$ and $BE$ need not be examined. If processing continued, both would be rejected because their endpoints are already in the same connected component of a graph.

Taking the three cheapest edges $AB,BC,AC$ instead gives a graph cycle on $A,B,C$, leaving $D,E$ isolated: it is neither a forest nor a spanning tree. Even taking the four cheapest edges adds only $CD$ and leaves $E$ isolated. A cheap infeasible selection cannot compete with a minimum spanning tree. For this small graph, checking all $\left(\genfrac{}{}{0ex}{}{7}{4}\right)=35$ four-edge subsets gives a direct certificate: among those that are spanning trees, exactly one has minimum cost $12$, namely $T$. The general algorithm avoids this exhaustive search.

An edge is safe for the current accepted forest $F$ if some minimum spanning tree contains both $F$ and that edge. The loop invariant is that some minimum spanning tree contains every accepted edge. It holds initially for the empty edge set. Suppose the next accepted edge $e$ joins a current connected component of a graph $S$ to its complement. No earlier rejected edge crosses this cut of a graph: once its endpoints are in one connected component of a graph, subsequent merges never separate them. Thus $e$ is a lightest edge across that cut of a graph.

For the short exchange argument, take a minimum spanning tree $T$ containing $F$. If $e$ is absent, adding it creates a fundamental cycle. This graph cycle contains another edge $f$ crossing the same cut of a graph. No edge of $F$ crosses the cut of a graph, so $f$ is not in $F$. Replace $f$ by $e$: the result is a spanning tree containing $F$ and $e$, with no greater total weight because $w(e)\le w(f)$. It is therefore also a minimum spanning tree. This is the minimum spanning tree cut property in the form needed for tied weights.

In the example, $CD$ is safe after rejecting $AC$: the current connected component of a graph $\{A,B,C\}$ has crossing edges $CD,CE,BE$ of weights $4,6,7$. Its cheapest connection is $CD$. The rejected $AC$ is also the unique heaviest edge of the graph cycle $A,B,C,A$, so the minimum spanning tree cycle property excludes it from every optimum.

Negative and zero edge weights are allowed: the comparisons and exchange argument still apply. Ties can give several minimum spanning trees, though they need not; any order among equal-weight edges remains valid. Distinct edge weights guarantee a unique minimum spanning tree. To see why, take the lightest edge $e$ belonging to exactly one of two proposed optima, say $T$. Deleting $e$ from $T$ gives a cut of a graph; the other optimum has a graph path across it, containing an edge $f$ absent from $T$. Hence $w(e)<w(f)$, and replacing $f$ by $e$ improves that other optimum, a contradiction. For disconnected input, process all edges to obtain a minimum spanning forest, one minimum spanning tree per original connected component of a graph; no spanning tree of the whole graph exists.^[ref]

A disjoint-set data structure stores the current partition of a set of vertices into connected components of a graph. The operation $\mathrm{find}(v)$ returns a representative of the block containing $v$. Two vertices are in the same block exactly when their representatives agree. For each candidate edge $uv$, compare $\mathrm{find}(u)$ and $\mathrm{find}(v)$. Equal representatives mean reject; different representatives mean accept and perform $\mathrm{union}(u,v)$, merging the two blocks. The representatives are bookkeeping choices, not preferred vertices of the minimum spanning tree.

Every acceptance reduces the connected component of a graph count by one and increases the accepted edge count by one, preserving $|F|=|V|-c$. Thus the ledger reaches $c=1$ exactly when $|F|=4$. Only ten representative queries and four merges are needed for the five examined edges, counting two queries per examination and using the already found representatives for each merge. Neither breadth-first search nor reconstruction of a graph path is needed for these connectivity queries.

For $n=|V|$ and $m=|E|$, comparison sorting algorithm takes $O(m\log m)$ time for $m\ge 2$, using Big O notation. One simple disjoint-set data structure implementation stores each block as a rooted tree and attaches the smaller block's root below the larger block's root. Whenever a vertex's depth increases, its block size at least doubles, so its depth is at most $\lfloor {\log }_{2}n\rfloor$. Consequently each representative query or merge takes $O(\log n)$ time. Initialization plus the scan costs $O(n+m\log n)$; including sorting algorithm gives $O(n+m\log m+m\log n)$, hence $O(m\log m)$ for a connected input with $n\ge 2$. These are operation bounds, not measured timings.^[ref]