Minimum spanning trees
A minimum spanning tree connects every node with the least total weight and no loops: the cheapest way to wire up a network. Two greedy algorithms find it, Kruskal's and Prim's.
Connect every node with the least total weight
You must connect five buildings with cables, and each possible cable has a price. You don't need every cable, only enough that every building can reach every other. Any loop would be wasted money: removing one cable of a loop keeps everything connected. So the answer is a set of links with no loop that touches every node, a spanning tree, which always has exactly n − 1 links.
A minimum spanning tree (MST) is a spanning tree with the smallest total weight. Networks, road and pipe layouts, and grouping similar items (stop adding links when they get too long, and the pieces are the groups) all reduce to it.
Both classic algorithms rest on one fact, the cut property: split the nodes into two groups in any way you like; the cheapest link crossing between them belongs to a minimum spanning tree. Both are greedy: they keep taking the cheapest safe link, and the cut property proves that never goes wrong.
The rule
Split the nodes in two any way you like: the cheapest link across the split can always be part of a minimum spanning tree. Kruskal's algorithm and Prim's algorithm each take such a link n − 1 times.
Kruskal's algorithm takes the cheapest links that don't close a loop
Kruskal's algorithm sorts every link by weight and walks the list, keeping a link unless its ends are already connected. That is exactly the question Union-find answers: find both roots; the same root means the link would close a loop.
Cable 2–4 was the fourth cheapest, but 2 and 4 were already joined through 0 and 1. Each kept link is the cheapest crossing between its two pieces, so the cut property says it is safe.
Prim's algorithm grows one tree from a start node
Prim's algorithm keeps a single tree and grows it: at each step, add the cheapest link from a node in the tree to a node outside it. That link crosses the split "tree" versus "the rest", so the cut property again says it is safe. A priority queue holds the candidate links; an entry whose far end has joined the tree in the meantime is skipped, as in Dijkstra's algorithm.
The total is the same 11. When several links tie, the two algorithms may choose different trees, but every minimum spanning tree has the same total.
On a dense graph, skip the heap and scan an array
Here every pair of points can be joined, so there are about n² ÷ 2 links: too many to list and sort. Prim's algorithm doesn't need the list. Keep, for each point outside the tree, its cheapest link to the tree so far. Each round, scan for the smallest, add that point, and update the others with their distance to it.
Each round costs O(n), so the whole run is O(n²), better than O(n² log n) for sorting every link. That is the version to use when the graph is dense.
Kruskal for a list of links, Prim for a dense graph
Algorithm | Cost | Best for |
|---|---|---|
Kruskal's algorithm | O(m log m) to sort, then O(log n) amortized per link | Links given as a list; sparse graphs |
Prim's algorithm with a heap | O(m log m) | Adjacency lists; growing from one node |
Prim's algorithm with an array | O(n²) | Dense graphs, such as all pairs of points |
A minimum spanning tree is not a set of shortest routes. In the cable example, buildings 0 and 3 are joined directly for 5, but the route between 3 and 4 inside the tree costs 5 + 1 + 2 = 8, more than their direct cable at 7. The tree minimizes the total, not any one route; for routes, use Dijkstra's algorithm.
3 questions
Remember this
- A spanning tree connects all n nodes with n − 1 links and no loop; a minimum spanning tree has the least total weight.
- The cut property: the cheapest link across any split of the nodes is safe to take.
- Kruskal's algorithm sorts the links and takes each one that union-find says won't close a loop: O(m log m).
- Prim's algorithm grows one tree with the cheapest link leaving it: O(m log m) with a heap, O(n²) with an array on dense graphs.
Now solve some yourself
Mixed with topics you have practiced 0 unlocked
9 more once you have practiced Union-find, Binary search on the answer. Play one of its examples to the end and solve one of its problems to unlock them.
Problems open on their own sites (LeetCode, Codeforces, CodeChef, AtCoder, CSES) in a new tab. Tick Solved when you get it accepted there; your ticks decide which mixed problems open next.
Next