Joining every town as cheaply as possible
Five towns, A to E, are to be joined by roads, and eight roads could be built. Each road carries a weight, its cost. The council does not need every road: it needs every town reachable from every other, directly or through other towns, at the lowest total cost.
A set of edges that joins all the vertices and contains no cycle is a spanning tree. A cycle is never needed, because removing any one edge of a cycle leaves every town still joined, and the total smaller. So the cheapest network is a spanning tree with the least total weight: a minimum spanning tree.
A tree on n vertices always has n − 1 edges. Five towns therefore need exactly four roads, chosen from the eight.
The five towns and the eight roads that could be built, each labeled with its cost.
Cheapest edge first
Kruskal’s algorithm starts by listing the edges in order of weight: AC 2, CE 3, AB 4, BC 5, BD 6, DE 7, CD 8 and BE 9. It then works down the list, and keeps each edge unless it would close a cycle with the edges already kept.
AC, weight 2, is the cheapest edge of all, so it is kept. CE, weight 3, comes next. It reaches E, a town not yet joined, so it is kept. AB, weight 4, brings in B, so it is kept too. Three edges are kept, and the towns A, B, C and E are joined at a cost of 2 + 3 + 4 = 9.
The three edges kept so far, AC, CE and AB, are in gold. They join A, B, C and E at a cost of 2 + 3 + 4 = 9.
Rejecting an edge that closes a cycle
The next edge on the list is BC, weight 5. B and C are already joined, through A: the kept edges AB and AC make the route B-A-C. Adding BC would close the cycle A-B-C, and it would join no new town. So BC is rejected, and the algorithm moves on down the list.
The test is whether the two ends of an edge are already joined to each other by kept edges, not whether each end already has an edge at it.
BC, dashed, would close the cycle A-B-C with the gold edges AB and AC, so it is rejected.
When to stop
BD, weight 6, is next. D is not yet joined to anything, so BD closes no cycle and is kept. That makes four edges, and all five towns are joined, so the tree is finished. The remaining edges, DE 7, CD 8 and BE 9, are never needed.
The minimum spanning tree is AC, CE, AB and BD, and its total weight is 2 + 3 + 4 + 6 = 15.
The minimum spanning tree on its own: four edges for five towns, with total weight 2 + 3 + 4 + 6 = 15.
Why the cheapest edge is safe
Split the towns into two groups, and any spanning tree must use at least one edge between the groups, or the two groups would never be joined. The cheapest edge between the groups can always be used. Add it to a tree that leaves it out, and it closes a cycle. That cycle crosses between the groups somewhere else as well, by an edge that costs at least as much. Remove that edge, and every town is still joined while the total has not gone up.
When BD was taken, A, B, C and E formed one group and D was alone. The edges between them are BD 6, DE 7 and CD 8. A tree that joined D by DE instead would cost 2 + 3 + 4 + 7 = 16, and swapping DE for BD brings it down to 15. Each edge Kruskal keeps is the cheapest edge between two groups that are not yet joined, so the tree it builds is a minimum.
Separate pieces and equal weights
Part way through, the kept edges need not form one connected piece. In a larger network the cheapest edges can sit in different places, and Kruskal keeps several small trees that later edges join together. In the first application below, the buildings form two separate groups until the trench C–G joins them.
When two edges have the same weight, either may be taken first. The two orders can give different trees, but every minimum spanning tree of a network has the same total weight. When all the weights are different, as in the lesson’s network, there is exactly one minimum spanning tree.
AC would close a loop: its towns are already joined by roads of cost < 4, so it is refused and the total stays down
Take the roads in cost order until all six towns are joined
Six towns and nine roads, taken in cost order. After three roads, AB 2 and BC 3 are taken and AC 4 is refused, because A and C are already joined through B. Slide on: CD 5 and DE 6 are taken, CE 7 is refused, and EF 8 joins the sixth town, for a total of 2 + 3 + 5 + 6 + 8 = 24.
The usual mistakes
Taking the four cheapest edges outright. AC, CE, AB and BC cost 2 + 3 + 4 + 5 = 14, which is less than 15, but BC closes the cycle A-B-C and D is not joined at all. That is not a spanning tree.
Keeping the rejected edge as well. Five edges on five towns always contain a cycle, and the total rises to 15 + 5 = 20.
Rejecting an edge because both its ends already have an edge at them. The question is whether the ends are joined to each other, and two separate pieces can each have edges.
Stopping too early or too late. A spanning tree on n vertices has n − 1 edges: four for five towns.
Cable and trenches
In the first application below, a college lays fiber-optic cable between seven buildings, and a gas main later rules out one trench. In the second, a county must link two buildings directly, so that link goes in first and the algorithm runs on the rest.
Worked example: Fiber-Optic Cable Between Seven Buildings on a College Campus, and a Trench That Cannot Be Dug
Question A college will lay fiber-optic cable in trenches so that all seven of its buildings are connected, directly or through other buildings: the admin building A, the cafeteria C, the dormitory D, the gym G, the library L, the music school M and the science block S. The trenches that can be dug, with their lengths in meters, are A–L 85, A–C 90, A–D 120, L–C 70, L–G 110, L–S 150, S–G 95, C–G 105, C–D 100, C–M 140, G–M 60 and D–M 160. No two lengths are equal. (a) Use Kruskal's algorithm to list the trenches in the order they are chosen, naming any trench it rejects on the way, and find the least total length of trench. (b) A survey then finds a gas main under the route of trench C–G, so C–G cannot be dug. What is the least total length now, and which trench takes the place of C–G?
1.Sort the trenches by length: G–M 60, L–C 70, A–L 85, A–C 90, S–G 95, C–D 100, C–G 105, L–G 110, A–D 120, C–M 140, L–S 150, D–M 160.
The trenches sorted from shortest to longest. 2.Take G–M (60), L–C (70) and A–L (85), since none of them closes a cycle. Reject A–C (90): A and C are already connected through L, so it would close the cycle A–L–C.
G–M, L–C and A–L are taken. A–C would close the cycle A–L–C, so it is rejected. 3.Take S–G (95) and C–D (100). The buildings now form two groups, A, L, C, D and G, M, S. C–G (105) joins the two groups, so take it. Six trenches now connect all seven buildings, and the algorithm stops.
S–G, C–D and C–G are taken. Six trenches connect all seven buildings. 4.(a) The order is G–M, L–C, A–L, S–G, C–D, C–G, with A–C rejected. The least total length is 60 + 70 + 85 + 95 + 100 + 105 = 515 m.
(a) The six trenches total 515 m. 5.Without C–G, the algorithm makes the same choices up to C–D, and the two groups are still separate. The next trench in the list is L–G (110), and it joins the group A, L, C, D to the group G, M, S.
Without C–G, the next trench that joins the two groups is L–G. 6.(b) L–G takes the place of C–G, and the least total length is now 515 − 105 + 110 = 520 m. Check: 60 + 70 + 85 + 95 + 100 + 110 = 520.
(b) 515 − 105 + 110 = 520 m, with L–G in place of C–G.
Answer: (a) G–M (60), L–C (70), A–L (85), S–G (95), C–D (100), C–G (105), with A–C rejected; the least total length is 515 m. (b) 520 m, with L–G in place of C–G
Common mistakes
- Taking A–C (90 m) because it is the next shortest trench. A and C are already connected through L, so A–C closes the cycle A–L–C and adds 90 m that connects nothing new.
- Stopping as soon as every building has a trench at it. After C–D every building has one, but the buildings still form two separate groups, A, L, C, D and G, M, S, and one more trench is needed to join them.
More spanning trees and route problems problems, worked step by step →
Worked example: A Fiber Network Joining Six Public Buildings in a County, When the Hospital and the Fire Station Must Be Linked Directly
Question A county will join six public buildings with fiber-optic cable: the hospital H, the fire station F, the police station P, the school S, the town hall T and the water works W. The possible cable routes, with lengths in kilometers, are P–H 6, H–T 7, P–S 9, P–F 8, H–F 11, T–F 5, T–W 10, S–F 4 and F–W 3. No two lengths are equal. (a) What is the least total length of cable that connects all six buildings? (b) The emergency plan requires a direct cable between the hospital and the fire station, so that messages between them never pass through another building. What is the least total length now, and which cable from (a) is no longer needed?
1.Sort the routes by length: F–W 3, S–F 4, T–F 5, P–H 6, H–T 7, P–F 8, P–S 9, T–W 10, H–F 11.
The routes sorted from shortest to longest. 2.Take F–W, S–F and T–F, which join W, S and T to F, and then P–H. Take H–T (7), which joins the pair H, P to the group F, S, T, W. Five cables now connect all six buildings.
Kruskal's algorithm takes five cables, and they connect all six buildings. 3.(a) The least total length is 3 + 4 + 5 + 6 + 7 = 25 km.
(a) The least total is 25 km. 4.For (b), lay H–F (11) first, then take the other routes in order. F–W, S–F, T–F and P–H are taken as before, and with H–F they already connect all six buildings. H–T is rejected, because H and T are already connected through F.
With H–F laid first, H–T would close the cycle H–F–T–H, so it is rejected. 5.(b) The least total length is 11 + 3 + 4 + 5 + 6 = 29 km, which is 4 km more, and the cable H–T is no longer needed. Check: adding H–F to the network from (a) makes the cycle H–F–T–H, and removing the longest other cable on it, H–T at 7 km, gives 25 + 11 − 7 = 29 km.
(b) 29 km, and H–T is no longer needed.
Answer: (a) 25 km; (b) 29 km, and H–T is no longer needed
Common mistakes
- Adding H–F to the network from (a) and keeping all five other cables, 25 + 11 = 36 km. H–F closes the cycle H–F–T–H, so one cable on that cycle is no longer needed.
- Running the algorithm in plain order and waiting for H–F to come up at 11 km. By then all six buildings are connected, so H–F is rejected and the requirement is not met.
More spanning trees and route problems problems, worked step by step →