Minimum Spanning Trees

Discrete Math · Axiom Academy

Discovering Kruskal's and Prim's greedy algorithms for finding the minimum spanning tree, with proofs using the cut property and union-find data structures. For a graph with n vertices, a spanning tree always has exactly n - 1 edges. Among all possible spanning trees, the MST has the smallest total weight. The Strategy: Sort all edges by weight, then greedily add edges from smallest to largest, skipping any edge that would create a cycle. Sort all edges in non-decreasing order by weight Initialize each vertex as its own component For each edge (u, v) in sorted order: If u and v are in different components, add the edge Otherwise, skip it (would create a cycle) The Strategy: Start from any vertex and greedily grow the tree by always adding the minimum-weight edge that connects the tree to a new vertex. Start with any vertex as the initial tree Repeat until all vertices are in the tree: Find the minimum-weight edge connecting a tree vertex to a non-tree vertex Add this edge and the new vertex to the tree 4. The Cut Property (Proof of Correctness) Both algorithms work because of a fundamental theorem called the Cut Property , which guarantees that greedy choices lead to an optimal MST. Both algorithms produce an MST, but they differ in approach and performance characteristics.

This is the written version of the interactive lesson above. See the full Discrete Math course.