Minimum spanning trees: Kruskal's and Prim's algorithms

Lesson · 10 min read · Graphs · Union-find and spanning trees

Connect every node at the least total cost. Take the cheapest edge that does not close a cycle, and repeat.

The problem

Given a connected, weighted, undirected graph, a spanning tree is a set of n − 1 edges that connects every node with no cycle. A minimum spanning tree (MST) is one with the smallest total weight: the cheapest way to lay cable between offices, to connect points on a circuit board, or to link data centres.

Six sites and the cost of linking each pair that can be linked.

Why greedy works: the cut property

Split the nodes into any two groups. Among the edges that cross between them, the cheapest one belongs to some minimum spanning tree. (If a tree avoided it, adding it would create a cycle crossing the split twice; removing the other crossing edge on that cycle gives a tree that is no more expensive.) Both standard algorithms are this property applied repeatedly.

Kruskal's algorithm

kruskal(n, edges)

Sort the edges by weight.
For each edge (u, v, w) in that order: if union(u, v) succeeds (they were in different groups), keep the edge and add w.
Stop after n − 1 edges. If fewer were kept, the graph is not connected.

Prim's algorithm

prim(graph, s)

Start the tree at s. Push every edge from s into a min-heap.
Pop the cheapest edge; if it leads to a node already in the tree, skip it.
Otherwise add that node and its edge to the tree, and push its edges. Repeat until all n nodes are in.

Kruskal, step by step

Edges are taken from cheapest to most expensive; union-find rejects any edge whose ends are already joined.

Kruskal's algorithm on the six sites.

Step 1 / 6

Sort the edges by weight: 1, 2, 2, 3, 4, 5, 6, 7, 8. Every node is its own group.
Step 2 / 6

total1edges1
E–F (1): it joins two different groups, so take it. Total 1.
Step 3 / 6

total3edges2
A–C (2): it joins two different groups, so take it. Total 3.
Step 4 / 6

total5edges3
D–E (2): it joins two different groups, so take it. Total 5.
Step 5 / 6

total8edges4
B–D (3): it joins two different groups, so take it. Total 8.
Step 6 / 6

total12edges5
A–B (4): it joins two different groups, so take it. Total 12. 5 edges join all 6 nodes: that is a minimum spanning tree, weight 12.

in the treerejected: would close a cycle

Which one to use

TimeKruskal O(m log m); Prim O(m log n)

SpaceO(n + m)

Kruskal is the natural choice when you are given a list of edges, and its union-find makes it easy to stop early or to work with groups. Prim suits an adjacency list, and on a complete graph with n points it can be written in O(n²) with no heap at all, which beats sorting all n²/2 edges.

The problem at the end of this module, connecting points on a plane, is that dense case: every pair of points is an edge.

Minimum spanning forest: when the graph is not connected

If your graph falls into several pieces, it has no spanning tree at all, because no set of edges can join two pieces that have nothing between them. What you can still ask for is a minimum spanning forest, which is a minimum spanning tree inside each connected piece. With n nodes in c pieces it has n − c edges, and its weight is the sum of the weights of those trees.

I like Kruskal's algorithm here because it gives you the forest without any change. Don't stop at n − 1 edges. Run through every edge, and union-find will keep the cheapest edges that join two groups, piece by piece, with c groups left over at the end. Prim's algorithm only grows one tree from its start node, so for a forest you'd restart it from a node it hasn't reached yet, once for each piece. If an interviewer tells you the graph may be disconnected, I'd say up front which of these you'll return and what you'll report, either the forest's weight or the fact that no tree exists.