I am covering the spanning tree problem in this document, focusing mainly on the minimum spanning tree (MST) since that is the version I use most in practice. A spanning tree of a connected, undirected graph is a subgraph that includes every vertex and is a tree, meaning it is connected and has no cycles. Among all possible spanning trees of a weighted graph, the minimum spanning tree is the one whose total edge weight is smallest. I find this concept foundational because it appears in network design, clustering, and as a building block for more advanced algorithms like the Steiner tree approximation I described earlier.
History and Background
The minimum spanning tree problem has one of the longest histories in combinatorial optimization. The earliest known algorithm was described by Czech mathematician Otakar Borůvka in 1926, motivated by the practical problem of designing an efficient electrical network. Joseph Kruskal published his greedy edge-sorting algorithm in 1956, and Robert Prim published his vertex-growing algorithm in 1957, building on earlier work by Vojtěch Jarník in 1930. These three algorithms, Borůvka’s, Kruskal’s, and Prim’s, remain the standard toolkit I reach for depending on the graph’s density and structure.
Problem Statement
Given a connected, undirected, weighted graph $G = (V, E, w)$, I want to find a subset of edges $T \subseteq E$ such that $T$ connects all vertices in $V$, contains exactly $|V| – 1$ edges, has no cycles, and the total weight $\sum_{e \in T} w(e)$ is minimized among all such subsets.
Core Concepts
- Tree: a connected acyclic graph.
- Spanning subgraph: a subgraph that includes every vertex of the original graph.
- Cut property: for any partition of vertices into two sets, the minimum weight edge crossing the partition must be part of some MST.
- Cycle property: for any cycle in the graph, the maximum weight edge in that cycle cannot be part of any MST (unless there are ties).
- Union-Find (Disjoint Set Union): a data structure I use in Kruskal’s algorithm to efficiently detect whether adding an edge would create a cycle.
How It Works
I usually pick between Kruskal’s and Prim’s algorithm depending on graph density.
Kruskal’s approach:
- I sort all edges by weight in ascending order.
- I initialize each vertex as its own separate component using a union-find structure.
- I go through edges in sorted order, and for each edge, I check if its two endpoints are already in the same component.
- If they are in different components, I add the edge to my spanning tree and union the two components.
- If they are already in the same component, adding the edge would create a cycle, so I skip it.
- I stop once I have added $|V| – 1$ edges.
Prim’s approach:
- I start from an arbitrary vertex and mark it as part of the tree.
- I maintain a priority queue of edges crossing from the tree to vertices outside it.
- I repeatedly extract the minimum weight edge from this queue that connects to a vertex not yet in the tree.
- I add that edge and vertex to the tree.
- I update the priority queue with new crossing edges from the newly added vertex.
- I repeat until all vertices are included.
Working Principle
Both algorithms rely on the same underlying mathematical guarantee: the cut property. Every time I add the cheapest available edge that does not create a cycle (Kruskal) or the cheapest edge crossing the current tree boundary (Prim), I am always choosing an edge that is guaranteed to belong to some minimum spanning tree, because it is the lightest edge crossing some cut in the graph. This greedy choice never needs to be undone later, which is what makes these algorithms both simple and provably correct, unlike many other optimization problems where greedy choices can lead to suboptimal results.
Mathematical Foundation
I define the total weight of a candidate spanning tree $T$ as:
$$ w(T) = \sum_{e \in T} w(e) $$
and I want:
$$ T^* = \arg\min_{T \text{ spans } G} w(T) $$
The cut property I rely on states: for any cut $(S, V \setminus S)$ of the vertex set, if edge $e$ is the unique minimum weight edge crossing the cut, then $e$ belongs to every minimum spanning tree of $G$. Formally:
$$ e = \arg\min_{(u,v) \in E,\ u \in S,\ v \notin S} w(u, v) \implies e \in T^* $$
This property is what justifies both Kruskal’s and Prim’s greedy choices at every step.
Diagrams
flowchart TD
A[Start with graph G] --> B{Choose algorithm}
B -->|Kruskal| C[Sort edges by weight]
C --> D[Add edge if it does not form a cycle using Union-Find]
D --> E{All V-1 edges added?}
E -- No --> D
E -- Yes --> F[Minimum Spanning Tree found]
B -->|Prim| G[Start from a vertex, grow tree]
G --> H[Pick minimum weight edge crossing tree boundary]
H --> I{All vertices included?}
I -- No --> H
I -- Yes --> FPseudocode
function KRUSKAL_MST(G):
T = empty set
sort edges of G by weight ascending
for each vertex v in G:
MAKE_SET(v)
for each edge (u, v) in sorted order:
if FIND(u) != FIND(v):
add (u, v) to T
UNION(u, v)
return T
function PRIM_MST(G, start):
T = empty set
visited = {start}
priority_queue = all edges from start, ordered by weight
while |visited| < |V(G)|:
(u, v, weight) = EXTRACT_MIN(priority_queue) where v not in visited
add (u, v) to T
add v to visited
for each edge (v, x) in G where x not in visited:
insert (v, x) into priority_queue
return T
Step-by-Step Example
I use the graph shown in the diagram above: vertices {A, B, C, D}, edges A-B(4), A-C(1), B-C(2), B-D(5), C-D(8).
Using Kruskal’s algorithm:
- Sorted edges: A-C(1), B-C(2), A-B(4), B-D(5), C-D(8).
- A-C(1): different components, add it. Tree = {A-C}.
- B-C(2): different components, add it. Tree = {A-C, B-C}.
- A-B(4): A and B are already connected through C, skip it.
- B-D(5): different components, add it. Tree = {A-C, B-C, B-D}.
- I now have 3 edges for 4 vertices, so I stop.
- Total weight = 1 + 2 + 5 = 8.
Time Complexity
Kruskal’s algorithm costs $O(E \log E)$ for sorting the edges, plus nearly $O(E \alpha(V))$ for the union-find operations, where $\alpha$ is the inverse Ackermann function, which grows so slowly it is effectively constant. So overall, Kruskal’s runs in $O(E \log E)$, which is the same as $O(E \log V)$ since $E$ is at most $V^2$. Prim’s algorithm, when implemented with a binary heap, runs in $O(E \log V)$, and with a Fibonacci heap, it improves to $O(E + V \log V)$, which is better for dense graphs.
Space Complexity
I need $O(V + E)$ space to store the graph itself. Kruskal’s algorithm needs additional $O(V)$ space for the union-find structure and $O(E)$ for the sorted edge list. Prim’s algorithm needs $O(V)$ space for the priority queue and visited tracking. So both algorithms use $O(V + E)$ space overall.
Correctness Analysis
I rely on the cut property and the cycle property I described earlier, both of which are provable using an exchange argument: if I assume some other spanning tree $T’$ has lower weight than the tree $T$ produced by my greedy algorithm, I can always find an edge in $T$ not in $T’$ and an edge in $T’$ not in $T$ that, when swapped, produce a tree with weight less than or equal to $T’$’s weight while making the trees more similar. Repeating this exchange argument shows that $T$ cannot have higher weight than any other spanning tree, proving optimality.
Advantages
- Both Kruskal’s and Prim’s algorithms are simple to understand and implement.
- They always find the exact optimal answer, not just an approximation.
- They run efficiently even on graphs with millions of edges when implemented with appropriate data structures.
- The concepts (cut property, greedy exchange) generalize to other optimization problems I encounter later, like matroid theory.
Disadvantages
- Kruskal’s algorithm requires sorting all edges upfront, which can be wasteful if the graph is very dense and I only need a partial tree.
- Prim’s algorithm’s performance depends heavily on the priority queue implementation I choose.
- Neither algorithm directly handles disconnected graphs; I would need to compute a minimum spanning forest instead.
- These algorithms assume static graphs; dynamic graphs with frequently changing edge weights need more specialized incremental algorithms.
Applications
I have applied spanning tree algorithms in network design, where I want to connect all offices or computers with minimum total cable length. It is also foundational in clustering algorithms, since removing the most expensive edges from an MST naturally groups nearby points together. I have seen it used in circuit design, approximation algorithms for harder problems like the traveling salesman problem and the Steiner tree problem, and in image segmentation where pixels are treated as graph nodes.
Implementation in C
#include <stdio.h>
#include <stdlib.h>
#define MAXV 100
#define MAXE 1000
typedef struct {
int u, v, weight;
} Edge;
Edge edges[MAXE];
int edgeCount;
int parent[MAXV], rank_[MAXV];
/* Union-Find with path compression and union by rank, used to
detect cycles efficiently while building the spanning tree. */
int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
void unite(int x, int y) {
int rx = find(x), ry = find(y);
if (rx == ry) return;
if (rank_[rx] < rank_[ry]) parent[rx] = ry;
else if (rank_[rx] > rank_[ry]) parent[ry] = rx;
else { parent[ry] = rx; rank_[rx]++; }
}
int compare_edges(const void *a, const void *b) {
return ((Edge *)a)->weight - ((Edge *)b)->weight;
}
int kruskal_mst(int n, int *total_weight) {
for (int i = 0; i < n; i++) { parent[i] = i; rank_[i] = 0; }
qsort(edges, edgeCount, sizeof(Edge), compare_edges);
int added = 0;
*total_weight = 0;
for (int i = 0; i < edgeCount && added < n - 1; i++) {
int u = edges[i].u, v = edges[i].v;
if (find(u) != find(v)) {
unite(u, v);
*total_weight += edges[i].weight;
printf("Edge added: %d - %d (weight %d)\n", u, v, edges[i].weight);
added++;
}
}
return added;
}
int main() {
int n = 4; /* A=0, B=1, C=2, D=3 */
edgeCount = 0;
edges[edgeCount++] = (Edge){0, 1, 4}; /* A-B */
edges[edgeCount++] = (Edge){0, 2, 1}; /* A-C */
edges[edgeCount++] = (Edge){1, 2, 2}; /* B-C */
edges[edgeCount++] = (Edge){1, 3, 5}; /* B-D */
edges[edgeCount++] = (Edge){2, 3, 8}; /* C-D */
int total = 0;
int edgesUsed = kruskal_mst(n, &total);
printf("Edges used: %d, Total MST weight: %d\n", edgesUsed, total);
return 0;
}
Sample Input and Output
Using the same graph from my step-by-step example, running this program gives:
Edge added: 0 - 2 (weight 1)
Edge added: 1 - 2 (weight 2)
Edge added: 1 - 3 (weight 5)
Edges used: 3, Total MST weight: 8
This exactly matches my manual computation of Kruskal’s algorithm earlier.
Optimization Techniques
I use path compression and union by rank together in the union-find structure to keep operations nearly constant time. For dense graphs, I switch from Kruskal’s to Prim’s algorithm with a Fibonacci heap to get better asymptotic performance. When the graph changes incrementally over time, I use dynamic MST maintenance techniques instead of recomputing from scratch. For extremely large graphs, I sometimes use Borůvka’s algorithm, which parallelizes well since each round processes all components simultaneously.
Common Mistakes
I have noticed people forget to check for disconnected graphs, which causes their algorithm to silently produce a spanning forest with fewer than $|V|-1$ edges instead of a proper error or forest handling. Another mistake is implementing union-find without path compression or union by rank, which degrades performance to nearly linear per operation instead of near-constant. I also see confusion between minimum and maximum spanning trees, where simply negating weights or reversing the sort order is all that is needed, but people sometimes rewrite the whole algorithm unnecessarily.
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.
- Prim, R.C., “Shortest connection networks and some generalizations,” Bell System Technical Journal, 1957.
- Borůvka, O., “O jistém problému minimálním,” Práce Moravské Přírodovědecké Společnosti, 1926.
- Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., “Introduction to Algorithms,” MIT Press. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/
- Wikipedia overview: https://en.wikipedia.org/wiki/Minimum_spanning_tree
- Sedgewick, R., Wayne, K., “Algorithms,” 4th Edition. https://algs4.cs.princeton.edu/43mst/
