Minimum spanning trees
Studying this course? Keep your progress in one place.
Key facts
- A spanning tree joins every vertex with no cycles, so a network with vertices has a spanning tree of exactly edges.
- A minimum spanning tree is the spanning tree with the least total weight.
- Kruskal's algorithm sorts the edges and accepts each one unless it forms a cycle.
- Prim's algorithm grows one tree from a start vertex, always adding the shortest edge to a new vertex.
- On a matrix, Prim's algorithm numbers columns and deletes rows as vertices join the tree.
The minimum spanning tree
A minimum spanning tree connects every vertex using the least total weight, with no cycles.
A spanning tree connects all the vertices of a network with no cycles. The minimum spanning tree is the one with the smallest total weight, such as the cheapest cables joining all the sites.
If all the weights are different it is unique. If some weights are equal there may be more than one.
Two algorithms find it: Kruskal's and Prim's.
- Vertices
- Edges in a spanning tree
A network has 9 vertices. How many edges does a spanning tree of it have?
Kruskal's algorithm
Sort the edges by weight, then accept each in turn unless it forms a cycle. Stop when edges are accepted.
Kruskal's algorithm works on the sorted list of edges.
- Sort the edges in increasing order of weight.
- Take the next edge. Accept it unless it forms a cycle with the edges already accepted.
- Stop when edges are accepted.
Test whether the two ends are already connected, not whether the vertices are already in the tree.
Worked example
Six vertices, edges , , , , , , , , . Find the minimum spanning tree.
- 1
The edges are already sorted by weight.
- 2
Accept (3), (4), (5) and (6).
- 3
Reject (7): it forms the cycle .
- 4
Reject (8): it forms the cycle .
- 5
Reject (9): it forms the cycle .
- 6
Accept (10). That is 5 edges for 6 vertices, so stop.
Edges , , are considered in order. Which is rejected?
Prim's algorithm
Start at any vertex and keep adding the shortest edge that joins the tree to a vertex outside it. Cycles cannot form.
Prim's algorithm grows a single tree from any starting vertex.
- Choose any vertex to start.
- Look at all edges from a vertex in the tree to a vertex not in it. Add the shortest.
- Repeat until every vertex is in the tree.
Because the tree stays connected as it grows, cycles can never form.
- 1
Start
choose any vertex
- 2
Look
edges from the tree to new vertices
- 3
Add
the shortest of these
- 4
Repeat
until all vertices are in the tree
Worked example
Edges , , , , , , . Use Prim's algorithm from .
- 1
Tree : edges out , . Add (6).
- 2
Tree : edges out , , . Add (4).
- 3
Tree : edges out , , . Add (5).
- 4
Tree : only is left and is the smallest. Add (3).
After adding in the example, which edge does Prim's algorithm add next?
Prim's on a matrix
Number the start column, delete its row, then repeatedly circle the smallest entry in the numbered columns among undeleted rows.
A distance matrix lists the weight between every pair of vertices, with a dash where there is no edge.
- Choose a start vertex. Number its column 1 and delete its row.
- In the numbered columns, circle the smallest entry in a row not yet deleted.
- That row is the new vertex. Number its column next and delete the row.
- Repeat until all rows are deleted.
The matrix of an undirected network is symmetric, so each edge appears twice.
- 1
Start
number the start column 1 and delete its row
- 2
Circle
the smallest entry in numbered columns, in rows not deleted
- 3
Number
the circled row's column next, then delete the row
- 4
Repeat
until every row is deleted
The matrix of an undirected network has 14 numerical entries in total. How many edges does the network have?
Try an exam question
A network has edges , , , , , , . Use Kruskal's algorithm to find a minimum spanning tree. State the edges in the order considered and the total weight.
[4 marks]
- [1]Edges considered in increasing order: , , , , , .
- [1]Accepts , and .
- [1]Rejects and because each forms a cycle; accepts .
- [1]Total weight .
That's the notes covered.
Carry on to the next subtopic.
Try a question
How many edges does a minimum spanning tree of this network contain?
1 mark, marked against the mark scheme
How many edges does a minimum spanning tree of this network contain?
1 mark, marked against the mark scheme