Minimum Spanning Trees as Greedy Algorithms
For a connected weighted undirected graph, a spanning tree connects every vertex with acyclic edges. An MST minimizes the sum of those edge weights.
Cut property
A cut partitions vertices into two nonempty sets. A lightest edge crossing a cut is safe: some MST contains it, subject to ties. Prim and Kruskal differ mainly in which cut their maintained state exposes.
- Prim's algorithm grows one tree and chooses the lightest edge leaving it.
- Kruskal's algorithm grows a forest and chooses the lightest edge joining two components.
Important boundaries
- Negative weights are valid.
- Equal weights may produce multiple MSTs with the same total cost.
- A disconnected graph has a minimum spanning forest, not one spanning tree.
- An MST minimizes total connection cost, not source-to-vertex path lengths.
With adjacency lists and a binary heap, Prim is commonly ; Kruskal is because edge sorting dominates. Representation and density—not a slogan that one algorithm is always “for sparse” or “for dense”—determine the practical choice.
Why the cut must respect earlier choices
For incremental correctness, start with accepted edges A contained in an MST T, and choose a cut crossed by no edge of A. Let e be a minimum-weight crossing edge. If T omits e, adding e creates a cycle. The path in T between e's endpoints must cross the cut at another edge f. Since f is no lighter than e, replacing f by e cannot increase cost. Because the cut respects A, f is not an accepted edge: the new MST still contains all earlier choices. This is stronger than saying each chosen edge individually belongs to some MST.
On a triangle with all three weights equal to 1, each edge belongs to some MST, but accepting all three produces a cycle. Prim and Kruskal prevent that incompatible combination. With weights A—B:2, B—C:2, A—C:3, both choose the two weight-2 edges, total 4; the shortest A-to-C route instead uses the weight-3 edge. For disconnected input, apply the same argument separately inside each component.
Open full-size imageBlack vertices form S, and white vertices form its complement. Adding the dashed edge e to the red tree path closes a cycle. Removing the crossing edge e′ breaks that cycle while keeping the tree connected; e′ plays the role of f in the proof above. Choosing a lightest crossing edge makes this exchange no more expensive. The source illustration assumes distinct weights; the argument above also allows ties.