Take the cheapest link that joins two groups

Go through the links from cheapest to dearest Add one only when it joins places that are not yet connected, and stop when every place is

Cheapest first, no loops

25346ABCD
Four places and five links.

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.

More

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.

Lesson help

Take the links from cheapest up, skip any whose ends are already connected, and stop when every place is joined.

About this lesson

Try the method in a practice when you are ready.

Report

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.

25346ABCD
Four places and five links.

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.

25346ABCD
Total 9: the dashed links would close loops.

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.

36571248ABCDE
A to E and B to E are taken.

Try it

Which link do you add next?

  1. C to E, cost 4
  2. 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

Sign in free

Practice without limits and keep your progress.