Cheapest first, no loops
Places may connect through other places, so the network needs no loops. A loop means some link could go and every place would still be connected, which only wastes its cost.
So sort the links by cost and take them from the cheapest. For each one, ask whether its two ends are already connected by links you have taken. If not, add it: it joins two separate groups. If they are, skip it, because it would close a loop.
Stop when every place is in one group. This always gives the lowest total cost. Links of equal cost can give networks that look different but cost the same.
1Take the links from cheapest to dearest.
2Add a link only if its ends are not yet connected.
3Stop when every place is connected.
Four places
Cheapest is A to B, cost 2: add it. Next is C to D, cost 3: C and D are not connected yet, so add it. Next is D to A, cost 4: it joins the group A, B to the group C, D, so add it.
Every place is now connected, for 2 + 3 + 4 = 9. The links of cost 5 and 6 would each close a loop, so they are left out.
Five places
Five places: four corners and E in the middle. You have taken A to E, cost 1, and B to E, cost 2.
Decide the next link the method takes.
Try it
Which link do you add next?
- C to E, cost 4
- A to B, cost 3
Show the answer
C to E, cost 4
Right. A to B is cheaper, but A and B are already connected through E, so it would close a loop. The next link that joins a new place is C to E, cost 4. Then C to D, cost 5, connects the last place, for a total of 12.
Enable JavaScript to answer interactively and save your place.
Practice Connect the community