I want to explain this as one of the most practical and intuitive graph algorithms I know: given a connected, weighted, undirected graph, I want to find a subset of edges that connects all the vertices together, without any cycles, at the minimum possible total edge weight. That subset is called a Minimum Spanning Tree (MST). I find it useful to think of it as the cheapest possible way to “wire up” a network — whether that’s roads, power lines, or computer cables — so that every point is reachable from every other point.
History and Background
The problem has a rich, somewhat tangled history I find genuinely interesting. The earliest known algorithm was developed by the Czech mathematician Otakar Borůvka in 1926, motivated by the practical problem of efficiently constructing an electrical network in Moravia. Joseph Kruskal published his now-famous algorithm in 1956, and Robert Prim independently published his in 1957 (though it turns out a similar idea had actually already appeared in a 1930 paper by Vojtěch Jarník, so Prim’s algorithm is sometimes called the Prim–Jarník algorithm). All three approaches — Borůvka’s, Kruskal’s, and Prim’s — solve the same problem using fundamentally different strategies, and I think comparing them side by side is one of the best ways to understand greedy algorithm design in general.
Problem Statement
I define it as: given a connected, weighted, undirected graph $G = (V, E)$ with edge weights $w: E \to \mathbb{R}$, find a spanning tree $T \subseteq E$ (a subset of edges connecting all vertices without forming any cycle) such that the total weight $\sum_{e \in T} w(e)$ is minimized.
Core Concepts
- Spanning tree: a subgraph that includes every vertex of the original graph, is connected, and contains no cycles — meaning it always has exactly $|V| – 1$ edges.
- Cut property: for any partition of the vertices into two non-empty sets, the minimum-weight edge crossing between them must be part of some MST — a foundational fact that justifies both Prim’s and Kruskal’s greedy choices.
- Cycle property: for any cycle in the graph, the maximum-weight edge in that cycle is never part of any MST (assuming distinct weights) — this justifies safely discarding certain edges.
- Union-Find (Disjoint Set Union): a data structure used in Kruskal’s algorithm to efficiently track which vertices are already connected, avoiding cycle formation.
- Greedy algorithm: an algorithm that builds up a solution by always making the locally optimal choice at each step — both Kruskal’s and Prim’s algorithms are greedy, and both are provably optimal for this particular problem.
How It Works
A. Kruskal’s algorithm:
- I sort all edges in the graph by weight, from smallest to largest.
- I initialize each vertex as its own separate component (using a Union-Find structure).
- I process edges in increasing order of weight: for each edge, if its two endpoints are in different components, I add the edge to the MST and merge the components; otherwise, I discard the edge (since adding it would create a cycle).
- I stop once I’ve added $|V|-1$ edges.
B. Prim’s algorithm:
- I pick an arbitrary starting vertex and add it to the “MST so far” set.
- I maintain a priority queue of all edges crossing from the current MST set to vertices outside it.
- I repeatedly extract the minimum-weight crossing edge, add its outside endpoint to the MST set, and add that vertex’s new crossing edges to the priority queue.
- I repeat until every vertex has been included in the MST set.
Working Principle
Both algorithms rely on the cut property I mentioned above: at every step, whatever set of vertices I’ve grouped together so far defines a “cut” separating them from the rest of the graph, and the minimum-weight edge crossing that cut is always safe to add to the MST without risking suboptimality later. Kruskal’s algorithm applies this idea globally, sorting all edges up front and greedily accepting any edge that doesn’t create a cycle. Prim’s algorithm applies it locally and incrementally, always growing a single connected component outward by picking the cheapest available edge leaving it. Despite this difference in perspective, both are provably guaranteed to arrive at a genuinely minimum spanning tree.
Mathematical Foundation
The total MST weight is:
$$ W(T) = \sum_{(u,v) \in T} w(u,v) $$
The cut property states: for any cut $(S, V \setminus S)$ of the graph, if edge $e = (u,v)$ with $u \in S, v \in V \setminus S$ has the minimum weight among all edges crossing the cut, then:
$$ e \in \text{some MST of } G $$
The cycle property states: for any cycle $C$ in the graph, if edge $e \in C$ has strictly the maximum weight among edges in $C$, then:
$$ e \notin \text{any MST of } G $$
Every spanning tree on $n$ vertices has exactly:
$$ |T| = n – 1 \text{ edges} $$
Diagrams
flowchart TD
Start([Start: sort edges by weight - Kruskal]) --> Init[Initialize each vertex as its own set]
Init --> Loop["For each edge (u,v) in sorted order"]
Loop --> Cycle{Do u and v belong to different sets?}
Cycle -- No, same set --> Discard[Discard edge - would form cycle]
Cycle -- Yes --> Add[Add edge to MST, union the two sets]
Discard --> More{More edges and MST not complete?}
Add --> More
More -- Yes --> Loop
More -- No --> End([Return MST])Pseudocode
Kruskal’s algorithm:
function Kruskal(Graph):
MST = empty set
sort edges of Graph by weight ascending
for each vertex v:
MakeSet(v) // union-find initialization
for each edge (u, v, weight) in sorted order:
if Find(u) != Find(v):
MST.add((u, v, weight))
Union(u, v)
if |MST| == |V| - 1:
break
return MST
Prim’s algorithm:
function Prim(Graph, start):
MST = empty set
visited = { start }
Q = priority queue of edges from start, keyed by weight
while |visited| < |V|:
(u, v, weight) = Q.extractMin() // cheapest edge with v not yet visited
if v in visited:
continue
MST.add((u, v, weight))
visited.add(v)
for each edge (v, x, w2) where x not in visited:
Q.insert((v, x, w2))
return MST
Step-by-Step Example
Using the graph above: edges A-B(2), A-C(3), B-C(1), B-D(4), C-D(5), C-E(6), D-E(2).
Kruskal’s trace:
- Sorted edges: B-C(1), A-B(2), D-E(2), A-C(3), B-D(4), C-D(5), C-E(6).
- B-C(1): different sets, add. MST={B-C}.
- A-B(2): different sets, add. MST={B-C, A-B}.
- D-E(2): different sets, add. MST={B-C, A-B, D-E}.
- A-C(3): A and C are now in the same set (via A-B-C), skip.
- B-D(4): B’s set {A,B,C} and D’s set {D,E} are different, add. MST={B-C, A-B, D-E, B-D}.
- Now |MST| = 4 = |V|-1, stop.
Final MST edges: B-C(1), A-B(2), D-E(2), B-D(4). Total weight = 1+2+2+4 = 9.
Time Complexity
- Kruskal’s algorithm: dominated by sorting edges, $O(E \log E)$, which is equivalent to $O(E \log V)$ since $E \leq V^2$; the union-find operations add only a near-constant $O(\alpha(V))$ factor per operation (where $\alpha$ is the inverse Ackermann function, effectively constant in practice).
- Prim’s algorithm: with a binary heap priority queue, $O(E \log V)$; with a Fibonacci heap, $O(E + V \log V)$, matching Dijkstra’s algorithm’s complexity profile since the two algorithms share a similar structure.
- Borůvka’s algorithm (for completeness): $O(E \log V)$, using $\log V$ rounds each processing all edges in $O(E)$.
All three achieve essentially the same asymptotic performance in practice, though constant factors and ease of implementation differ.
Space Complexity
Kruskal’s algorithm needs $O(V)$ space for the union-find structure and $O(E)$ space to store and sort the edge list, giving $O(V+E)$ overall. Prim’s algorithm needs $O(V)$ space for the visited set and $O(E)$ space for the priority queue (which can hold up to one entry per edge in the worst case), also giving $O(V+E)$ overall.
Correctness Analysis
Both algorithms’ correctness follows directly from the cut property. For Kruskal’s algorithm: when I consider edges in increasing weight order and add an edge that connects two previously separate components, that edge is, by construction, the minimum-weight edge crossing the cut defined by those two components at that point in the process — so by the cut property, it’s guaranteed to belong to some MST, and adding it can never prevent reaching an optimal solution. For Prim’s algorithm: at every step, the vertex set “visited so far” defines a cut, and I always select the minimum-weight edge crossing that cut — again directly satisfying the cut property. Because both algorithms only ever add edges justified by the cut property, and because they both produce exactly $|V|-1$ edges connecting all vertices without cycles (a valid spanning tree), the resulting tree is guaranteed to be of minimum total weight.
Advantages
- Both Kruskal’s and Prim’s algorithms are simple, well-understood, and guaranteed to find a truly optimal (minimum-weight) spanning tree.
- Kruskal’s algorithm is naturally well-suited to sparse graphs, since it processes the edge list directly.
- Prim’s algorithm is naturally well-suited to dense graphs, especially when implemented with a simple array-based minimum search rather than a heap.
- MST algorithms are a clean, canonical example of when a purely greedy strategy is provably optimal, unlike many other combinatorial optimization problems.
Disadvantages
- Neither algorithm directly generalizes to directed graphs — the analogous problem there (minimum spanning arborescence) requires different algorithms, like the Chu–Liu/Edmonds’ algorithm.
- MSTs are not unique when edge weights are not distinct — multiple valid minimum spanning trees can exist with the same total weight, which can be surprising if one expects a single canonical answer.
- The basic algorithms assume the graph is connected; if it isn’t, I get a “minimum spanning forest” instead, which needs to be explicitly acknowledged when implementing.
- Neither algorithm accounts for additional real-world constraints, like maximum degree per node or capacity limits, without further extension.
Applications
- Network design: laying out the cheapest possible cabling, piping, or road network connecting a set of locations.
- Clustering: removing the most expensive edges from an MST is a well-known technique for single-linkage hierarchical clustering.
- Image segmentation in computer vision, using MST-based region-merging approaches.
- Circuit design, minimizing the total wire length needed to connect components on a chip.
- Approximation algorithms for harder problems, such as using MSTs as a building block in Christofides’ algorithm for the Traveling Salesperson Problem.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
#define V 5 // A=0, B=1, C=2, D=3, E=4
#define E 7
struct Edge {
int src, dest, weight;
};
int parent[V], rank_[V];
int find(int i) {
if (parent[i] != i)
parent[i] = find(parent[i]); // path compression
return parent[i];
}
void unionSets(int a, int b) {
int rootA = find(a), rootB = find(b);
if (rootA == rootB) return;
if (rank_[rootA] < rank_[rootB]) {
parent[rootA] = rootB;
} else if (rank_[rootA] > rank_[rootB]) {
parent[rootB] = rootA;
} else {
parent[rootB] = rootA;
rank_[rootA]++;
}
}
int compareEdges(const void *a, const void *b) {
return ((struct Edge *)a)->weight - ((struct Edge *)b)->weight;
}
void kruskalMST(struct Edge edges[]) {
qsort(edges, E, sizeof(struct Edge), compareEdges);
for (int v = 0; v < V; v++) {
parent[v] = v;
rank_[v] = 0;
}
int mstWeight = 0, edgeCount = 0;
printf("Edges in the MST:\n");
for (int i = 0; i < E && edgeCount < V - 1; i++) {
int u = edges[i].src, v = edges[i].dest, w = edges[i].weight;
if (find(u) != find(v)) {
unionSets(u, v);
printf("%d - %d : weight %d\n", u, v, w);
mstWeight += w;
edgeCount++;
}
}
printf("Total MST weight: %d\n", mstWeight);
}
int main() {
struct Edge edges[E] = {
{0, 1, 2}, // A-B
{0, 2, 3}, // A-C
{1, 2, 1}, // B-C
{1, 3, 4}, // B-D
{2, 3, 5}, // C-D
{2, 4, 6}, // C-E
{3, 4, 2} // D-E
};
kruskalMST(edges);
return 0;
}
Sample Input and Output
Input: the 5-vertex, 7-edge graph defined above.
Output:
Edges in the MST:
1 - 2 : weight 1
0 - 1 : weight 2
3 - 4 : weight 2
1 - 3 : weight 4
Total MST weight: 9
This matches my manual Kruskal’s trace exactly — same edges, same total weight of 9.
Optimization Techniques
- Use union-find with both path compression and union by rank, which together bring the amortized cost per operation down to nearly constant time (inverse Ackermann function).
- For Prim’s algorithm, use a Fibonacci heap when the graph is dense enough that the improved decrease-key performance matters, achieving $O(E + V \log V)$.
- For very large distributed graphs, use Borůvka’s algorithm, since its round-based structure (each round halves the number of components) parallelizes naturally across multiple machines.
- Pre-filter or bucket-sort edges by weight when weights are drawn from a small integer range, speeding up Kruskal’s sorting step below $O(E \log E)$.
Common Mistakes
- Forgetting to check for cycles in Kruskal’s algorithm (i.e., skipping the union-find check), which can silently produce an invalid, cycle-containing result instead of a tree.
- Using a naive $O(V)$ linear-scan-for-minimum in Prim’s algorithm on a large sparse graph, missing the substantial speedup available from a proper priority queue.
- Assuming the MST is unique when edge weights contain ties — different algorithms (or different tie-breaking rules) can legitimately produce different, equally optimal MSTs.
- Applying an MST algorithm directly to a directed graph, expecting the same guarantees — directed spanning-tree problems require fundamentally different algorithms.
- Not handling disconnected graphs, which produces an incomplete “forest” rather than a single spanning tree, without any warning unless explicitly checked.
Further Reading
- 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.
- Prim, R. C. (1957). “Shortest Connection Networks and Some Generalizations.” Bell System Technical Journal, 36(6), 1389–1401.
- Borůvka, O. (1926). “O jistém problému minimálním.” Práce Moravské Přírodovědecké Společnosti, 3, 37–58.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. Introduction to Algorithms, MIT Press: https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- GeeksforGeeks, Minimum Spanning Tree: https://www.geeksforgeeks.org/dsa/minimum-spanning-tree-tutorial/
