Lesson 2 of 8 · 18 min
Finding minimum spanning trees
Find a minimum spanning tree and its weight by inspection, with Kruskal's method and with Prim's method, and recognise when there is more than one.
What you will be able to do
- Find a minimum spanning tree with Kruskal's method, skipping edges that would form a cycle.
- Find a minimum spanning tree with Prim's method from any starting vertex.
- Find the weight of a minimum spanning tree.
- Decide whether a minimum spanning tree is unique when some edges have equal weights.
A ranger wants to upgrade some walking tracks between seven camp sites, to , to an all-weather surface. Every camp site must be reachable on upgraded track, and the upgrade costs the same per kilometre everywhere, so the ranger wants the least total length.
That is a minimum spanning tree. You could try spanning trees at random, but this graph has 320 of them. Instead, use a method that builds the best tree one edge at a time.
Tracks between camp sites, with lengths in kilometres.
Kruskal's method
List the edges from lightest to heaviest
Write them in order of weight. Where weights are equal, the order between them does not matter.
Choose the lightest edge
It cannot make a cycle on its own.
Choose the next lightest edge that does not make a cycle
If an edge joins two vertices that are already connected by the edges you have chosen, it would close a cycle. Skip it.
Stop at v − 1 edges
Once you have edges, every vertex is joined. Add their weights to get the weight of the minimum spanning tree.
Step through Kruskal's method on the camp-site tracks. Watch the separate pieces join up, and notice which edge is skipped and why.
Worked example
Kruskal's method on the camp-site tracks
Use Kruskal's method to find a minimum spanning tree for the camp-site tracks (lengths in km), and state its weight.
Edges: 6, 4, 7, 5, 9, 3, 10, 6, 8, 4, 5, 9.
Step 1: Order the edges by weight
3, 4, 4, 5, 5, 6, 6, 7, 8, 9, 9, 10.
Step 2: Choose the first five
(3), (4), (4), (5) and (5) form no cycle. The pieces so far are and .
Step 3: Skip AB
and are already joined by –––, so (6) would make a cycle. Skip it.
A tree has no cycles, and the cheaper edges already connect to , so would be wasted.
Step 4: Choose DE
(6) joins the two pieces. That is 6 edges for 7 vertices, so stop.
A spanning tree on vertices has edges.
Step 5: Add the weights
Try it yourself first, then check the working one step at a time.
Answer
The minimum spanning tree has edges , , , , and , with weight 27 km.
Method
List the edges from lightest to heaviest.
Choose each edge in turn unless it makes a cycle.
Stop at edges and add the weights.
Watch out for
Choosing as well: a seventh edge always creates a cycle.
Stopping at : is not yet joined to the rest.
Kruskal's method on the camp-site tracks considers (6 km) but does not choose it. Which vertices were already connected, making form a cycle?
Prim's method
Start at any vertex
This vertex is the tree so far.
Look at every edge leaving the tree
These are the edges joining a vertex in the tree to a vertex not yet in it.
Add the lightest of them
Its far vertex joins the tree. Because the new vertex was not in the tree, no cycle can form.
Repeat until every vertex is in the tree
That takes edges. Add their weights.
Step through Prim's method on the same tracks, starting at . The tree grows from one vertex; at each step the highlighted edges are the candidates.
Worked example
Prim's method from A on the camp-site tracks
Use Prim's method, starting at , to find a minimum spanning tree for the camp-site tracks. List the edges in the order they are added.
Step 1: Start at A
Edges leaving : 6, 4, 7. Add the lightest, (4).
Step 2: Tree {A, C}
Edges to new vertices: 6, 7, 3, 10. Add (3).
Step 3: Tree {A, C, D}
Candidates: 6, 5, 6, 8, 9, 10. Add (5).
is no longer a candidate: both its ends are in the tree, so it would make a cycle.
Step 4: Tree {A, B, C, D}
Candidates: 9, 6, 8, 9, 10. Add (6).
Step 5: Tree {A, B, C, D, E}
Candidates: 4, 8, 9, 10. Add (4).
Step 6: Tree {A, B, C, D, E, G}
Candidates: 5, 8, 10. Add (5). Every vertex is now in the tree.
Step 7: Add the weights
Try it yourself first, then check the working one step at a time.
Answer
Edges in order: , , , , , . The minimum spanning tree has weight 27 km — the same tree Kruskal's method found.
Method
Start with one vertex as the tree.
List the edges joining the tree to a vertex not in it; add the lightest.
Repeat until every vertex is in the tree.
Watch out for
Only looking at edges from the newest vertex. After joins, the next edge () comes from .
Common mistake
Prim's method is not "nearest neighbour"
At each step, look at the edges from every vertex already in the tree, not just the one you added last. From , joins first (), then (), then (). The next edge is (6), from , even though was the latest vertex added.
Kruskal's method
- Works on the whole graph at once: sort every edge by weight.
- The chosen edges can sit in separate pieces until the end.
- You must check each edge for a cycle.
- Easiest when the network is drawn.
Prim's method
- Grows one tree from a starting vertex.
- The chosen edges are always connected.
- Cycles cannot form, so there is nothing to check.
- Works well from a table of distances.
Tip
Inspection for small graphs
For a graph with only a few vertices you can find a minimum spanning tree by inspection: pick out the light edges, avoid cycles, and make sure every vertex is reached. That is Kruskal's method done in your head. For anything larger, name a method and show its steps.
Both methods gave the same tree of 27 km for the camp sites. But when some edges have equal weights, there can be a genuine choice. Look at the graph below: and are both 4.
A graph with two edges of weight 4.
Worked example
A graph with two minimum spanning trees
A graph has edges 4, 3, 4, 5, 6 and 2. Find the weight of a minimum spanning tree, and decide whether the minimum spanning tree is unique.
Step 1: Order the edges
2, 3, 4, 4, 5, 6.
Step 2: Choose ST and PR
Neither makes a cycle.
Step 3: Meet the tie
and both weigh 4. Either joins to . Once one is chosen, the other would close the cycle –––.
When equal edges are interchangeable like this, each choice gives a different minimum spanning tree with the same weight.
Step 4: Finish with QS
(5) joins to . That is 4 edges for 5 vertices. (6) is not needed.
Step 5: Add the weights
Try it yourself first, then check the working one step at a time.
Answer
The minimum weight is 14. There are two minimum spanning trees, and , so it is not unique.
Method
Run Kruskal's method as usual.
At a tie, check whether choosing one of the equal edges rules out the other. If so, each choice gives a minimum spanning tree.
Watch out for
Choosing both and , which forms a cycle.
Thinking that two different trees must have different weights.
For the graph with vertices to above, how many different minimum spanning trees are there?
Key idea
When is a minimum spanning tree unique?
If every edge weight is different, the minimum spanning tree is unique. With equal weights there may be more than one — but the minimum weight is always the same. Equal weights do not always cause a choice: on the camp-site tracks, and are both 4 and both are needed, so that tree is unique.
Exam tip
Show the order you chose the edges, name any edge you skipped and why (" would form a cycle"), list the final edges, count them (), and give the total weight with units.
Summary
Kruskal's method: take edges from lightest to heaviest, skipping any edge that would form a cycle, until there are edges.
Prim's method: grow one tree from any vertex, each time adding the lightest edge from the tree to a new vertex.
Both methods give a minimum spanning tree; for small graphs, inspection is the same idea done mentally.
The weight of a minimum spanning tree is the sum of its edge weights.
Equal edge weights can give more than one minimum spanning tree, all with the same weight.
Finished the lesson?
Try the 2 quick checks above and the lesson completes itself, or mark it complete now.