Spanning trees and network optimisation
Studying this course? Keep your progress in one place.
Key facts
- A network is a graph whose arcs have weights such as distance, cost or time.
- A spanning tree contains every node and has exactly arcs; the minimum spanning tree has least total weight.
- Kruskal's algorithm adds the lightest arcs in order, rejecting any that form a cycle.
- Prim's algorithm grows one tree by adding the lightest arc from the tree to a node outside it.
- An MST connects every node cheaply; it does not give the shortest route between two nodes.
The language of networks
A network is a graph with weighted arcs, and a minimum spanning tree connects every node with the least total weight.
The points are nodes (vertices) and the lines joining them are arcs (edges), each with a weight.
A tree is a connected network with no cycles. A spanning tree contains every node, and a minimum spanning tree (MST) is a spanning tree of least total weight.
Typical uses are laying cable, pipes or roads so that every site is connected using the least total length or cost.
- Arcs in a spanning tree for nodes
A network has 9 nodes. How many arcs does a spanning tree of it have?
Kruskal's algorithm
Add the lightest arcs in order, skipping any arc that would form a cycle, until arcs are chosen.
Kruskal's algorithm works across the whole network:
- List the arcs in ascending order of weight.
- Add the next arc unless it would form a cycle with arcs already chosen.
- Stop when arcs have been chosen.
An arc is rejected only if its two nodes are already connected. Two separate pieces of tree may still be joined.
Worked example
Use Kruskal's algorithm on the network above (6 nodes, so 5 arcs are needed).
- 1
Order the arcs: 2, 3, 4, 5, 6, 7.
- 2
Add (2), (3), (4): no cycles.
- 3
Add (5): this joins the piece – to the piece ––.
- 4
Add (6): now 5 arcs are chosen, so stop.
- 5
(7) would be rejected anyway: –– already connects and .
Two arcs in a partly built tree join nodes that are in the same piece. Should Kruskal's algorithm accept the arc?
Prim's algorithm on a network
Start from any node and repeatedly add the lightest arc that joins the tree to a node outside it.
Prim's algorithm grows a single tree:
- Choose any starting node.
- Add the lightest arc that joins a node in the tree to a node not yet in it.
- Repeat until every node is in the tree.
Prim's tree is always connected as it grows, whereas Kruskal's may have separate pieces until the end.
Worked example
Start at . Use Prim's algorithm on the network above.
- 1
From : the lightest arc leaving the tree is (8). Add it.
- 2
Tree : choose (6).
- 3
Tree : choose (10).
- 4
Tree : choose (7). All 5 nodes are in the tree.
In Prim's algorithm, the tree so far contains and . Which arcs may be chosen next?
Prim's algorithm on a matrix
Look only at the columns of tree nodes, in rows of nodes not yet in the tree, and choose the smallest entry each time.
A distance matrix has a row and column for each node, the entry being the arc weight.
Keep a list of nodes in the tree. At each step choose the smallest entry in the columns of tree nodes, restricted to rows of nodes not yet in the tree. That entry is the next arc. Add its node and repeat.
- 1
Start at
cross out its row
- 2
Look at tree columns
only rows not crossed out
- 3
Circle the smallest entry
this is the next arc
- 4
Cross out the new row
repeat until all rows are crossed out
Worked example
A distance matrix has rows , , , . Start at and find the MST.
- 1
Tree : column gives 5, 9, 7. Smallest is (5).
- 2
Tree : for the best is 4 (from ); for the best is 7 (from ). Choose (4).
- 3
Tree : for : 7 (from ), 8 (from ), 6 (from ). Choose (6).
At each step of Prim's on a matrix, where do you look for the smallest entry?
Choosing and applying the methods
Both algorithms give an MST of the same total weight, but an MST is not a shortest route between two nodes.
If arcs have equal weights the MST may not be unique, but its weight is.
If an arc becomes unavailable (a road closed), delete it and apply the algorithm again: the new MST is never lighter than the old.
An MST (a minimum connector) connects all nodes using the least total weight. It does not give the shortest route between two particular nodes: the direct arc between two nodes may be far shorter than the path through the tree.
| Kruskal's | Prim's | |
|---|---|---|
| Builds | Pieces that join up | One growing tree |
| Cycle check | Needed | Not needed |
| Suits | Sorted lists of arcs | Matrices |
Kruskal's
- Builds:
- Pieces that join up
- Cycle check:
- Needed
- Suits:
- Sorted lists of arcs
Prim's
- Builds:
- One growing tree
- Cycle check:
- Not needed
- Suits:
- Matrices
Does the minimum spanning tree give the shortest route between two particular nodes?
Try an exam question
A network has five nodes to and arcs 4, 7, 5, 9, 6, 8, 3. Use Kruskal's algorithm to find a minimum spanning tree, giving the arcs in the order chosen and the total weight.
[4 marks]
- [1]Arcs in order of weight: 3, 4, 5, 6, 7, 8, 9.
- [1]Accept , and (no cycles).
- [1]Accept (joins the two pieces). Four arcs for five nodes, so stop; would form a cycle.
- [1]Total weight .
That's the notes covered.
Carry on to the next subtopic.
Try a question
How many arcs does a spanning tree of this network contain?
1 mark, marked against the mark scheme
How many arcs does a spanning tree of this network contain?
1 mark, marked against the mark scheme