Prerequisite: minimum spanning trees and Kruskal’s algorithm.
1. Setting and problem
Let be a finite, connected, undirected, loopless simple graph with . Let be a weight function. Weights may be negative, and several edges may share a weight. Fix an integer with .
Definition
(Spanning forest and its weight)
A spanning forest is an acyclic edge set , viewed on all vertices. Its weight is .
Problem. Among all spanning forests with exactly connected components, find one of minimum weight.
2. Edge-count characterization
Lemma
(Components of a forest)
A forest on vertices has exactly components.
Proof
(Counting components edge by edge)
Start with no edges, so there are components. Add the edges of one at a time. Each added edge lies in the acyclic set , so at the moment it is added its endpoints are in different components. Otherwise it would close a cycle. Each addition therefore reduces the component count by exactly one.
So a forest has exactly components if and only if it has exactly edges. Feasible forests always exist. Since is connected, it has a spanning tree with edges, and deleting any of those edges leaves a forest with edges. Call a forest optimal if it minimizes weight among all forests with edges.
3. Algorithm and tie policy
Tie policy. Number the edges arbitrarily but fixed. Then order edges by the pair lexicographically. This is a strict total order . Every statement " comes after " below refers to , and it implies .
Algorithm .
- Initialize a union–find structure with one singleton set per vertex. Set .
- Scan the edges in -order. For each edge , stop immediately if . Otherwise, if , add to and . If the two finds agree, reject .
- Return .
If , the algorithm returns without accepting any edge.
Termination with enough edges. Suppose the scan ends with . Then has more than components. By connectivity, some edge joins two distinct final components. Components only merge over time, so and were in different components when was scanned. The algorithm would then have accepted , which is a contradiction. Hence , and is a forest because every accepted edge joins two different components.
4. Correctness: an exchange invariant
Theorem
(Correctness of the stopped Kruskal algorithm)
Let be finite, connected, undirected and simple, let be any real weight function (negative weights and ties allowed), let , and order the edges by . Then returns a spanning forest with exactly components whose weight is minimum among all such forests; that is, it returns an optimal forest.
Proof
(Setting up the exchange invariant)
Let be the accepted edges in acceptance order, and let .
Invariant . Some optimal forest contains .
holds trivially. At , an optimal forest contains , and both have edges, so the optimal forest equals the output. It remains to show that implies for .
Assume is optimal and . Let . If , we are done. Otherwise, the following key lemma applies.
Lemma
(Edges of an optimal forest come later)
Let be the first accepted edges, let be a forest with , and let be the next accepted edge, with . Then every comes after in .
Proof
(Rejected earlier edges would close a cycle)
Suppose . The edges accepted before was scanned are exactly . Since , was rejected. At that moment its endpoints were joined by a path in some . That path together with forms a cycle inside . This contradicts acyclicity. Also because .
Proof
(The exchange step in two cases)
Now consider . Exactly one of two cases occurs.
Case A: joins two different components of . Then is still a forest, since it creates no cycle, and it has edges. We need one edge to remove. Count: , so choose any . Removing an edge from a forest leaves a forest. So is a forest with edges and . By the later-edges lemma, , hence . Thus is optimal.
Observe that this case cannot arise in the ordinary spanning-tree proof, because there is connected. Here may have components, so the case must be handled.
Case B: both endpoints of lie in one component of . Then contains a unique cycle through . The set is a forest, so . Choose . Then , so . Deleting a cycle edge preserves connectivity within that component. Therefore is a forest with the same components as , it has edges, and it contains . By the later-edges lemma, .
In both cases holds.
Nothing in the proof uses the sign of . Negative weights and ties are fully covered.
Proof X-ray
Why the exchange covers forests
Maintain an optimal forest containing the edges accepted so far. If the next accepted edge closes a cycle in that forest, remove a different edge on the cycle. If it joins two of the optimal forest’s components, adding it creates no cycle, and any edge outside the accepted prefix can be removed. In both cases the removed edge was considered later than the accepted edge: an earlier rejected edge would form a cycle inside the optimal forest. Therefore its weight is no smaller, and the exchange retains an optimum.
5. Worked trace
Worked example
(Stopped Kruskal with a negative weight and a tie)
Take with vertices and . The target is edges.
| index | edge | weight |
|---|---|---|
| 1 | ||
| 2 | ||
| 3 | ||
| 4 | ||
| 5 | ||
| 6 | ||
| 7 | ||
| 8 |
The -order is . The tie between and breaks by index , and the tie between and breaks by index .
| step | edge | finds equal? | action | components | |
|---|---|---|---|---|---|
| 1 | no | accept | 1 | ||
| 2 | no | accept | 2 | ||
| 3 | no | accept | 3 | ||
| 4 | yes | reject | 3 | unchanged | |
| 5 | no | accept | 4 |
The scan stops with . The output is with weight .
Worked example
(The opposite tie policy gives another optimal forest)
Ties matter for which forest is returned, not for its weight. Under the opposite tie policy for weight 3, the algorithm would accept instead of . That gives with components and , also of weight . Both forests are optimal, and the fixed policy simply makes the output deterministic.
Worked example
(The extreme values of )
Use the graph of the trace. For the target is edges, so the scan stops before accepting anything and returns of weight : six singleton components. For the target is edges, so the scan continues beyond the stopping point of the trace. The edges , , are accepted, is rejected and is accepted as before. Since , the scan goes on: (weight , index ) joins to the large component, so and the scan stops. The output is a minimum spanning tree of weight . The last accepted edge has positive weight; with exactly one component the algorithm must accept it.
Common mistake
(Stopping after k edges instead of n-k edges)
The scan stops at accepted edges, not at . In the trace with and , stopping after two edges would return , which has four components. The two counts coincide only when .
Common mistake
(Refusing an edge because its weight is positive)
Because the problem asks for exactly components, the algorithm must keep accepting edges until it has of them, even when the next acceptable edge has positive weight. In the trace, has weight but is accepted; discarding it would leave a forest with three edges and three components, which solves a different problem.
6. Exactly, at most, and at least components
Every performs the same scan and differs only in when it stops. Hence extends by the next accepted edge. Writing for the optimal exactly- weight, the full run here accepts in that order, which gives:
| 6 | 5 | 4 | 3 | 2 | 1 | |
|---|---|---|---|---|---|---|
Concept lensStructural
Optimal forests are a spanning tree with its heaviest edges removed
Because extends , the optimal forest with components is the minimum spanning tree with the last of its accepted edges deleted. Here the tree loses to give the optimal two-component forest, of weight , and loses as well to give the optimal three-component forest , of weight . The stopping rule is thus a cut of one fixed tree, and the sequence records the weights of its prefixes.
The sequence first falls and then rises. With negative weights, there is no monotonic relationship between and the optimum. Each additional edge adds its own weight, and that weight may be negative or positive.
- At most components means at least edges. The optimum is . For that is .
- At least components means at most edges. The optimum is . For that is , attained at with .
Accepted weights are nondecreasing in acceptance order, so these minima are easy to locate. For "at most ", run and then keep accepting while the next accepted weight is negative. For "at least ", stop at edges or just before the first accepted edge of positive weight, whichever comes first. Zero-weight edges may go either way without changing the weight.
Counterexample mode
Exactly k components is not at most k components
Claim: the forest returned by also has minimum weight among all forests with at most components. Take the graph of the trace and , so and returns of weight . The set is also a forest; it has components and weight . So is not optimal for at most five components. The theorem is a statement about the exact count, because the exchange argument keeps the number of edges fixed at . The repair is the rule above for at most components: after , keep accepting while the next accepted weight is negative. Here that accepts (weight ) and then stops, since the next accepted weight is not negative, and it gives .
7. Complexity and caveats
- Initialization: make-set operations take time.
- Sorting: comparison sorting of edges under costs . For , simplicity gives , so this is also . Stopping early does not reduce the worst-case sorting cost, since the sort finishes before the scan begins. For one may skip the sort and return .
- Union–find: with union by rank and path compression, the at most finds and unions take time. Without a balancing rule, individual finds can cost in the worst case. The stated bound therefore depends on the implementation.
- Total: : initialization contributes , and for a connected graph with the sorting term absorbs the union–find scan. The single-vertex graph has no edges and takes time. Non-comparison sorts, such as radix sort on bounded integer weights, can do better but lie outside the comparison model.
8. Quick checks
Quick check
(A forest on 10 vertices has 7 edges. How many connected components does it have?)
Solution · Answer
By the component-count lemma it has components.
Quick check
(For the graph of the trace and , what does return, and what is its weight?)
Solution · Answer
The target is edges. The scan accepts , and and then stops, so the output is with weight , which equals in the table.
Quick check
(All edges have weight and . Which forest does return?)
Solution · Answer
The target is one edge. All weights tie, so the order is the order of the indices, and the scan accepts the edge with index . The output is , of weight ; the first scanned edge is always accepted, because a single edge cannot close a cycle.
Quick check
(Every weight is increased by . Does the output of change?)
Solution · Answer
No. The order is unchanged, so the scan accepts the same edges. Every candidate forest has exactly edges, so all weights shift by the same amount and the minimizer stays the same. This would fail for the at-most- problem, where the number of edges varies.