Maths › Decision Mathematics 1 › Minimum spanning trees: Prim and Kruskal
Minimum spanning trees: Prim and Kruskal
Connect every node as cheaply as possible. Two algorithms, one growing outwards from a starting node and one working down a sorted list of edges, and they always agree on the total.
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.
COMMON MISCONCEPTION
Prim's and Kruskal's algorithms can give trees of different total weight, so it is worth trying both.
Two ways to the same tree
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.
Both always produce a minimum spanning tree, so the totals always agree. Only ties in the weights can make the trees themselves differ.
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 answer. 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.
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, the same tree Prim found.
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.
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, and both always give the same total.
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.
Open the full revision checklist to see every objective in the course in one place.