Maths › Decision Mathematics 1 › Minimum spanning trees: Prim and Kruskal
Minimum spanning trees: Prim and Kruskal
A minimum spanning tree connects every node of a network at the least possible total cost. Prim's algorithm grows the tree outwards from a starting node and Kruskal's works down a sorted list of edges. Both return a minimum spanning tree, so both give the same minimum total weight, though they need not select the same edges when the minimum spanning tree is not unique.
Builds on Graphs: order, Eulerian paths and planarity and Algorithms, sorting and bin packing.
IN THIS TOPIC
- Apply Prim's algorithm from a network and from a distance matrix, and Kruskal's from a sorted edge list.
- State the number of edges in a spanning tree and check an answer against it.
- Quote the cubic order of both algorithms and use it to scale a running time.
- Read a graph from its adjacency matrix, and check the row sums against the orders.
- Update a minimum spanning tree when one arc is cheapened or removed, by the cycle it closes or the split it leaves, without rerunning the algorithm.
COMMON MISCONCEPTION
Prim's and Kruskal's algorithms can give trees of different total weight, so it is worth trying both.
Both algorithms produce a minimum spanning tree, so the total weight is the same either way. They can select different edges only where weights are tied and more than one minimum spanning tree exists; with all the weights distinct the tree is unique and the two return the same edges. Running both is a check on the arithmetic, not a search for a lighter tree.
Prim's and Kruskal's algorithms
A spanning tree connects all n nodes using n − 1 edges and no cycle. The minimum spanning tree is the one of least total weight, and two algorithms find it.
Prim grows a single tree. Start at any node, then repeatedly add the cheapest edge joining the tree to a node not yet in it. Kruskal works from the other end. Sort all the edges by weight, take them in order, reject any that would close a cycle, and stop when n − 1 have been taken.
Prim's and Kruskal's algorithms both produce a minimum spanning tree. Their trees have the same total weight, but may contain different edges when more than one minimum spanning tree exists. That can happen only where edge weights are tied: if all the weights are distinct, the minimum spanning tree is unique and the two algorithms return the same edges.
Under the Pearson Edexcel Decision Mathematics implementations both are cubic in the number of nodes, O(n3), which is the order to quote for either; in computer-science contexts the complexity also depends on the data structure and the graph representation. Prim reaches that order by doing n − 1 rounds and scanning a table of about n2 entries in each; Kruskal by sorting the edges, of which a network on n nodes may hold up to n(n − 1)/2, and then testing each accepted edge against the part of the tree built so far. Cubic is a heavy order: quadrupling the number of nodes multiplies the work by 64.
WORKED EXAMPLE
Prim from A
Apply Prim's algorithm to the network, starting at A.
From A the cheapest edge is AB (5). From {A, B} the choices are AC 7, BC 4, AD 9, BE 9, so take BC (4).
From {A, B, C}: CD 3 is cheapest, so take CD (3). Then CE 6 is shorter than BE 9, so take CE (6).
Finally EF 2 is shorter than DF 10, giving EF (2).
Five edges for six nodes, total 5 + 4 + 3 + 6 + 2 = 20.
Kruskal, and matrices
Kruskal reaches the same total on this network. Sorting the nine edges gives EF 2, CD 3, BC 4, AB 5, CE 6, AC 7, BE 9, AD 9, DF 10. The first five are taken; each of the remaining four would close a cycle among nodes already connected, so all four are rejected. The total is 20 again.
When a question supplies a distance matrix instead of a drawing, use Prim. It needs only the columns of the nodes already in the tree, so it works straight off the table. Cross out the row of each node as it joins, scan the columns of the joined nodes for the smallest uncrossed entry, and record the order in which the nodes are added. Kruskal on a matrix would mean sorting every entry first, which is much slower by hand.
The plainer relative of that table is the adjacency matrix, which records the structure and not the weights. Label the rows and the columns with the nodes and put in each cell the number of edges joining that pair, which for a simple graph is 1 when the two are joined and 0 when they are not. Below is the four-node graph used earlier, the one with two edges between A and B and a loop at C.
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 2 | 0 | 0 |
| B | 2 | 0 | 1 | 1 |
| C | 0 | 1 | 2 | 1 |
| D | 0 | 1 | 1 | 0 |
Three things can be read straight off it. The matrix of an undirected graph is symmetric, since an edge is entered on both sides of the diagonal. Each row sums to the order of its node, so the four rows give 2, 4, 4 and 2, and a loop is entered as 2 to keep that true. And an entry above 1 off the diagonal is a multiple edge, so a simple graph shows zeros down the diagonal and nothing but 0 and 1 elsewhere, with its complement obtained by swapping those two off the diagonal.
A digraph loses the symmetry: an arc is entered once, in the row of the node it leaves, so the row sums are the outdegrees and the column sums the indegrees. A distance matrix is the same table again with a weight in place of a count, which is what Prim's algorithm reads.
GUIDED PRACTICE
Kruskal on the same network
Apply Kruskal's algorithm to the same network and confirm the total.
Show the working
Sorted: EF 2, CD 3, BC 4, AB 5, CE 6, AC 7, BE 9, AD 9, DF 10.
Take EF, CD, BC, AB, CE. That is five edges for six nodes, so the tree is complete.
AC would close ABC, BE would close BCE, AD would close ABCD and DF would close a longer cycle, so all four are rejected.
Total 20. Every weight used here is distinct, so this network's minimum spanning tree is unique and Kruskal selects the same five edges Prim did.
When the network changes
A question that alters one weight after the tree is found does not want the whole algorithm again. A spanning tree has exactly one path between any two nodes, so adding an edge to it closes exactly one cycle, and removing an edge from it splits it into exactly two pieces. Those two facts are all the updating needs.
An arc is cheapened. If the arc is already in the tree, the tree stands and only its total falls. If it is not, put it in, find the cycle it closes, and drop the heaviest edge on that cycle; the new arc stays unless it is itself the heaviest. On the network above, cut AD from 9 to 1. It closes the cycle A B C D, whose tree edges are AB 5, BC 4 and CD 3, so AB goes: the tree is now AD, BC, CD, CE, EF, of weight 1 + 4 + 3 + 6 + 2 = 16. Kruskal agrees: AD 1, EF 2, CD 3, BC 4, then AB 5 is rejected because A and B are already joined through D and C, and CE 6 completes the five.
An arc is removed. If it was not in the tree, nothing changes. If it was, the tree falls into two pieces, and the cheapest surviving arc with one end in each piece rejoins them. Remove BC from the network above and the tree splits into {A, B} and {C, D, E, F}. The arcs crossing that split are AC 7, AD 9 and BE 9, so AC comes in and the new total is 20 − 4 + 7 = 23.
Either way the answer is the old tree with one edge swapped, and the working to show is the cycle or the split, the candidates on it with their weights, and the one chosen. An arc made dearer is the same two cases the other way round: if it was not in the tree nothing changes, and if it was, treat it as removed and then see whether it is still the cheapest way across the split it leaves.
GUIDED PRACTICE
One arc cheapened
Working from the original tree of weight 20, the arc BE is reduced from 9 to 3. Find the new minimum spanning tree and its weight, and confirm the answer by Kruskal's algorithm.
Show the working
BE is not in the tree. Adding it closes the cycle B C E, whose tree edges are BC 4 and CE 6.
CE is the heaviest edge on that cycle, so CE leaves and BE enters: the tree is AB, BC, CD, BE, EF, of weight 5 + 4 + 3 + 3 + 2 = 17.
Kruskal on the altered list, EF 2, CD 3, BE 3, BC 4, AB 5, CE 6, AC 7, AD 9, DF 10: take EF, CD, BE, BC, AB, which is five edges, and CE would now close the cycle B C E. Total 17.
ASSESSMENT FOCUS
- State the order in which edges are added as well as the finished tree.
- Check you have exactly n − 1 edges before totalling.
- For Kruskal, write 'reject: forms a cycle' against every edge you skip.
- From a matrix, use Prim and record the order the nodes join in.
- Given an adjacency matrix, sum the rows and compare the totals with the orders before working with it.
- Asked for the order of either algorithm, answer cubic in the number of nodes, and scale a run-time by the cube of the size ratio.
CHECK YOURSELF
A network has 8 nodes. How many edges does its minimum spanning tree have, and what happens if you take one more?
Show a hint
A tree has no cycles.
Show the answer
Seven edges, one fewer than the number of nodes. An eighth edge would join two nodes already connected and so create a cycle.
A spanning tree of n nodes has exactly n − 1 edges and no cycle; the minimum one has least total weight.
Prim grows outwards from a node and Kruskal works down the sorted edges rejecting cycles; both give the same minimum total, though the edges chosen can differ when the minimum spanning tree is not unique.
An adjacency matrix counts the edges joining each pair, so it is symmetric for an undirected graph and its row sums are the orders.
WORKBOOK
Printable practice for this topic: original exam-style questions with room to work, and a fully worked answer book. Free to use; please do not redistribute or sell.
Or read them with their worked answers on the minimum spanning trees: Prim and Kruskal questions page.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device, unless you sign in.
- Apply Prim's algorithm from a network and from a distance matrix, and Kruskal's from a sorted edge list.
- State the number of edges in a spanning tree and check an answer against it.
- Quote the cubic order of both algorithms and use it to scale a running time.
- Read a graph from its adjacency matrix, and check the row sums against the orders.
- Update a minimum spanning tree when one arc is cheapened or removed, by the cycle it closes or the split it leaves, without rerunning the algorithm.
Open the full revision checklist to see every objective in the course in one place.