Module 27
Minimum Spanning Trees
Connect every node at the lowest total cost: the cut property, Kruskal with union-find, Prim with a heap, virtual nodes and critical edges.
A spanning tree connects all n nodes of an undirected graph with exactly n − 1 edges and no cycles. A minimum spanning tree (MST) does it with the smallest total weight: the cheapest way to lay cables, pipes or roads so everything is connected.
This module explains why greedy choices are safe here (the cut property), then teaches Kruskal's algorithm (sort edges, add if no cycle, using union-find from Module 25) and Prim's algorithm (grow one tree with a heap, or with arrays on dense graphs). Problems add tricks like a virtual node for "build your own source" options and testing which edges every MST must contain.
Best after: Union-Find (DSU), Heaps and Priority Queues
Part 1
Learn the ideas
- 27.1Kruskal's Algorithm and the Cut PropertySort edges by weight and add each one that joins two different components. The cut property guarantees each added edge belongs to some MST.14 min
- 27.2Prim's AlgorithmGrow one tree from any node, always adding the cheapest edge that leaves it. A heap gives O(E log V); a plain array gives O(V²), best for dense graphs.12 min
Part 2
Solve the problems
In order of difficulty. Each one shows the pattern it teaches.
MST on a complete graph: array-based Prim without building the edges.
Kruskal on an edge list, returning −1 when the graph can't be connected.
A virtual node turns "build a well here" options into ordinary edges, so the whole problem becomes one MST.
Test an edge's role by rebuilding the MST without it and with it forced in.
Two spanning structures sharing edges: take shared edges first, then each person's own.