Minimum Spanning Trees (Kruskal, Prim)

Math for CS · Axiom Academy

Kruskal's, Prim's, and the cut property Both Kruskal's and Prim's algorithms are greedy, and both are correct. Their correctness rests on a single powerful theorem. A cut is a partition of V into two non-empty sets. An edge crosses the cut if its endpoints are in different sets. The cut property says: the lightest crossing edge is always safe to include in the MST. Sort all edges by weight (ascending). 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 to the MST and merge their components. Stop when n - 1 edges have been added. Union-Find (Disjoint Set Union) The key data structure is Union-Find , which supports two operations: Find( x ): Return the representative of x 's component Union( x, y ): Merge the components containing x and y With union by rank and path compression , each operation takes nearly O(1) amortized time — specifically where is the inverse Ackermann function, which is for any practical input size. Sort: (B,C,1), (A,C,2), (D,E,3), (A,B,4), (B,D,5), (C,D,8), (C,E,10) Add (B,C,1) : components merge Skip (A,B,4) : A and B already in same component Add (B,D,5) : merge all into . Done — 4 edges. Start with any vertex s . Initialize the tree . Maintain a priority queue of edges crossing the cut between T and . Extract the minimum-weight crossing edge (u, v) . Add v to T . Add all edges from v to non-tree vertices to the priority queue. Repeat until T includes all vertices.

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