Suppose links have costs and we need to connect every pair of vertices that the original network can connect. Selecting cheap links sounds sensible, but choosing the cheapest edges without checking their structure can waste a link on a cycle. Kruskal's algorithm combines two ideas: consider edges in nondecreasing cost order, and use a disjoint-set structure to determine whether an edge would join two different components.
The data structure answers a structural question, not an optimality question. We will prove separately that the selected edges form the required forest and that their total cost is minimal. This separation also makes disconnected graphs, equal weights and negative costs easier to handle correctly.
State the output for every input graph
Let be a finite undirected weighted multigraph. Parallel edges are distinct input edges, self-loops are allowed, and each edge has an integer weight that may be negative. Number the vertices ; may be zero. Each edge receives its input index, so equal-weight parallel edges can still be distinguished.
Definition 14.1.1
(Spanning forest and minimum cost)
A spanning forest contains every vertex, contains no cycle, and has the same connected components as . Each nontrivial original component is therefore spanned by a tree; an isolated vertex is a one-vertex tree with no edges. A self-loop cannot belong to a forest. For two parallel edges, selecting both would form a cycle of length two in this multigraph convention.
The forest's cost is the sum of its selected edge weights. A minimum spanning forest has minimum cost among all spanning forests of . If is connected and nonempty, this is a minimum spanning tree. When , the empty forest has cost zero.
We do not require the input to be connected, and we do not claim that the optimum is unique. Fixed tie-breaking makes one implementation's result reproducible without making every minimum forest identical.
Sort, then accept only component-joining edges
Start with no selected edges and one disjoint-set element per vertex. Sort input edges by (weight, input index). For each edge in that order, compare find(u) with find(v). If the roots differ, select and union the sets; otherwise skip it. After all edges are examined, return the selected edges and their cost.
A loop has the same endpoint twice, so it is always skipped, even if its weight is negative. A later parallel edge is not automatically skipped: it is skipped only if its endpoints are already connected by selected edges when it is considered.
Common mistake
(Taking the cheapest edges without the cycle test)
Take vertices 0, 1, 2, 3 and edges 0–1, 1–2, 0–2 of weight 1 and 2–3 of weight 5. The three cheapest edges form the triangle: they contain a cycle and leave vertex 3 disconnected, at cost 3. A minimum spanning tree must use 2–3 and two triangle edges, for cost . Counting edges instead of testing components gives a wrong answer.
Proposition 14.1.2
(Kruskal selects a spanning forest)
After every examined edge, the selected edges form a forest whose connected components are exactly the sets of the disjoint-set structure. When the scan ends, the selected edges are a spanning forest of .
Proof
(The selected edges and disjoint sets have the same components)
Initially the selected graph has no edges and the disjoint sets are singletons, so their components agree. If an edge's endpoints are in different sets, by induction they lie in different selected-graph components. Adding that edge joins those components without creating a cycle; union makes exactly the corresponding sets one set. If its endpoints are already in one set, a selected path already joins them, so adding the edge would create a cycle. Skipping it changes neither partition.
Thus the selected edges remain a forest, and find represents exactly its connected components after every step. This proves the cycle test, but by itself it does not prove minimum weight.
When the scan ends, every original edge has endpoints in the same selected component: an accepted edge joined its endpoints, while a skipped edge's endpoints were already joined and never become separated. Every original path is a sequence of such edges, so its endpoints lie in the same selected component. Conversely, selected edges are original edges and cannot connect different original components. The two component partitions agree, so the result is a spanning forest.
Concept lensStructural
The forest as a rule on the edge order
Kruskal's choice can be stated without a procedure: list the edges by the pair ; an edge is selected exactly when no path joins and using only earlier edges in the list. A loop is never selected, since its endpoints are trivially joined. It follows that the output depends only on the order of the edges, not on the weights themselves: replacing every weight by , a strictly increasing function, selects the same edges.
Why the greedy choice can be part of an optimum
Theorem 14.1.3
(Kruskal's forest has minimum cost)
For every finite undirected weighted multigraph, including graphs with negative weights, parallel edges, self-loops and several components, the forest returned by Kruskal's algorithm is a minimum spanning forest.
Proof
(Exchange across a cut, including ties and negative weights)
We prove by induction that some minimum spanning forest contains all edges selected so far. This is true initially: the finite graph has finitely many possible forests, so an optimum exists.
Suppose the algorithm next selects . Let be the selected-forest component containing just before ; lies outside . Consider any original edge crossing this cut. If , the scan considered earlier. Its endpoints are still in different selected components now, because one lies in and the other outside; as components only merge, they were different when was considered too. Kruskal would have selected it, contradicting the current cut. Thus every cut-crossing edge has weight at least .
Choose an optimum containing all previously selected edges. If it already contains , it satisfies the induction step. Otherwise are in the same original component, so the tree of on that component has a unique – path. This path must cross the cut at some edge . No previously selected edge crosses the cut: is a component of the selected forest. Therefore removing keeps all previously selected edges. Adding to creates one cycle; deleting gives another spanning forest with cost no larger because .
Since was already minimum, the new forest is also minimum and contains the previous selected edges plus . Induction establishes the claim. At the end, the selected forest is itself spanning. Because both it and the optimum containing it are trees on each original component, neither can contain an additional edge without a cycle; they are equal. The returned forest is minimum.
Proof X-ray
Where the sorted order enters
The step that does the work is the inequality for every edge crossing the cut. It rests on two facts: the scan runs in order of weight, and components only merge, so a lighter crossing edge would already have been accepted. The exchange itself uses only that is a component of the selected forest, so the removed edge was never selected before. The signs of the weights never enter. Without the sorted order the first fact fails, as the example below shows.
The proof compares weights; it never assumes they are positive. Equal weights permit an exchange of equal cost and can yield several different minimum forests. The input index decides which one this implementation selects when costs tie.
Counterexample mode
The cycle test without the sort is not enough
Take vertices 0, 1, 2 and edges listed in input order as 0–1 of weight 5, 1–2 of weight 1 and 0–2 of weight 1. Applying only the cycle test in this order accepts 0–1, then accepts 1–2, and skips 0–2 because 0 and 2 are already connected. The cost is . The two weight-1 edges alone form a spanning tree of cost 2, so the result is not minimum. The cycle test certifies acyclicity; the order by (weight, index) is what makes every crossing edge at least as heavy as the accepted one.
Trace ties, a loop, a parallel edge and an isolated vertex
Worked example 14.1.4
(A disconnected input still has a well-defined optimum forest)
Use vertices and the indexed edges below. Vertex 4 is isolated.
| Index | Edge | Weight | Result |
|---|---|---|---|
| 0 | 0–1 | 1 | select |
| 1 | 0–2 | 1 | select |
| 2 | 1–2 | 1 | skip: cycle |
| 3 | 1–3 | 3 | skip: already connected |
| 4 | 2–3 | 2 | select |
| 5 | 3–3 | -5 | skip: loop |
| 6 | 0–1 | 4 | skip: parallel edge would close a cycle |
The processing order is indices , sorted by weight and then index. The selected edge indices are , with cost . The final selected components are and , matching the original graph. A different tie rule could select another two of the three weight-1 edges, still with minimum cost 4.
Worked example 14.1.5
(Parallel edges: the lighter copy wins)
Take vertices 0, 1, 2 and the indexed edges 0: 0–1 of weight 3, 1: 0–1 of weight 2, 2: 1–2 of weight 4, 3: 0–2 of weight 4. The processing order is indices . Edge 1 is selected. Edge 0 is a parallel copy whose endpoints are already connected, so it is skipped although it comes first in the input. Edge 2 joins vertex 2 to and is selected; edge 3 would close a cycle and is skipped. The selected indices are , with cost . The tie between edges 2 and 3 is broken by index; selecting edge 3 instead would give another minimum forest of the same cost.
Common mistake
(Deleting parallel edges by input order)
Keeping only the first of several parallel edges is not safe. In the example above the first copy of 0–1 has weight 3, so a graph built from the first copies has minimum forest cost , whereas the cheaper copy gives 6. Parallel edges must all reach the sort.
Implement the disjoint sets
The following implementation uses union by size without path compression. Each root stores its component size; nonroot size entries need not be current. find follows parent links until a root. When joining different roots, make the root of the smaller tree a child of the larger. Equal sizes are resolved in favor of the first root passed to union.
class DisjointSets:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, vertex):
while self.parent[vertex] != vertex:
vertex = self.parent[vertex]
return vertex
def union(self, left, right):
a, b = self.find(left), self.find(right)
if a == b:
return False
if self.size[a] < self.size[b]:
a, b = b, a
self.parent[b] = a
self.size[a] += self.size[b]
return True
def minimum_spanning_forest(n, edges):
if n < 0:
raise ValueError("vertex count must be nonnegative")
indexed = []
for index, (u, v, weight) in enumerate(edges):
if not 0 <= u < n or not 0 <= v < n:
raise ValueError("edge endpoint outside the vertex range")
indexed.append((weight, index, u, v))
indexed.sort()
sets = DisjointSets(n)
selected = []
cost = 0
for weight, index, u, v in indexed:
if sets.union(u, v):
selected.append(index)
cost += weight
return cost, selected
Input is a nonnegative integer n and an iterable of triples (u, v, weight) with integer endpoints and weights. The code validates endpoint ranges but assumes the stated types and triple structure. It builds a separate indexed list and does not mutate the caller's edge collection. Returned indices name the original edges; their order is the greedy processing order. For n=0, the edge list must be empty and the return is (0, []).
Proposition 14.1.6
(Union by size keeps parent chains short)
With union by size and no path compression, on vertices every find follows at most parent links. Hence find and union take steps.
Proof
(Why union by size keeps parent chains short)
Whenever a root becomes a child, its entire tree is no larger than the root's new partner. Every vertex whose depth increases then belongs to a set at least twice the size of its previous set. A vertex starts in a singleton, and its set never contains more than vertices. Its depth can therefore increase at most times when .
Consequently find and one union use parent-link steps. This simple bound uses no path-compression theorem. The sizes refer to whole sets at the time of union; a nonroot's stale size is never used to select a new parent.
For input edges, indexing and initialization cost ; comparison sorting costs . The union attempts cost , giving
time and additional cells, including the indexed list and output. This is an operation-count bound: arbitrary-size integer comparisons and additions have their own bit costs. A more sophisticated union–find with path compression can have a sharper amortized bound, but it is not what this code implements.
Worked example 14.1.7
(Union by size on four vertices, and the smallest inputs)
Process the edges 0–1, 2–3, 0–2 of a four-vertex graph in this order. union(0,1) joins roots 0 and 1 of equal size, so root 1 becomes a child of 0 and size[0] becomes 2. union(2,3) makes 3 a child of 2. union(0,2) compares the equal sizes 2 and 2, so root 2 becomes a child of 0 and size[0] becomes 4. The deepest vertex is 3, at depth 2, matching .
At the smallest inputs the function returns (0, []) for with no edges, and also for with a single self-loop of weight , because union(0,0) finds equal roots and returns false.
Exercises with solutions
Quick check
(1. Why is a negative self-loop skipped even though it would lower the sum of the chosen edge weights?)
Solution · Solution 1
A spanning forest must be acyclic, and a self-loop is already a cycle. Its endpoints are the same vertex, so union returns false and Kruskal skips it. The goal is minimum cost among valid spanning forests, not minimum cost over arbitrary edge subsets.
Quick check
(2. In the five-vertex example, list the selected edge indices and final components. Does the isolated vertex invalidate the result?)
Solution · Solution 2
The indices are [0, 1, 4], with total cost 4. The components are and . The isolated vertex forms its own one-vertex tree and must be retained; the output is a minimum spanning forest, not a single spanning tree of the whole disconnected graph.
Quick check
(3. Three vertices have edges 0–1, 1–2 and 0–2, all of weight 1. Is the minimum spanning tree unique?)
Solution · Solution 3
No. Any two edges connect all three vertices without a cycle and have total cost 2. Deterministic input-index tie-breaking chooses one of these optima; it does not remove the other valid optimum trees.
Quick check
(4. Why does a skipped edge never need to be reconsidered to make the final forest span each original component?)
Solution · Solution 4
When it is skipped, its endpoints already lie in one selected component. Later unions can merge components but never split them, so its endpoints remain connected. At the end this holds for every original edge, and hence for every original path. Thus each original connected component is connected in the selected graph; selected edges cannot connect separate original components.
The greedy proof and the data-structure proof do different jobs. The exchange argument establishes minimum weight, while the disjoint-set invariant makes the cycle decision efficient. Neither alone is a substitute for checking the other.