Cheapest cables that still reach every house: A minimum spanning tree (MST) connects every vertex using the least total length, with no cycle.
The cable problem: Picture a town wanting to lay fibre cable so every building is connected, using the least total length of cable. You never need a loop (a cycle) — that would be wasted cable.
Edge count: For a graph with n vertices, the MST always has exactly n − 1 edges.
Kruskal's algorithm
Sort
Sort all edges from cheapest to dearest.
Add
Add them one at a time.
Skip cycles
Skip any edge that would create a cycle.
Stop
Stop when every vertex is joined.
Sort → add → skip cycles
IB-style question — Kruskal's algorithm
A town wants to connect 5 buildings A, B, C, D, E with fibre cable. The possible links and their lengths (in hundreds of metres) are:
AB = 6, AC = 9, BC = 4, BD = 8, CD = 5, CE = 11, DE = 7.
Use Kruskal's algorithm to find the minimum spanning tree and its total length.
Step by step
- Sort the edges from cheapest to dearest.
- Add BC (4): joins B–C. No cycle.
- Add CD (5): joins D to B–C. No cycle.
- Add AB (6): joins A. No cycle.
- Add DE (7): joins E. Now all 5 vertices are connected with 4 edges — stop.
- (The next edge BD = 8 would make the cycle B–C–D–B, so it would be skipped anyway.)
Final answer
MST edges BC, CD, AB, DE; total length 22 (i.e. 2200 m of cable).
Free preview
This is the free notes preview
You're reading the free notes. Aimnova Pro unlocks the full study experience — and you can try it with your first topic free to keep:
- FlashcardsLock in vocabulary and key terms with spaced repetition.
- Practice questionsAnswer exam-style questions and get instant AI marking.
- Mock exams & past-paper vaultSit full mocks and see exactly how examiners award marks.
- Personalised study planA daily plan built around your exam date and weak areas.
Grow the tree outward from one vertex: Prim's algorithm builds the same minimum spanning tree, but a different way — it grows one connected tree.
Prim's algorithm
Start
Start at any vertex.
Add the cheapest edge out
Look at every edge that leaves the tree you have so far, and add the cheapest one that reaches a new vertex.
Repeat
Repeat until all vertices are in the tree.
Why it works
- Because you only ever reach new vertices, you can never form a cycle.
- Prim's and Kruskal's always give the same total weight (and usually the same tree when the weights are all different).
From a distance table: In the exam the graph is often given as a distance table (a matrix). Prim's on a table: cross out the start column, ring the smallest entry in the start row, then keep ringing the smallest entry in any ringed row that reaches an un-ringed column.
IB-style question — Prim's algorithm
Use Prim's algorithm, starting at vertex A, to find the minimum spanning tree of the same network (AB = 6, AC = 9, BC = 4, BD = 8, CD = 5, CE = 11, DE = 7).
Step by step
- Start at A. Cheapest edge from A is AB = 6 — add it. Tree = {A, B}.
- Edges leaving {A,B} to new vertices: AC = 9, BC = 4, BD = 8. Cheapest is BC = 4.
- Edges to new vertices: BD = 8, CD = 5, CE = 11. Cheapest is CD = 5.
- Edges to E: CE = 11, DE = 7. Cheapest is DE = 7.
- All 5 vertices included.
Final answer
Same MST as Kruskal — edges AB, BC, CD, DE; total weight 22. (Order added differs; the tree is the same.)