A network designer must connect sites using the cheapest set of links, where each possible link has a cost. The answer is a minimum spanning tree. Two classical algorithms build one, and both are justified by one structural fact, the cut property. Kruskal's algorithm also needs a data structure that tracks which vertices are already connected, the disjoint-set union (union–find). This unit uses the shortest-path ideas from Dijkstra's algorithm only for comparison; the main prerequisite is the graph vocabulary of the connectivity and traversal units: connected, cycle, tree and component.
1. Spanning trees and the problem
Definition 18.1.1
(Spanning tree and minimum spanning tree)
Let be a finite, connected, undirected graph with vertices, with a real weight on each edge. Parallel edges may be present; self-loops are never useful and are ignored. A spanning tree is a set such that is connected and acyclic. Every spanning tree has exactly edges, and adding any non-tree edge to a spanning tree creates exactly one cycle. A minimum spanning tree (MST) is a spanning tree of minimum total weight . Several MSTs may exist when weights tie, but they all have the same weight. Weights may be negative; only their order matters.
Definition 18.1.2
(Cut, crossing edge and respecting set)
A cut is a partition with both parts nonempty. An edge crosses the cut if one endpoint is in each part. A set of edges respects the cut if no edge of crosses it.
2. The cut property
Theorem 18.1.3
(Cut property)
Let for some MST . Let be a cut that respects, and let be a crossing edge of minimum weight among all edges crossing the cut. Then for some MST .
Proof
(Swapping a cycle edge for the lightest crossing edge)
If take . Otherwise contains exactly one cycle, and it passes through . The cycle starts on one side of the cut and returns to it, so it crosses the cut an even number of times; is one crossing, so at least one other edge of the cycle crosses, and since the cycle's other edges are in . As respects the cut, . By the choice of , . Let . Removing from leaves two components, and because lies on the unique cycle of , the endpoints of lie in different components; so is connected with edges, hence a spanning tree. Its weight is , so is an MST, and it contains .
Proof X-ray
Where each hypothesis of the cut property is used
The cycle in exists because and is a spanning tree. That crosses the cut, together with the even number of crossings of a cycle, produces a second crossing edge on the cycle. That respects the cut is used exactly once: it shows , so deleting does not remove anything of . The minimality of among crossing edges is used exactly once: it gives , so the swap does not raise the weight. Finally lies on the cycle, so reconnects the two components of and the result is again a spanning tree.
This is an exchange argument: we start from an arbitrary optimal solution and swap one element for the greedy choice without losing optimality. A greedy algorithm that adds, at each step, an edge licensed by the cut property therefore keeps the invariant "the chosen edges are contained in some MST".
Counterexample mode
The respecting hypothesis cannot be dropped
Claim: if lies in some MST and is a minimum-weight edge crossing some cut, then lies in some MST, whether or not respects the cut. Take the triangle on vertices with all three edge weights equal to . Then is an MST, of weight . For the cut the crossing edges are and , both of weight , so is a minimum-weight crossing edge. But contains the crossing edge , and is the whole triangle, which contains a cycle and lies in no spanning tree. The repair is the hypothesis that respects the cut: then the edge removed in the proof is never in .
3. Disjoint-set union
Definition 18.1.4
(Disjoint-set union)
A disjoint-set structure maintains a partition of into sets and supports find(x), returning a representative of the set containing (the same representative for all elements of a set until it changes), and union(x,y), merging the two sets.
Represent each set as a rooted tree stored in an array parent, where a root has parent[r]=r and is the representative, and store size[r] for roots.
make: parent[i] = i; size[i] = 1 for each i
find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving
x = parent[x]
return x
union(x, y):
a = find(x); b = find(y)
if a == b: return false
if size[a] < size[b]: swap a, b
parent[b] = a; size[a] = size[a] + size[b]
return true
Lemma 18.1.5
(Union by size bounds the depth)
If only union by size is used, every tree has depth at most , so find costs .
Proof
(Depth increases only when the tree size doubles)
The depth of a vertex increases by one only when the root of its tree is attached under another root, which happens only when the tree containing has size at most the size of the other tree. The merged tree then has at least twice the size of the tree that held before. A tree has at most vertices, so 's tree size can double at most times. Hence depth is at most .
Path halving only shortens paths, so the lemma still bounds depth. It is a standard result, which we cite and do not prove here, that union by size together with path compression or halving performs any sequence of operations on elements in total time, where is the inverse Ackermann function, below 5 for any input that fits in memory. For this unit it is enough to treat each operation as , which already suffices for the bounds below.
4. Kruskal's algorithm
sort edges so that w(e_1) <= w(e_2) <= ... <= w(e_m)
T = empty; make the disjoint sets
for i = 1..m:
(u, v) = e_i
if union(u, v): add e_i to T
return T
The edge is accepted exactly when its endpoints lie in different components of the current forest .
Theorem 18.1.6
(Correctness of Kruskal's algorithm)
For a connected graph, Kruskal's algorithm returns an MST.
Proof
(Each accepted edge is a lightest crossing edge)
We show by induction that, after each step, the edge set is contained in some MST. Initially . Suppose edge is accepted, and for an MST . Let be the vertex set of the component of containing ; then . No edge of crosses , so respects the cut, and crosses it. Let be any other edge crossing the cut. If came earlier in the sorted order, it is not in (no edge of crosses the cut), so it was examined and rejected, which means its endpoints were already connected by the forest at that time, and the forest only grows, so its endpoints would now lie in the same component; but crosses the cut, a contradiction. Hence every crossing edge other than comes later in the order, with . So is a minimum-weight crossing edge, and by the cut property lies in some MST. Rejected edges are not added, so the invariant persists.
At the end, is a forest. Suppose it had at least two components. Because is connected, some edge of joins two different final components. When was examined, its endpoints were in different components, since components only merge, so would have been accepted, a contradiction. So is a spanning tree contained in an MST, hence it is that MST.
Proof X-ray
Why an accepted edge is a lightest crossing edge
The non-routine step is to extract a cut from the algorithm's state: take to be the component of in the current forest, so the forest respects the cut by construction. Two facts then make a lightest crossing edge. The order is sorted, so any crossing edge examined later is at least as heavy. And components only merge, so a crossing edge examined earlier would have been rejected only if its endpoints were already connected, which a crossing edge never is; hence no crossing edge came earlier. The final argument is separate and uses the connectivity of : an edge joining two final components would have been accepted. Without the sorted order, the cut argument gives nothing.
If is not connected, the same algorithm returns a minimum spanning forest.
Complexity. Sorting costs , which is when there are no parallel edges because then . The union–find operations cost with the lemma, or with the cited result. Total , that is without parallel edges.
Concept lensStructural
The tree as a record of every threshold
For each real , let be the graph on with the edges of weight at most . After Kruskal has examined all such edges, every rejected edge had endpoints already connected and every accepted edge joined two components, so the forest has the same components as . Hence two vertices are connected in exactly when the tree path between them has all weights at most : the heaviest edge on that path is the smallest threshold at which the vertices connect. In the example below, vertices and are not connected in but are in , and the heaviest edge on their tree path is .
5. Prim's algorithm
Prim grows a single tree from a root . Keep a vertex set (initially ) and a tree . Repeatedly choose a minimum-weight edge with exactly one endpoint in , add it and its new endpoint.
With a binary heap of candidate edges ordered by weight, push every edge leaving ; repeatedly pop the smallest, discard it if , otherwise add to , add the edge to , and push all edges from to vertices not in .
Correctness. At each step the tree edges lie in , so they respect the cut ; the chosen edge is a minimum-weight crossing edge, and the cut property keeps the invariant " is contained in some MST". After additions is a spanning tree inside an MST. The heap holds at most entries, so the time is , which is without parallel edges. The structure resembles Dijkstra's algorithm, but the key of a vertex is the weight of a single connecting edge rather than the length of a path.
6. Worked example: Kruskal with the union–find trace
Worked example 18.1.7
(Kruskal with the union–find trace)
Vertices and edges (4), (1), (2), (5), (8), (10), (3). Sorted by weight: (1), (2), (3), (4), (5), (8), (10). When sizes tie, union(x,y) attaches the root of under the root of .
- : roots 1 and 3, sizes 1 and 1 tie;
parent[3]=1,size[1]=2. Accept. - :
find(2)=2,find(3)=1; 's tree has size 1, smaller than 2, soparent[2]=1,size[1]=3. Accept. - : tie;
parent[5]=4,size[4]=2. Accept. - : both roots equal 1. Reject (it would close the cycle ).
- :
find(2)=1(size 3),find(4)=4(size 2);parent[4]=1,size[1]=5. Accept. - : same root. Reject. 7. : same root. Reject.
The MST is with weight , and it has edges.
Worked example 18.1.8
(A disconnected graph gives a forest)
Take vertices and edges (1) and (2). Kruskal accepts because find(1) and find(2) differ, and accepts in the same way. The output has edges, but a spanning tree on vertices needs . The components and are never joined because no edge connects them, so the output is a minimum spanning forest of weight . In general a forest with components on vertices has edges, so accepting fewer than edges signals that the graph is disconnected.
7. Worked example: Prim on the same graph
Worked example 18.1.9
(Prim on the same graph)
Start at .
- : crossing edges (4), (1). Choose .
- : crossing edges (4), (2), (8), (10). Choose .
- : crossing edges (5), (8), (10). Choose .
- : crossing edges (10), (3). Choose .
Total , the same tree as Kruskal's.
8. Common mistakes
- Treating Kruskal's rejected edges as errors: they are exactly the edges whose endpoints are already connected.
- Applying either algorithm to a directed graph. Minimum spanning arborescences need a different algorithm.
- Running Prim or Kruskal on a disconnected graph and expecting a tree: the result is a forest with one tree per component.
Common mistake
(Reusing a stale find result)
The roots change as unions are performed, so a find result computed for an earlier edge may be out of date. Call find again for each edge at the moment it is examined.
Common mistake
(Assuming the MST is unique)
The MST is unique when all weights are distinct, as the last exercise shows. With ties it need not be: the triangle with all three weights equal to has three MSTs, one for each pair of edges, all of weight .
Common mistake
(Reading shortest paths off the MST)
An MST minimizes total weight, not distances. For the triangle with , , , the only MST is , in which the path from to has length , while the edge has length .
Exercises
Exercise 18.1.10
(Vertices with edges (3), (1), (3), (2), (4). Find the weight of an MST and list all MSTs.)
Core
Solution(3)
- 1
Run Kruskal on the sorted edges
Sorted: (1), (2), then and (3), then (4). Kruskal accepts and , giving components and . The next edge, or , joins them, so three edges are accepted and the weight is .
- 2
Show that nothing lighter exists
Key step
The edge weights in increasing order are , so any three distinct edges weigh at least .
Because: Every spanning tree has exactly edges.
- 3
List the MSTs
Weight requires the edges of weights , and one of the two weight- edges. The sets and are both trees. So the MST weight is and the MSTs are exactly these two.
Quick check
(Starting from singletons with union by size and the tie rule that attaches the root of under the root of , perform union(1,2), union(3,4), union(1,3). Give the parent array and the depth of vertex 4.)
Track the sizes of the roots.
Solution · Answer
union(1,2): tie, parent[2]=1, size[1]=2. union(3,4): tie, parent[4]=3, size[3]=2. union(1,3): roots 1 and 3, sizes 2 and 2 tie, parent[3]=1, size[1]=4. The parent array for vertices is . Vertex 4 goes , depth 2, which equals , the bound of the lemma.
Quick check
(Run Prim from vertex on the graph of the first exercise (edges (3), (1), (3), (2), (4)) and give the total weight.)
List the crossing edges at each step.
Solution · Answer
: crossing (3), (1); take . : crossing (3), (3), (4); take or (a tie; say ). : crossing (2), (4); take . Total , matching the Kruskal result.
Exercise 18.1.11
(Prove that if all edge weights of a connected graph are distinct, its MST is unique.)
SynthesisProof
Solution(4)
- 1
Assume two different MSTs and take the lightest edge in exactly one of them
Suppose are both MSTs, and let be the lightest edge lying in exactly one of them. By symmetry of the roles, assume .
Because: Weights are distinct, so this edge is unique.
- 2
Find the cycle and an edge outside
The set contains a cycle through . This cycle has an edge , otherwise the cycle would lie in , which is acyclic. Then and , so lies in exactly one of the trees.
- 3
Compare weights
Key step
Hence .
Because: is the lightest edge in exactly one tree, and weights are distinct.
- 4
Swap to get a lighter tree
∎is a spanning tree, because lies on the unique cycle of , and its weight is . This contradicts that is an MST.