Kruskal's Algorithm

Kruskal's algorithm is a greedy graph optimization procedure within computation and algorithms that computes a minimum spanning tree (MST) for a connected, edge-weighted undirected graph G = (V, E, w), or a minimum spanning forest when G is disconnected. Published by American mathematician and statistician Joseph B. Kruskal Jr. in the Proceedings of the American Mathematical Society in 1956, the algorithm sorts all edges e ∈ E in non-decreasing order of weight and scans the sorted sequence, adding each edge (u, v) to the growing forest F if and only if its endpoints u and v currently reside in distinct connected components.

By maintaining connected components inside a disjoint-set data structure (Union–Find) equipped with union by rank and path compression, Kruskal's algorithm tests cycle formation in O(α(|V|)) amortized time per edge, where α denotes the inverse Ackermann function. Consequently, total execution time is governed by the initial edge sort, running in O(|E| log |E|) = O(|E| log |V|) time within computational complexity theory. Across statistical physics, phylogenetics, and machine learning, Kruskal's bottom-up component coalescence is isomorphic to single-linkage hierarchical clustering, percolation cluster merging, and minimum-mutation haplotype network construction.

Problem Definition and Forest Growth Mechanics

Let G = (V, E, w) be an undirected graph with |V| vertices, |E| edges, and real edge-weight function w : E → ℝ. A spanning tree T ⊆ E of a connected graph G is a connected, acyclic subgraph containing all |V| vertices and |V| − 1 edges, with total weight w(T) = ∑_{e ∈ T} w(e). Kruskal's algorithm constructs a minimum-weight spanning forest F in three phases:

1. Initialization: Create an empty edge set F ← ∅ and initialize |V| singleton disjoint sets via Make-Set(v) for every v ∈ V.
2. Global Edge Sorting: Sort the edge set E into non-decreasing weight order w(e₁) ≤ w(e₂) ≤ ... ≤ w(e_|E|).
3. Greedy Coalescence Sweep: Iterate over e_i = (u, v) for i = 1, ..., |E|. Query component roots via Find-Set(u) and Find-Set(v). If Find-Set(u) ≠ Find-Set(v), append e_i to F and merge the two components via Union(u, v); otherwise discard e_i because its endpoints are already connected in F. Terminate once |F| = |V| − 1.

Correctness via the Cut and Cycle Rules

The optimality of Kruskal's greedy choice follows from the cut property of minimum spanning trees. Whenever Kruskal's algorithm selects an edge e = (u, v) connecting two distinct components C_u and C_v of F, consider the cut (S, V \ S) with S = C_u. No edge currently in F crosses (S, V \ S), and any lighter edge crossing (S, V \ S) would have been inspected earlier and merged C_u with its complement; hence e is a minimum-weight edge across (S, V \ S) and belongs to some MST of G. Conversely, any rejected edge e = (u, v) with Find-Set(u) = Find-Set(v) is a maximum-weight edge on the cycle F ∪ {e} and is excluded by the cycle property (and more generally by the Rado–Edmonds theorem on the graphic matroid M(G)).

Reverse-Delete Dual Algorithm

Kruskal (1956) also formulated the dual Reverse-Delete algorithm: starting from F = E, sort edges in non-increasing weight order and delete each edge e_i whenever F \ {e_i} remains connected, which corresponds to Kruskal's algorithm on the planar dual graph G*.

Disjoint-Set Union-Find Runtime Breakdown

In a simple graph where |E| ≤ |V|(|V| − 1)/2, log |E| = O(log |V|). Breaking down the two stages of Kruskal's algorithm yields:

• Sorting Phase: O(|E| log |E|) = O(|E| log |V|) time using comparison sorting, or O(|E|) time if edge weights are small integers sorted via radix sort.
• Disjoint-Set Phase: |V| calls to Make-Set, 2|E| calls to Find-Set, and at most |V| − 1 calls to Union, running in O((|V| + |E|) α(|V|)) time via disjoint-set data structures.

Filter-Kruskal Optimization

To avoid sorting heavy edges when the MST completes early, Filter-Kruskal (Osipov, Sanders, & Singler, 2009) interleaves Quicksort partitioning with Union–Find: it partitions E around a pivot weight, recursively processes the lighter subset E_≤, filters out edges in E_> whose endpoints already share a Union–Find root, and only recurses on the surviving cross-component edges.

Single-Linkage Hierarchical Clustering and Minimax Paths

In multivariate statistics, running Kruskal's algorithm on a pairwise dissimilarity matrix d(x_i, x_j) and stopping k − 1 steps prior to completion (when k components remain) yields the single-linkage clustering partition that maximizes minimum inter-cluster separation (Gower & Ross, 1969). Moreover, the unique path between u and v in the Kruskal MST minimizes the maximum edge weight encountered along any u–v path (the minimax bottleneck path); negated to maximize minimum capacity, this bottleneck tree often seeds high-capacity paths for the Ford–Fulkerson algorithm.

In evolutionary genomics and viral epidemiology, Kruskal's algorithm constructs minimum spanning haplotype networks (GrapeTree) from whole-genome SNP distances to trace outbreak transmission chains. In computer vision, Felzenszwalb and Huttenlocher's (2004) graph-based image segmentation adapts Kruskal's merge rule by comparing cross-component edge weights against the internal spanning-tree variability of adjacent pixel regions.

Does Kruskal's algorithm produce a unique minimum spanning tree?

If all edge weights in G are pairwise distinct, the minimum spanning tree is unique, and Kruskal's algorithm, Prim's algorithm, and Borůvka's algorithm construct the identical edge set T. When duplicate edge weights occur, tie-breaking during the sort can yield different spanning trees that all share the same optimal total weight w(T).

How does Kruskal's algorithm behave on disconnected graphs?

Unlike Prim's algorithm, which grows a single connected tree from one starting root, Kruskal's global edge scan processes all connected components simultaneously. On a graph with c connected components, the final edge set F contains |V| − c edges and forms a minimum spanning forest.

1. Kruskal, J. B. (1956). "On the shortest spanning subtree of a graph and the traveling salesman problem." Proceedings of the American Mathematical Society, 7(1), 48–50. https://doi.org/10.1090/S0002-9939-1956-0078686-7
2. Gower, J. C., & Ross, G. J. S. (1969). "Minimum spanning trees and single linkage cluster analysis." Journal of the Royal Statistical Society: Series C (Applied Statistics), 18(1), 54–64. https://doi.org/10.2307/2346439
3. Tarjan, R. E. (1975). "Efficiency of a good but not linear set union algorithm." Journal of the ACM, 22(2), 215–225. https://doi.org/10.1145/321879.321884
4. Felzenszwalb, P. F., & Huttenlocher, D. P. (2004). "Efficient graph-based image segmentation." International Journal of Computer Vision, 59(2), 167–181. https://doi.org/10.1023/B:VISI.0000022288.19776.77
5. Osipov, V., Sanders, P., & Singler, J. (2009). "The Filter-Kruskal minimum spanning tree algorithm." Proceedings of the 11th Workshop on Algorithm Engineering and Experiments (ALENEX), 52–61. https://doi.org/10.1137/1.9781611972894.5