Minimum Spanning Trees as Greedy Algorithms

For a connected weighted undirected graph, a spanning tree connects every vertex with $V-1$ 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 $O(E\log V)$; Kruskal is $O(E\log E)$ because edge sorting dominates. Representation and density—not a slogan that one algorithm is always “for sparse” or “for dense”—determine the practical choice.

Source

• Princeton Algorithms: Minimum Spanning Trees