Kruskal's Algorithm
Imagine a telecom company that must connect a thousand cities with fiber-optic cable. Every possible link between two cities has a known installation cost. The company wants the cheapest possible set of links. This set must still connect every city, directly or indirectly. This is the Minimum Spanning Tree problem. It appears everywhere from network design to circuit layout. It also appears in clustering algorithms that group similar data points. Kruskal's algorithm attacks this problem with a strikingly simple idea. First, sort every possible edge by cost. Then greedily add the cheapest edges one at a time. Skip any edge that would create a cycle. There is no backtracking, no dynamic programming table, no complicated search. There is just a sorted list and a fast way to check "would this edge close a loop?" That check is answered by a disjoint-set forest (union-find). The marriage of these two simple ideas produces an algorithm. It is both easy to implement and provably optimal. The big picture is a case study in strategy. It shows how a greedy strategy, backed by the right combinatorial property, can work. Such a strategy can solve a global optimization problem using only local decisions. The correctness of Kruskal's algorithm rests entirely on the Cut Property of spanning trees. This property guarantees that the lightest edge crossing any cut belongs to some minimum spanning tree. Once you trust that property, the rest of the algorithm is mechanical. This article gives a precise definition of the algorithm. It includes a full pseudocode listing with the union-find data structure. It also includes a diagram tracing the edge-selection process on a real weighted graph. There is a rigorous complexity analysis dominated by sorting. There is a correctness proof via the cut property and an exchange argument. Finally, there is a worked numeric example you can follow edge by edge.
- Kruskal's algorithm builds a Minimum Spanning Tree by sorting all edges by weight and greedily adding each edge that does not create a cycle.
- Cycle detection is done efficiently with a disjoint-set forest (union-find) supporting near-constant-time `find` and `union` operations.
- Total running time is O(E log E), dominated by the initial sort of the edge list; E log E equals E log V for connected graphs since E ≤ V².
- Correctness follows from the Cut Property: the cheapest edge crossing any cut is safe to include in some MST.
- Kruskal's algorithm is edge-centric and works well on sparse graphs, in contrast to Prim's Algorithm, which is vertex-centric and favors dense graphs.
- The algorithm naturally produces a minimum spanning forest when the input graph is disconnected, adding exactly one tree per connected component.
Sort the edges once, then greedily accept each edge that connects two previously separate components, using union-find to test that condition in near-constant time.
The idea
A spanning tree of a connected, undirected graph G = (V, E) is a subset of |V| − 1 edges that connects all vertices without forming a cycle. A minimum spanning tree (MST) is a spanning tree whose total edge weight is smallest among all spanning trees. Kruskal's algorithm computes an MST by processing edges in increasing order of weight and maintaining a growing forest of trees, adding an edge exactly when its two endpoints currently lie in different trees of that forest. The central data structure is the disjoint-set forest, also called union-find. It maintains a partition of the vertex set into groups, one group per current tree fragment, and supports two operations: `Find(v)`, which returns a canonical representative of the group containing v, and `Union(u, v)`, which merges the groups containing u and v. An edge (u, v) is safe to add precisely when `Find(u) ≠ Find(v)`: adding it merges two separate components into one and cannot create a cycle, because a cycle would require u and v to already be connected. The algorithm is an instance of the general greedy MST framework built on the Cut Property: for any cut (a partition of V into two nonempty sets S and V−S) with no edge of the current MST-in-progress crossing it, the minimum-weight edge crossing that cut is safe to add to some MST. Kruskal's algorithm implicitly considers, at each step, the cut separating the component containing u from the component containing v, and because edges are processed in sorted order, the edge under consideration is guaranteed to be the lightest one crossing that cut among all edges not yet examined.
How it works
The algorithm proceeds in three conceptual phases: initialize every vertex as its own singleton tree, sort the edges, then sweep through the sorted list adding safe edges until the forest becomes a single tree (or until all edges are exhausted, in which case it returns a minimum spanning forest for a disconnected graph). ``` KRUSKAL-MST(G = (V, E), weight w): // Phase 1: initialize disjoint-set forest, one set per vertex for each vertex v in V: MAKE-SET(v) A = empty set // edges of the MST being built sort E into non-decreasing order by w(u, v) // Phase 2: greedily process edges in sorted order for each edge (u, v) in sorted E: if FIND-SET(u) != FIND-SET(v): A = A + {(u, v)} UNION(u, v) // else: adding (u, v) would create a cycle -> skip return A // the MST (or minimum spanning forest)
// --- Disjoint-set forest with union by rank and path compression --- MAKE-SET(x): parent[x] = x rank[x] = 0 FIND-SET(x): if parent[x] != x: parent[x] = FIND-SET(parent[x]) // path compression return parent[x] UNION(x, y): rx = FIND-SET(x) ry = FIND-SET(y) if rx == ry: return // already in the same set if rank[rx] < rank[ry]: parent[rx] = ry else if rank[rx] > rank[ry]: parent[ry] = rx else: parent[ry] = rx rank[rx] = rank[rx] + 1 ``` A subtlety worth stating explicitly: the loop can be terminated early once |A| reaches |V| − 1, since at that point the forest has become a single spanning tree and no further edges can be safe. This optimization does not change the asymptotic complexity (sorting still dominates) but saves real work in practice on dense graphs.
Reading the figure: edges are examined in increasing weight order. Each green edge was accepted because its two endpoints were in different components at the time it was considered; each grey edge was rejected because union-find reported its endpoints already shared a component, so adding it would close a cycle.
Complexity & correctness
Time complexity. Let n = |V| and m = |E|. The algorithm performs:
- Initialization of the disjoint-set forest: O(n).
- Sorting the edge list: O(m log m).
- A pass over all m edges, each doing two `FIND-SET` calls and at most one `UNION`.
With path compression and union by rank, a sequence of f `FIND-SET`/`UNION` operations on n elements costs O(f · α(n)) total, where α is the inverse Ackermann function — a quantity that is at most 4 for any input size that could ever be constructed in practice. So the main loop costs O(m · α(n)), which is essentially O(m). The dominant term is the sort: O(m log m). Since a simple graph has m ≤ n², log m ≤ 2 log n, so O(m log m) = O(m log n) as well; both forms are standard and equivalent up to constants. The overall running time is ``` O(m log m) = O(m log n) ``` If the edges arrive pre-sorted, or weights are small integers allowing radix/bucket sort, the running time drops to O(m · α(n)), essentially linear in the number of edges — a fact worth knowing but not the default assumption.
Space complexity. O(n + m): the edge list, the parent/rank arrays of size n, and the output tree of n − 1 edges.
Correctness. The proof has two parts: a safety argument (every edge Kruskal adds belongs to some MST) and a completeness argument (the algorithm produces a spanning tree, not just a forest, when the graph is connected). Safety, via the Cut Property. Process edges in sorted order e₁, e₂, …, eₘ. Suppose edge eᵢ = (u, v) is considered and found to connect two different components C_u and C_v of the current forest. Let S = C_u and consider the cut (S, V − S). No edge currently in the forest crosses this cut, because C_u is a maximal connected component under the edges accepted so far. Among all edges crossing this cut, eᵢ is the lightest one that has not been rejected, and since edges are processed in nondecreasing weight order, no lighter edge crossing this exact cut was skipped — any earlier edge crossing this cut must have been rejected for creating a cycle within a component, meaning both endpoints were already in the same side, contradicting that it crosses (S, V−S). Hence eᵢ is a minimum-weight edge crossing this cut, and the Cut Property guarantees some MST contains it. By an exchange argument, augmenting the algorithm's current partial forest (which is a subset of some MST, by induction) with eᵢ keeps it a subset of some MST. Base case and induction. Initially the forest is empty, which is trivially a subset of every MST. The inductive step above shows that each accepted edge preserves the invariant "the current forest A is a subset of the edge set of some MST." By induction this invariant holds after processing all edges. Completeness. If a rejected edge (u, v) would have connected two different components, it would have been safe and accepted — contrapositive: every rejected edge already had its endpoints in the same component, so the graph induced by A on any component is connected wherever the original graph is. When the input graph is connected, the forest ends as a single tree spanning all n vertices with exactly n − 1 edges, which combined with the invariant means A is a minimum spanning tree. If the input graph has k connected components, Kruskal's algorithm produces a minimum spanning forest with n − k edges, one MST per component — still correct, just not a single tree.
Tradeoffs. Kruskal's algorithm is simple to reason about and works directly from an edge list, so it is attractive when the graph is sparse (m close to n) or already available in sorted or edge-list form, such as when edges stream in from an external source. It is less attractive on dense graphs with an adjacency-matrix representation, where Prim's Algorithm with a Fibonacci heap or a simple array-based priority queue can achieve O(m + n log n) or O(n²) respectively without ever sorting the full edge set. Kruskal's algorithm also generalizes gracefully to disconnected graphs (yielding a forest) and is the natural starting point for matroid-theoretic generalizations of greedy optimization, since the set of forests in a graph forms the independent sets of a graphic matroid.
Worked example
Consider six cities A–F with candidate links and costs:
| Edge | Weight |
|---|---|
| (A, B) | 1 |
| (A, D) | 2 |
| (C, F) | 3 |
| (E, F) | 4 |
| (B, F) | 5 |
| (D, E) | 6 |
| (B, C) | 7 |
| (B, E) | 8 |
Sorted order is already given above. Trace the union-find state (each vertex starts as its own set):
| Step | Edge examined | Find(u) | Find(v) | Action | Sets after step |
|---|---|---|---|---|---|
| 1 | (A,B), w=1 | A | B | different → accept, union | {A,B}, {C}, {D}, {E}, {F} |
| 2 | (A,D), w=2 | A | D | different → accept, union | {A,B,D}, {C}, {E}, {F} |
| 3 | (C,F), w=3 | C | F | different → accept, union | {A,B,D}, {C,F}, {E} |
| 4 | (E,F), w=4 | E | F(=C,F root) | different → accept, union | {A,B,D}, {C,E,F} |
| 5 | (B,F), w=5 | root(A,B,D) | root(C,E,F) | different → accept, union | {A,B,C,D,E,F} |
| 6 | (D,E), w=6 | root | same root | same → reject (cycle) | unchanged |
| 7 | (B,C), w=7 | same root | same root | same → reject (cycle) | unchanged |
| 8 | (B,E), w=8 | same root | same root | same → reject (cycle) | unchanged |
After step 5 the forest already spans all six vertices with 5 = n − 1 edges, so an implementation with the early-termination check would stop here without even inspecting edges 6–8. The resulting MST is ``` { (A,B)=1, (A,D)=2, (C,F)=3, (E,F)=4, (B,F)=5 } ``` with total weight 1 + 2 + 3 + 4 + 5 = 15. Notice edge (D, E) with weight 6 was tempting (cheaper than several rejected alternatives) but was correctly rejected because D and E were already connected through the chain A–D and A–B–F–C–F–E, and including it would have closed a cycle without lowering total cost.
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Using a plain array/list for components with linear-scan membership tests | Naively checking "are u and v connected?" by traversing the whole component costs O(n) per query, degrading total time to O(nm) | Use a proper disjoint-set forest with union by rank and path compression |
| Forgetting path compression or union by rank | Union-find degenerates to a linked list under adversarial union order, making `Find` cost O(n) in the worst case | Implement both optimizations; together they give near-constant amortized cost per operation |
| Not stopping early / assuming output is always a single tree | On a disconnected graph, Kruskal's algorithm cannot produce n − 1 edges; code that asserts this will crash or loop | Detect and accept a minimum spanning forest with n − k edges when the graph has k components |
| Sorting by an unstable or lossy comparator (e.g., converting weights to floats and losing precision) | Ties or precision loss can cause a different, still-valid MST or, worse, an invalid one on buggy comparators | Use a stable, exact comparator; remember MSTs need not be unique but must always be optimal-weight |
| Re-running `Find` redundantly instead of caching the representative within one iteration | Wastes work and, more importantly, easy to introduce a bug comparing stale roots after a union changes them | Compute `Find(u)` and `Find(v)` once per edge, compare, then union if needed |
Pioneers & history
Joseph Kruskal developed the algorithm as a graduate student, publishing it in 1956 while working at Bell Labs, in a paper that also surveyed the shortest-spanning-subtree problem and noted the algorithm's connection to earlier work by Borůvka. His formulation crystallized the "sort edges, greedily accept if no cycle" strategy into the clean, general-purpose procedure taught today, and it later became a foundational example in the theory of matroids, where Jack Edmonds and others showed that the greedy algorithm optimizes over any weighted matroid, with the graphic matroid as the special case underlying Kruskal's algorithm.
Origins · 1 minJoseph Bernard Kruskal Jr. and how this was discovered
Where this matters
Network design is the canonical use case: telecommunications and power-grid engineers use MST algorithms to minimize the total cable or wire length needed to connect a set of sites, and Kruskal's edge-list formulation is a natural fit when link costs are enumerated directly rather than derived from vertex adjacency. Circuit design tools use MST-style algorithms during physical layout to minimize wire length in clock trees and power distribution networks. In computational biology, single-linkage hierarchical clustering is essentially built by running Kruskal's algorithm and stopping early, since the clusters formed after processing the k cheapest edges correspond to connected components under a distance threshold. Computer vision pipelines use MST-based segmentation, where pixels are nodes, edge weights encode intensity difference, and the resulting forest partitions an image into visually coherent regions. Approximation algorithms for harder problems, such as the metric Traveling Salesman Problem, use an MST (frequently computed via Kruskal's algorithm on sparse instances) as a core subroutine to build a 2-approximate tour. Because the union-find data structure it relies on is itself a widely reused building block, understanding Kruskal's algorithm also equips you to recognize and implement disjoint-set forests in dynamic connectivity, image labeling, and Boruvka-style parallel MST algorithms.
Ask the tutor: How does the choice of sorting algorithm change Kruskal's guarantees when edge weights are small bounded integers?
Is the minimum spanning tree produced by Kruskal's algorithm always unique?
No. If several edges share the same weight, different tie-breaking orders during the sort can produce different spanning trees, all with the same minimum total weight. Uniqueness is guaranteed only when all edge weights are distinct, because then no cut ever has two edges of equal minimum weight competing for inclusion, and the safe-edge argument pins down a single choice at every step. In practice, when weights repeat, any consistent tie-breaking rule (e.g., by original edge index) yields a valid MST; comparing outputs from two different implementations may show structurally different but equally optimal trees.
How does Kruskal's algorithm compare to Prim's algorithm in practice?
Kruskal's algorithm sorts all edges upfront and grows a forest, making it a natural fit for sparse graphs and edge-list input, with complexity O(E log E). Prim's Algorithm grows a single tree from a start vertex using a priority queue over vertices, achieving O(E log V) with a binary heap or O(E + V log V) with a Fibonacci heap, which is more attractive on dense graphs. If the edge list is already sorted, or weights are integers permitting linear-time sorting, Kruskal's algorithm can approach linear time and often wins in practice; if the graph is given as an adjacency matrix or is very dense, Prim's algorithm with a simple array-based queue reaches O(V²) without ever paying a sorting cost.
Why does union by rank combined with path compression matter so much for performance?
Without these optimizations, a sequence of unions can build a long, thin tree in the disjoint-set forest, making `Find` cost O(n) in the worst case and the whole algorithm O(nm). Union by rank always attaches the shallower tree under the root of the deeper one, keeping tree height logarithmic in the number of unions. Path compression flattens the path from any queried node directly to the root during every `Find` call, so future queries on that node are essentially constant time. Together, a classical amortized analysis shows any sequence of m operations on n elements costs O(m·α(n)), where α grows so slowly it is effectively a small constant for all realistic n.
Does Kruskal's algorithm work with negative edge weights?
Yes, without any modification. Kruskal's algorithm never assumes weights are nonnegative; it only relies on being able to compare and sort them. The Cut Property and the safe-edge argument hold regardless of sign, so negative weights simply mean some very "cheap" edges get selected first, potentially producing a spanning tree with negative total weight. This is unlike shortest-path algorithms such as Dijkstra's, which require nonnegative weights for correctness — MST algorithms have no such restriction because they never re-relax or improve a previously fixed distance.
What is the relationship between Kruskal's algorithm and matroid theory?
The forests of a graph form the independent sets of a structure called the graphic matroid, and it turns out that a simple greedy algorithm — sort elements by weight, add each one that keeps the current set independent — computes a minimum-weight basis for any matroid, not just graphic ones. Kruskal's algorithm is exactly this generic greedy matroid algorithm specialized to the graphic matroid. This connection, formalized by Jack Edmonds, explains why the same greedy pattern reappears in problems like finding a maximum-weight set of linearly independent vectors or a maximum-weight set of non-overlapping intervals under certain constraints.
Can Kruskal's algorithm be parallelized?
Sorting the edges parallelizes well using standard parallel sort algorithms, and this is often the dominant cost, so real speedups are achievable there. The sequential dependency in the union-find phase is harder to parallelize directly, since later unions depend on the state left by earlier ones, but practical systems use techniques like Borůvka-style rounds (each vertex or component picks its cheapest outgoing edge simultaneously) combined with Kruskal-style filtering to build parallel and distributed MST algorithms, especially for graphs too large to fit on one machine.
What is the space complexity, and can Kruskal's algorithm run in a streaming setting?
Space is O(V + E): the edge list dominates, alongside O(V) for the disjoint-set parent and rank arrays and O(V) for the output tree. A pure streaming setting is awkward because the algorithm needs edges in sorted order, and sorting a stream typically requires O(E) auxiliary space unless external sorting is used. Semi-streaming MST algorithms exist that process edges in a single pass using O(V polylog V) space by maintaining a compressed sketch of the graph, but the classic Kruskal formulation assumes the full sorted edge list is available.