Unit 12: Cheapest Network

Six houses, eight possible cables, one budget

Each cable has a price. Lay enough of them that every house is joined to every other, directly or through neighbours, for as little money as possible.

The answer always uses exactly n - 1 cables — any more and one of them is closing a loop, which joins nothing new.

Python

edges = [(0, 1, 3), (0, 4, 5), (1, 2, 5), (1, 4, 6), (2, 3, 9), (2, 5, 3), (3, 5, 7), (4, 5, 2)]

for a, b, w in sorted(edges, key=lambda e: e[2]):
    print(w, a, b)

It prints

2 4 5
3 0 1
3 2 5
5 0 4
5 1 2
6 1 4
7 3 5
9 2 3

Take the cheapest cable that joins two separate groups

Go down the sorted list. If a cable joins two houses that are already connected, it can only be closing a loop — skip it. Otherwise take it.

That is Kruskal's algorithm, and everything hard about it is in the words "already connected".

Why this greedy one is safe

Split the houses into any two piles. The cheapest cable crossing that split must be in some best answer: take any best answer that lacks it, add it — you get a loop — and remove another cable of that loop that crosses the split. The result still joins everything, and cost no more.

Kruskal only ever takes a cheapest crossing cable, so it stays inside a best answer the whole way. That is the argument unit 4 said to look for.

The structure that answers it

Union-find keeps a forest of groups. Each item points at another item in its group, and following the chain far enough reaches the root — the one pointing at itself.

Two items are in the same group exactly when they have the same root. Joining two groups is one assignment: point one root at the other.

Python

parent = list(range(6))

def find(x):
    while parent[x] != x:
        x = parent[x]
    return x

def union(a, b):
    a = find(a)
    b = find(b)
    if a == b:
        return False
    parent[a] = b
    return True

print(union(0, 1), union(1, 2), union(0, 2))
print([find(i) for i in range(6)])

It prints

True True False
[2, 2, 2, 3, 4, 5]

False means "already together"

union returning False is the answer Kruskal needs: the cable was pointless. That is why it returns something at all.

After joining 0-1 and 1-2, the roots of 0, 1 and 2 are all 2, while 3, 4 and 5 are still alone.

Flatten the chain while you walk it

Long chains make find slow. Fix it as you go: point each node you pass straight at its grandparent, and the chain halves every time it is used.

With that one extra line, a million operations cost about a million steps. It is called path compression and it is never worth leaving out.

Python

parent = [1, 2, 3, 4, 4]

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

print(find(0))
print(parent)

It prints

4
[2, 2, 4, 4, 4]

What else it is good for

Anything shaped like "these two are now connected, are these two connected?". Friend groups, islands joining as water drains, whether adding a road makes the map one piece.

It cannot un-join, though. If a problem removes edges, the usual trick is to run time backwards.

Sort, then join what is not joined

The two halves are now written. Sort the cables by price, walk down the list, and take a cable whenever union says the two ends were in different groups.

Five cables, twenty pounds.

Python

n = 6
edges = [(0, 1, 3), (0, 4, 5), (1, 2, 5), (1, 4, 6), (2, 3, 9), (2, 5, 3), (3, 5, 7), (4, 5, 2)]
parent = list(range(n))

def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x

total = 0
used = []
for a, b, w in sorted(edges, key=lambda e: e[2]):
    ra = find(a)
    rb = find(b)
    if ra != rb:
        parent[ra] = rb
        total += w
        used.append((a, b, w))

print(used)
print(total)

It prints

[(4, 5, 2), (0, 1, 3), (2, 5, 3), (0, 4, 5), (3, 5, 7)]
20

Where the time goes

Sorting the cables is m log m and dominates everything. The union-find work is so close to m that it is usually written as if it were.

So Kruskal is "the cost of sorting", which for 200000 cables is a few million steps.

When the graph is in pieces

If the houses are in two groups with no cable between them, nothing can join them and the loop simply ends with fewer than n - 1 cables taken.

Count them. Fewer than n - 1 means "impossible", which is exactly what a problem wants told.

Grow one blob instead of joining many

Prim's algorithm starts at one house and repeatedly buys the cheapest cable leading out of the blob to a house not yet in it.

That is Dijkstra with one line changed: the heap holds the price of the cable, not the distance from the start.

Python

import heapq

n = 6
edges = [(0, 1, 3), (0, 4, 5), (1, 2, 5), (1, 4, 6), (2, 3, 9), (2, 5, 3), (3, 5, 7), (4, 5, 2)]
adj = [[] for i in range(n)]
for a, b, w in edges:
    adj[a].append((b, w))
    adj[b].append((a, w))

seen = [False] * n
heap = [(0, 0)]
total = 0
order = []
while heap:
    w, node = heapq.heappop(heap)
    if seen[node]:
        continue
    seen[node] = True
    total += w
    order.append(node)
    for nxt, weight in adj[node]:
        if not seen[nxt]:
            heapq.heappush(heap, (weight, nxt))

print(order)
print(total)

It prints

[0, 1, 2, 5, 4, 3]
20

Twenty again, by a different route

Prim bought its cables in a different order from Kruskal and spent exactly the same. Both are best answers, and a graph can have several.

Use Kruskal when the edges arrive as a list — which is nearly always. Use Prim when the graph is dense, or when the edges are easier to generate than to store.

Now read the proof again

The cut property never said "cheapest". It said the best cable crossing a split is usable — and best is whatever you sort by.

So sort the other way and the very same code returns the maximum spanning tree: 32 instead of 20.

Python

n = 6
edges = [(0, 1, 3), (0, 4, 5), (1, 2, 5), (1, 4, 6), (2, 3, 9), (2, 5, 3), (3, 5, 7), (4, 5, 2)]

def spanning(reverse):
    parent = list(range(n))

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    total = 0
    for a, b, w in sorted(edges, key=lambda e: e[2], reverse=reverse):
        ra = find(a)
        rb = find(b)
        if ra != rb:
            parent[ra] = rb
            total += w
    return total

print(spanning(False), spanning(True))

It prints

20 32

Where this turns up in disguise

A problem about joining islands so the worst cable on the route is as small as possible has the same answer: the minimum spanning tree. Any other network has a heavier crossing edge somewhere.

Spotting that a problem is really a spanning tree is most of the work; the code is ten lines you already have.