Cheapest cables that still reach every house: 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. The cheapest connecting network with no cycle is a minimum spanning tree (MST).
For a graph with n vertices, the MST always has exactly n − 1 edges.
Kruskal's algorithm: sort all edges from cheapest to dearest, then add them one at a time — but skip any edge that would create a cycle — until every vertex is joined.
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).
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:
1. Start at any vertex. 2. Look at every edge that leaves the tree you have so far, and add the cheapest one that reaches a new vertex. 3. Repeat until all vertices are in the tree.
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.)