Minimum spanning trees
Studying this course? Keep your progress in one place.
Key facts
- A minimum spanning tree (MST) connects every vertex with the least total weight; it has arcs and no cycle.
- Kruskal's algorithm: sort the arcs, take the smallest, and reject any arc that makes a cycle.
- Prim's algorithm: grow one tree from any vertex by adding the smallest arc joining the tree to a new vertex.
- On a distance matrix, label the start column 1 and delete its row, then circle the smallest entry in the labelled columns among undeleted rows.
- Equal weights can give different MSTs, but the total weight is always the same.
The minimum connector problem
A minimum spanning tree is the spanning tree of least total weight. A network with vertices needs exactly arcs and no cycle.
A tree is a connected network with no cycles. A spanning tree includes every vertex, using some of the original arcs.
If you add one more arc you create a cycle, and if you take one away a vertex is cut off.
The minimum spanning tree (MST), or minimum connector, has the smallest total weight. It solves problems such as joining every site to a water or cable network at least cost.
How many arcs does an MST of a network with 9 vertices have?
Kruskal's algorithm
Kruskal's algorithm sorts the arcs by weight and takes them in turn, rejecting any arc that would make a cycle, until arcs are chosen.
Kruskal's algorithm builds the MST by choosing arcs.
- Sort the arcs into increasing order of weight.
- Select the smallest arc.
- Select the next smallest arc, rejecting it if it would form a cycle with arcs already chosen.
- Repeat step 3 until arcs are selected.
No starting vertex is needed. Show the order in which arcs are considered and which are rejected.
Worked example
Arcs of the network in increasing order: , , , , , . Find the MST.
- 1
Accept (3).
- 2
Accept (4).
- 3
Accept (5).
- 4
Accept (6). This joins to .
- 5
Reject (7): and are already joined through . That is 4 arcs, so stop.
When must Kruskal's algorithm reject an arc?
Prim's algorithm on a network
Prim's algorithm grows one tree from any starting vertex, repeatedly adding the smallest arc that joins the tree to a vertex not yet in it.
Prim's algorithm grows a single tree from a starting vertex.
- Choose any vertex to start.
- Select the smallest arc joining a vertex in the tree to a vertex not yet in the tree.
- Repeat until every vertex is in the tree.
The arcs may be chosen in a different order from Kruskal's, but the MST has the same total weight. You never need to check for cycles, because each arc adds a new vertex.
- 1
Start
choose any vertex
- 2
Select
the smallest arc from the tree to a new vertex
- 3
Repeat
until every vertex is in the tree
Worked example
Apply Prim's algorithm to the network above, starting at .
- 1
From : arcs and . Choose .
- 2
From , arcs to new vertices are , , , . Choose .
- 3
From : , , . Choose .
- 4
From the arcs to are and . Choose .
What must each arc added by Prim's algorithm do?
Prim's algorithm on a matrix
On a matrix, label the start column 1 and delete its row, then circle the smallest entry in the labelled columns among undeleted rows, and repeat.
A distance matrix has rows and columns labelled with the vertices; the entry in row and column is the weight of arc . A dash means no arc. It is symmetrical about the leading diagonal.
- Choose a start vertex. Label its column 1 and delete its row.
- In the labelled columns, circle the smallest entry in a row not yet deleted.
- Label the new vertex's column with the next number and delete its row.
- Repeat until all rows are deleted.
- 1
Label
start column 1, delete its row
- 2
Circle
smallest entry in labelled columns, undeleted rows
- 3
Label and delete
the new vertex: next number, delete its row
- 4
Repeat
until all rows are deleted
The network above as a matrix, with a dash where there is no arc:
Worked example
Apply Prim's algorithm to the matrix, starting at A.
- 1
Label column 1 and delete row . The smallest entry in column is 4 (row ): arc .
- 2
Label column 2 and delete row . Columns and now give 7 and 6 (row ) and 8 (row ) and 5 (row ). Smallest is 5: arc .
- 3
Label column 3 and delete row . The smallest available entry is 6 (row , column ): arc .
- 4
Label column 4 and delete row . The smallest entry for row is 3 (column ): arc .
What does the number written above a column show?
Matrix to network and back
To draw a network from a matrix, draw one arc for each non-blank entry in the upper triangle, so that no arc is drawn twice.
To draw a network, mark each vertex, then for each non-blank entry in the upper triangle draw one arc and write its weight on it.
To write the matrix, make a square table and put each weight in the cell for each end, once in each triangle. Put a dash for any pair with no arc.
Row is , 12, 9, 15, for columns , , , , . It gives arcs , and , with no arc .
Matrix manipulation is not needed.
- Arcs in the networkhalf the non-blank entries
A symmetrical matrix has 14 non-blank entries. How many arcs does the network have?
Exam variations
Equal weights, a forced arc or a new vertex change how you apply the algorithm, but never the checks: arcs and no cycle.
Always show the order in which arcs are considered or added. Marks are given for the method as well as the final weight.
If an arc is forced into the tree, include it first and then continue the algorithm.
When a new vertex is added, repeat the algorithm: some old arcs may drop out when the new arcs offer cheaper connections.
- 1
Equal weights
either arc may be chosen; the weight is the same
- 2
Arc forced in
include it first, then continue the algorithm
- 3
New vertex added
repeat the algorithm; some old arcs may drop out
- 4
Check
n − 1 arcs for n vertices and no cycle
Equal weights
- Either arc may be chosen
- MST may differ, weight does not
Arc forced in
- Include it first
- Cost is at least the MST weight
New vertex added
- Repeat the algorithm
- Some old arcs may drop out
Two arcs have the same weight. What can happen?
Try an exam question
A network has vertices A, B, C, D and E and arcs AB = 9, AC = 7, BC = 4, BD = 6, CD = 5, CE = 3, DE = 8. Use Kruskal's algorithm to find the minimum spanning tree. State the order in which you consider the arcs, which you reject, and the weight of the tree.
[4 marks]
- [1]Arcs considered in order of weight: CE 3, BC 4, CD 5, BD 6, AC 7, DE 8.
- [1]BD is rejected because it forms the cycle B, C, D.
- [1]AC is accepted and DE is rejected because it forms a cycle.
- [1]The MST is CE, BC, CD and AC with weight 3 + 4 + 5 + 7 = 19.
That's the notes covered.
Carry on to the next subtopic.
Try a question
How many arcs does a minimum spanning tree of this network contain?
1 mark, marked against the mark scheme
How many arcs does a minimum spanning tree of this network contain?
1 mark, marked against the mark scheme