Whenever I’ve needed to connect a set of points — cities, computers, circuit components — using the least total amount of “wire,” I’ve turned to Kruskal’s algorithm. It solves the minimum spanning tree problem: given a connected, weighted, undirected graph, it finds a subset of edges that connects all vertices together, without any cycles, at the minimum possible total edge weight. What I find particularly satisfying about Kruskal’s approach is how directly it embraces greediness — sort all the edges by weight, and just keep adding the cheapest one that doesn’t create a cycle — and yet this simple strategy is provably optimal.
History and Background
I credit this algorithm to Joseph Kruskal, who published it in 1956 in a paper titled “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem.” Interestingly, the underlying idea of building a minimum spanning tree by always selecting the globally cheapest available edge had actually been described even earlier by Otakar BorĹŻvka in 1926, in the context of designing an efficient electrical network in Moravia, making it one of the oldest graph algorithms in existence, predating modern computing entirely. Kruskal’s specific formulation, however, is the one most commonly taught today, largely because of how naturally it pairs with the Union-Find (Disjoint Set) data structure for efficient cycle detection.
Problem Statement
I’m given a connected, undirected graph with weighted edges, and I want to find a spanning tree — a subset of edges that connects all vertices without forming any cycle — whose total edge weight is as small as possible. If the graph has n vertices, any spanning tree must have exactly n - 1 edges. There may be multiple minimum spanning trees if some edge weights are equal, but the total minimum weight itself is always unique. Kruskal’s algorithm solves this by greedily selecting edges in increasing order of weight, using a mechanism to avoid ever forming a cycle.
Core Concepts
- Spanning tree: a subgraph that includes all vertices of the original graph, is connected, and contains no cycles, meaning it has exactly
n - 1edges fornvertices. - Minimum spanning tree (MST): among all possible spanning trees of a graph, the one (or ones) with the smallest total edge weight.
- Union-Find (Disjoint Set Union, DSU): a data structure I use to efficiently track which vertices are already connected to each other, allowing me to quickly check whether adding a given edge would create a cycle.
- Cut property: a fundamental theorem stating that for any partition of the vertices into two disjoint sets, the minimum-weight edge crossing between them must be part of some minimum spanning tree — this is the theoretical justification for Kruskal’s greedy strategy.
- Cycle property: the complementary theorem stating that the maximum-weight edge in any cycle cannot be part of any minimum spanning tree, which is why Kruskal’s algorithm safely skips edges that would form a cycle.
How It Works
I proceed as follows:
- I sort all edges of the graph in non-decreasing order of weight.
- I initialize a Union-Find structure where every vertex starts in its own separate set.
- I process edges one at a time, in sorted order. For each edge
(u, v, w), I check whetheruandvare already in the same set (using the Union-Find’s “find” operation). - If they are in different sets, adding this edge cannot create a cycle, so I include it in the MST and merge (union) the two sets.
- If they are already in the same set, adding this edge would create a cycle, so I skip it.
- I continue until I’ve included exactly
n - 1edges (or I’ve processed all edges, whichever comes first).
Working Principle
The algorithm’s correctness rests on the cut property of minimum spanning trees. At every step, when I consider the next cheapest unprocessed edge, if it connects two vertices currently in different components (sets), then this edge is guaranteed to be the minimum-weight edge crossing the cut between those two components (since I always process edges in increasing weight order, and any earlier, cheaper edge crossing that same cut would already have been considered and either included or would have connected the same two components already). The cut property guarantees this edge belongs to some MST, so including it is always a safe, correct greedy choice. Conversely, when an edge would connect two vertices already in the same component, including it would necessarily form a cycle, and by the cycle property, it cannot be part of any minimum spanning tree (since it would be the maximum weight edge in the cycle it creates, given the sorted processing order).
Mathematical Foundation
Formally, let G = (V, E) be a connected, weighted graph. The Minimum Spanning Tree T is the spanning tree minimizing:
$$ \text{weight}(T) = \sum_{(u,v) \in T} w(u,v) $$
among all possible spanning trees of G.
Cut Property (formal statement): For any cut (S, V \setminus S) of the graph’s vertices into two non-empty disjoint sets, if e is the minimum-weight edge with one endpoint in S and the other in V \setminus S, then there exists a minimum spanning tree containing e.
The total time complexity of Kruskal’s algorithm is dominated by sorting the edges, which takes O(|E| \log |E|), combined with O(|E| \alpha(|V|)) for the Union-Find operations, where α is the inverse Ackermann function (effectively a very small constant for all practical input sizes):
$$ T(|V|, |E|) = O(|E| \log |E|) $$
which is equivalent to O(|E| \log |V|) since |E| is at most O(|V|^2).
Diagrams
flowchart TD
A[Sort all edges by weight in increasing order] --> B[Initialize Union-Find: each vertex its own set]
B --> C[MST = empty set]
C --> D{More edges remaining and MST has fewer than n-1 edges?}
D -- No --> H[Return MST]
D -- Yes --> E[Take next cheapest edge u-v-w]
E --> F{find u == find v?}
F -- Yes: same set, cycle --> D
F -- No: different sets --> G[Add edge to MST; union u and v]
G --> DPseudocode
function kruskal(graph, V):
MST = []
edges = all edges of graph, sorted by weight ascending
// Union-Find initialization
parent[i] = i for each vertex i
rank[i] = 0 for each vertex i
for each edge (u, v, w) in edges:
if find(parent, u) != find(parent, v):
MST.append((u, v, w))
union(parent, rank, u, v)
if length(MST) == V - 1:
break
return MST
function find(parent, i):
if parent[i] != i:
parent[i] = find(parent, parent[i]) // path compression
return parent[i]
function union(parent, rank, x, y):
rootX = find(parent, x)
rootY = find(parent, y)
if rootX == rootY:
return
if rank[rootX] < rank[rootY]:
parent[rootX] = rootY
elif rank[rootX] > rank[rootY]:
parent[rootY] = rootX
else:
parent[rootY] = rootX
rank[rootX] += 1
Step-by-Step Example
Consider a graph with vertices A, B, C, D and edges: A-B (1), A-C (3), B-C (3), B-D (6), C-D (4).
Sorted edges by weight: A-B(1), A-C(3), B-C(3), C-D(4), B-D(6).
Processing:
| Edge | Weight | Same set? | Action | MST so far |
|---|---|---|---|---|
| A-B | 1 | No | Add | {A-B} |
| A-C | 3 | No | Add | {A-B, A-C} |
| B-C | 3 | Yes (both connect to A already) | Skip (would form cycle) | {A-B, A-C} |
| C-D | 4 | No | Add | {A-B, A-C, C-D} |
| B-D | 6 | Yes (all connected now) | Skip | {A-B, A-C, C-D} |
I stop once I have n - 1 = 3 edges. Final MST: A-B (1), A-C (3), C-D (4), with total weight 8.
Time Complexity
- Best case:
O(|E| \log |E|)— dominated by the sorting step, since even a graph that’s already an MST-friendly structure still requires sorting the edges. - Average case:
O(|E| \log |E|). - Worst case:
O(|E| \log |E|), equivalentlyO(|E| \log |V|)— the Union-Find operations with path compression and union by rank contribute only a nearly-constantO(\alpha(|V|))per operation, so sorting remains the dominant cost.
Space Complexity
Kruskal’s algorithm requires O(|E|) space to store and sort the edge list, plus O(|V|) space for the Union-Find parent and rank arrays. The resulting MST itself takes O(|V|) space, since it always contains exactly |V| - 1 edges.
Correctness Analysis
I prove correctness using the cut property, formalized earlier. I show, by induction on the number of edges added, that the set of edges chosen by Kruskal’s algorithm at any point is always a subset of some minimum spanning tree. The base case (no edges chosen) is trivially true. For the inductive step, when Kruskal’s algorithm adds an edge e = (u, v) because u and v are in different components, I can construct a cut where S is the component containing u and V \setminus S is everything else. Since all edges considered before e (by sorted order) either connected vertices already in the same component or were skipped for other reasons, e must be the minimum-weight edge crossing this cut among all edges not yet processed with a smaller or equal weight; more precisely, no smaller-weight edge could have connected these two specific components without already having been added. By the cut property, some MST contains an edge crossing this cut with weight at most w(e), and since Kruskal processes edges in increasing order, e is a valid minimal choice, so the invariant holds after adding e. By induction, the final set of |V|-1 edges chosen forms a valid minimum spanning tree.
Advantages
- Conceptually simple, greedy, and easy to reason about once the Union-Find data structure is understood.
- Works particularly well on sparse graphs, where the number of edges
|E|is much smaller than|V|^2, since the sorting step dominates and scales with|E|. - Naturally produces a global view of edge importance by sorting all edges up front, which can be useful for other analyses (like building a full minimum spanning forest).
- The Union-Find structure it relies on has near-constant amortized time per operation, making the algorithm very efficient in practice.
Disadvantages
- Requires sorting all edges up front, which can be a bottleneck on graphs with a very large number of edges compared to vertices (dense graphs), where Prim’s algorithm (especially with a good priority queue) may perform better.
- Doesn’t naturally extend to directed graphs; minimum spanning trees are defined for undirected graphs, and directed analogs require different algorithms (like the Chu-Liu/Edmonds algorithm for minimum arborescences).
- If the graph is disconnected, Kruskal’s algorithm as described produces a minimum spanning forest rather than a single spanning tree, which needs to be explicitly acknowledged and handled depending on the application.
- Implementing Union-Find correctly, with both path compression and union by rank, takes a bit of care to get the full efficiency benefit.
Applications
- Network design, such as laying out the minimum amount of cable needed to connect a set of buildings or computers.
- Circuit design, minimizing the total wire length needed to connect components on a circuit board.
- Cluster analysis in machine learning, where MSTs are used as part of certain hierarchical clustering algorithms.
- Approximation algorithms for harder problems, such as using MSTs as a building block in approximate solutions to the traveling salesman problem.
- Image segmentation in computer vision, where MST-based approaches are used to group pixels into coherent regions.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int u, v, weight;
} Edge;
int parent[100], rankArr[100];
int find(int i) {
if (parent[i] != i) {
parent[i] = find(parent[i]); /* path compression */
}
return parent[i];
}
void unionSets(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return;
if (rankArr[rootX] < rankArr[rootY]) {
parent[rootX] = rootY;
} else if (rankArr[rootX] > rankArr[rootY]) {
parent[rootY] = rootX;
} else {
parent[rootY] = rootX;
rankArr[rootX]++;
}
}
int compareEdges(const void *a, const void *b) {
return ((Edge *)a)->weight - ((Edge *)b)->weight;
}
void kruskal(Edge edges[], int numEdges, int numVertices) {
qsort(edges, numEdges, sizeof(Edge), compareEdges);
for (int i = 0; i < numVertices; i++) {
parent[i] = i;
rankArr[i] = 0;
}
int mstWeight = 0;
int edgeCount = 0;
printf("Edges in the Minimum Spanning Tree:\n");
for (int i = 0; i < numEdges && edgeCount < numVertices - 1; i++) {
int u = edges[i].u, v = edges[i].v, w = edges[i].weight;
if (find(u) != find(v)) {
unionSets(u, v);
printf("%d - %d : %d\n", u, v, w);
mstWeight += w;
edgeCount++;
}
}
printf("Total weight of MST: %d\n", mstWeight);
}
int main() {
/* 0=A, 1=B, 2=C, 3=D */
Edge edges[] = {
{0, 1, 1}, /* A-B */
{0, 2, 3}, /* A-C */
{1, 2, 3}, /* B-C */
{1, 3, 6}, /* B-D */
{2, 3, 4} /* C-D */
};
int numEdges = 5;
int numVertices = 4;
kruskal(edges, numEdges, numVertices);
return 0;
}
Sample Input and Output
Input: graph with vertices A(0), B(1), C(2), D(3) and edges A-B(1), A-C(3), B-C(3), B-D(6), C-D(4).
Output:
Edges in the Minimum Spanning Tree:
0 - 1 : 1
0 - 2 : 3
2 - 3 : 4
Total weight of MST: 8
Optimization Techniques
- Union by rank and path compression: combining both optimizations in the Union-Find data structure gives near-constant amortized time per operation (technically
O(\alpha(n)), the inverse Ackermann function), which is essential for Kruskal’s algorithm to reach its stated efficiency. - Early termination: stopping as soon as
|V| - 1edges have been added, rather than processing every remaining edge in the sorted list, avoids unnecessary work once the MST is complete. - Bucket sort for integer weights: if edge weights are small integers within a known range, using a non-comparison sort like counting sort or bucket sort can reduce the sorting step’s complexity below
O(|E| \log |E|). - Parallel/external sorting: for extremely large graphs that don’t fit in memory, using external or parallel sorting algorithms for the edge list allows Kruskal’s algorithm to scale to massive datasets.
Common Mistakes
- Forgetting path compression or union by rank in the Union-Find implementation, which degrades performance significantly on adversarial inputs (approaching linear-time
findoperations in the worst case). - Not sorting edges correctly (e.g., sorting by a wrong key, or forgetting to sort at all), which breaks the fundamental greedy invariant the algorithm relies on.
- Applying Kruskal’s algorithm to a disconnected graph without recognizing that the result will be a spanning forest, not a single spanning tree, potentially leading to incorrect assumptions downstream.
- Confusing Kruskal’s algorithm (edge-focused, sorts all edges globally) with Prim’s algorithm (vertex-focused, grows a single tree from a starting vertex), which have different performance characteristics depending on graph density.
Further Reading
- Kruskal, J. B. “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem,” Proceedings of the American Mathematical Society, 1956: https://www.ams.org/journals/proc/1956-007-01/S0002-9939-1956-0078686-7/
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. “Introduction to Algorithms” (CLRS), Chapter on Minimum Spanning Trees: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- GeeksforGeeks, “Kruskal’s Minimum Spanning Tree Algorithm”: https://www.geeksforgeeks.org/dsa/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/
- Wikipedia, “Kruskal’s algorithm”: https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
