Three Greedy Views of a Minimum Spanning Tree
A minimum spanning tree can be built by considering edges globally, growing one connected tree, or merging many components in parallel. These are the ideas behind Kruskal’s, Prim’s, and Borůvka’s algorithms. All three make locally cheapest choices, but those choices occur in different states: Kruskal scans a sorted edge list, Prim maintains a growing vertex set, and Borůvka lets every current component choose an outgoing edge.
Throughout, \(G=(V,E)\) is a finite, connected, simple graph with a weight \(w(e)\) assigned to each edge. A spanning tree is a connected, acyclic subgraph containing every vertex. A minimum spanning tree (MST) is a spanning tree with minimum total edge weight. When weights tie, an algorithm needs a tie-breaking rule to specify its exact choices; the resulting MST need not be unique.
For a precise trace, fix how ties are resolved. In the examples below, a stated edge order breaks ties for Kruskal and Borůvka. Prim’s tie rule is also stated when needed. Different tie rules can change the selected edges, but not the minimum total weight. The correctness results for these algorithms follow from the cut property: a cheapest edge crossing a cut is safe to include in some MST. The exchange argument below explains why ties do not invalidate this fact.
Why a Cheapest Crossing Edge Is Safe
Proof. Choose an MST \(T\). If \(e\in E(T)\), the claim holds. Otherwise, adding \(e\) to \(T\) creates a cycle: the endpoints of \(e\) were already joined by a unique path in the tree \(T\). That path must cross the cut, because its endpoints lie on opposite sides. Let \(f\) be a crossing edge on the path. Since \(e\) is a minimum-weight crossing edge, \(w(e)\leq w(f)\). Removing \(f\) from the cycle leaves a spanning tree \(T'=T+e-f\), and its weight satisfies \(w(T')=w(T)+w(e)-w(f)\leq w(T)\). Since \(T\) was already minimum, \(T'\) is also an MST, and it contains \(e\). \(\square\)
This lemma accounts for the greedy decisions: each selected edge is cheapest across a cut that separates the pieces being joined. Ties can make the resulting tree non-unique, but a tied cheapest edge is still safe. The algorithms’ correctness and termination follow from their established cut-property arguments; the traces here focus on how their states differ.
One Graph, Three Traces
Worked Example: A Graph with a Unique MST
Let \(V=\{a,b,c,d,e,f\}\) and let the weighted edge set be \(ab:1,\ bd:2,\ ac:3,\ bc:4,\ de:4,\ ef:5,\ ce:6,\ df:7,\ cf:8\). The number after the colon is the edge weight. The graph is connected. For ties, use the order in which edges were listed.
Kruskal. Process the edges in nondecreasing weight order, keeping the listed order among equal weights.
| Edge considered | Weight | Decision | Components after decision |
|---|---|---|---|
| \(ab\) | 1 | Accept | \(\{a,b\},\{c\},\{d\},\{e\},\{f\}\) |
| \(bd\) | 2 | Accept | \(\{a,b,d\},\{c\},\{e\},\{f\}\) |
| \(ac\) | 3 | Accept | \(\{a,b,c,d\},\{e\},\{f\}\) |
| \(bc\) | 4 | Reject: endpoints already connected | \(\{a,b,c,d\},\{e\},\{f\}\) |
| \(de\) | 4 | Accept | \(\{a,b,c,d,e\},\{f\}\) |
| \(ef\) | 5 | Accept | \(\{a,b,c,d,e,f\}\) |
Kruskal stops after accepting \(5\) edges, producing \(\{ab,bd,ac,de,ef\}\), with total weight \(1+2+3+4+5=15\).
Prim from \(a\). At each step, choose a minimum-weight edge crossing from the current vertex set to its complement. There are no ties in these choices.
| Current vertex set | Cheapest crossing edge | New vertex set |
|---|---|---|
| \(\{a\}\) | \(ab:1\) | \(\{a,b\}\) |
| \(\{a,b\}\) | \(bd:2\) | \(\{a,b,d\}\) |
| \(\{a,b,d\}\) | \(ac:3\) | \(\{a,b,c,d\}\) |
| \(\{a,b,c,d\}\) | \(de:4\) | \(\{a,b,c,d,e\}\) |
| \(\{a,b,c,d,e\}\) | \(ef:5\) | \(\{a,b,c,d,e,f\}\) |
Prim returns the same five edges, of total weight \(1+2+3+4+5=15\). For example, after the first step the crossing edges are \(ac:3,\ bd:2,\ bc:4,\ de:4,\ df:7\); the minimum is \(bd:2\).
Borůvka. Initially each vertex is its own component. The cheapest outgoing choices are \(a\to ab:1,\ b\to ab:1,\ c\to ac:3,\ d\to bd:2,\ e\to de:4,\ f\to ef:5\). The distinct chosen edges are \(ab,ac,bd,de,ef\). They join all six vertices in one round, so Borůvka returns a spanning tree of weight \(1+3+2+4+5=15\).
Check: Each output has five edges and connects all six vertices without a cycle, so each is a spanning tree. Its total weight is \(15\). Independently, Kruskal’s trace shows that the other edges of weight at most \(5\) either have already-connected endpoints (\(bc\)) or are included; all remaining edges have weight at least \(6\). The selected tree is the unique MST because each of its edges is the unique lightest edge across a cut separating the corresponding parts at the point it is selected.
Ties Can Change the Tree
Worked Example: Different Tie-Breaks, Different MSTs
Let \(V=\{a,b,c,d\}\), with weighted edges \(ab:1,\ bc:1,\ cd:1,\ da:1,\ ac:2,\ bd:2\). The four weight-1 edges form a cycle. Kruskal breaks ties in the order \(ab,bc,cd,da\); Prim starts at \(a\), breaking ties by alphabetical edge order; Borůvka uses alphabetical order to break ties among a component’s cheapest outgoing edges.
Kruskal: Accept \(ab:1\), then \(bc:1\), then \(cd:1\). The edge \(da:1\) is rejected because \(a\) and \(d\) are already connected. The accepted edges form the path \(a-b-c-d\), of weight \(1+1+1=3\).
Prim: From \(\{a\}\), choose \(ab:1\) rather than \(ad:1\), by the stated tie rule. From \(\{a,b\}\), the cheapest crossing edges include \(ad:1\) and \(bc:1\), so choose \(ad:1\). From \(\{a,b,d\}\), choose \(bc:1\) (it crosses to \(c\); \(cd:1\) is also available, and \(bc\) comes first in the tie order). The tree is \(\{ab,ad,bc\}\), again of weight \(1+1+1=3\).
Borůvka: Initially \(a\) and \(b\) choose \(ab:1\), \(c\) chooses \(bc:1\), and \(d\) chooses \(ad:1\), each the alphabetically first cheapest incident edge. The distinct edges \(\{ab,bc,ad\}\) connect all vertices without a cycle. Its weight is \(1+1+1=3\).
Check: Every spanning tree on four vertices has three edges, each of weight at least \(1\), so its weight is at least \(3\). Each displayed output is a spanning tree of weight \(3\), hence is minimum. The outputs differ because of tie-breaking; their equal minimum weights do not depend on that choice.
Proof. For any of the displayed tied choices, the chosen edge is a minimum-weight edge across the cut under consideration. The lemma therefore gives an MST containing that edge. In the four-vertex example, the direct lower bound of \(3\) and the three explicitly checked trees of weight \(3\) establish minimality. Since the edge sets \(\{ab,bc,cd\}\) and \(\{ab,ad,bc\}\) differ, the graph has distinct MSTs. \(\square\)
Disconnected Inputs and Borůvka’s Rounds
Worked Example: A Minimum Spanning Forest
Let \(V=\{1,2,3,4,5\}\), with weighted edges \(12:1,\ 23:2,\ 45:1\). This graph has two connected components, \(\{1,2,3\}\) and \(\{4,5\}\), so it has no spanning tree. The appropriate output is a minimum spanning forest: a minimum spanning tree of each connected component.
Kruskal accepts \(12:1\), \(45:1\), and \(23:2\); all three join different current components. Prim started at \(1\) adds \(12:1\), then \(23:2\), and has exhausted that component. Restarting at \(4\), it adds \(45:1\). Borůvka’s first round has choices \(1\to12,\ 2\to12,\ 3\to23,\ 4\to45,\ 5\to45\); the distinct choices merge each connected component into one tree. Each algorithm returns \(\{12,23,45\}\), with total weight \(1+2+1=4\).
Check: The output has one tree on \(\{1,2,3\}\), with two edges, and one tree on \(\{4,5\}\), with one edge. These are all the input edges, so no alternative forest can have lower total weight.
In a connected graph, Borůvka’s rounds also explain why its components shrink quickly. Each current component chooses an edge leaving it; therefore each resulting connected group contains at least two old components. If there are \(k\) components before a round, there are at most \(k/2\) afterward. Thus the number of rounds is at most \(\lceil\log_2 n\rceil\) before the graph becomes one component.
Proof. Contract each old component conceptually to one object, retaining the chosen edges between distinct objects. Every old component has at least one chosen outgoing edge, so it is joined to at least one other old component in the resulting groups. Consequently, every new component contains at least two old components. If there are \(r\) new components, they contain at least \(2r\) old components in total, so \(2r\leq k\), or \(r\leq k/2\). Repeated halving reaches one component after at most \(\lceil\log_2 k\rceil\leq\lceil\log_2 n\rceil\) rounds. \(\square\)
When equal-weight choices might select a cycle, implementations process the chosen edges and skip any edge whose endpoints are already connected. This preserves a forest. The halving argument still applies: each old component chose an outgoing edge, and if that edge is skipped, its endpoints were already joined by accepted edges in that round, so the old component is still part of a group containing another old component.
Implementation Costs and Practical Differences
The algorithms differ not only in the order of their choices but also in the data they maintain. Here \(n=|V|\) and \(m=|E|\). The bounds below are standard for the indicated implementations, on a connected graph; a disconnected graph can be handled component by component to produce a forest.
| Algorithm | Typical implementation | Time bound | Main work |
|---|---|---|---|
| Kruskal | Sort edges; disjoint-set union | \(O(m\log m)\) | Sort all edges, then test and merge components |
| Prim | Adjacency lists; binary heap | \(O((n+m)\log n)\) | Update priorities of vertices adjacent to the growing tree |
| Borůvka | Scan edges each round; disjoint-set union | \(O(m\log n)\) | Find each component’s cheapest outgoing edge in each round |
Kruskal’s bound is dominated by sorting; disjoint-set operations take near-constant amortized time per edge with path compression and union by rank. Prim’s adjacency-list implementation uses a binary heap to select the cheapest next edge and update candidate weights. Borůvka scans the edges to find cheapest outgoing edges, and the number of rounds is logarithmic by the halving argument. These are implementation-dependent bounds, not claims that one algorithm is always fastest: graph density, data structures, memory layout, and parallel hardware can matter.
Common Pitfalls
Wrong calculation: “Kruskal rejects \(da:1\) in the tie example, so Prim must reject it too.” This confuses an algorithm’s state with another’s. Kruskal has already accepted \(ab\) and \(bc\) when it considers \(da\); Prim’s state depends on its starting vertex and earlier tie-breaks. Starting Prim at \(a\), it can accept \(ad\) and still produce an MST. Check the actual current components or current vertex set before deciding whether an edge is eligible.
Also check connectivity. On a disconnected input, no spanning tree containing every vertex exists. The three methods can instead produce a minimum spanning forest, but Prim must restart in each component, and the output should not be described as a spanning tree of the whole graph.
Check Your Understanding
For each question, state any tie-breaking rule you use and verify the resulting edge set.
- On the four-vertex tied graph, what tree does Kruskal return if the weight-1 edge order is \(da,cd,bc,ab\)?
- Why does a minimum edge crossing a cut remain safe when another edge has the same weight?
- In Prim’s algorithm, why must the next edge cross from the current vertex set to its complement?
- How many Borůvka rounds are sufficient when the initial graph has \(16\) vertices, using the halving bound?
- What should the output be called when the input graph is disconnected, and how does Prim handle that case?