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.
- Apply Kruskal's algorithm, rejecting edges that would form a cycle.
- State the number of edges in a spanning tree and check an answer against it.
WHAT YOU PROBABLY THINK
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, and repeatedly add the cheapest edge joining the tree to a node not yet in it. Kruskal instead sorts all the edges by weight and takes them in order, rejecting any that would close a cycle, until n − 1 have been taken.
Both always produce a minimum spanning tree, so the totals always agree and the opening claim is false. The trees themselves can differ only when there are ties in the weights.
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 beats BE 9, so take CE (6).
Finally EF 2 beats 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 from the other end. 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 rather than a drawing, Prim is the natural choice, because it only ever needs the columns of the nodes already in the tree. 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.
YOUR TURN
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.
THE EXAM BIT
- 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
S
e
v
e
n
e
d
g
e
s
,
o
n
e
f
e
w
e
r
t
h
a
n
t
h
e
n
u
m
b
e
r
o
f
n
o
d
e
s
.
A
n
e
i
g
h
t
h
e
d
g
e
w
o
u
l
d
j
o
i
n
t
w
o
n
o
d
e
s
a
l
r
e
a
d
y
c
o
n
n
e
c
t
e
d
a
n
d
s
o
c
r
e
a
t
e
a
c
y
c
l
e
.
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.
CHECK YOUR PROGRESS
Rate how confident you feel with each objective for this lesson. Ratings are saved in this browser, on this device only.
- Apply Prim's algorithm from a network and from a distance matrix.
- Apply Kruskal's algorithm, rejecting edges that would form a cycle.
- 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.
No animated video for this topic yet; these notes stand alone.