Minimum spanning trees: the cheapest safe edge

A county wants to join six towns, A to F, with fibre. Cable could go along nine routes, each with a cost, from 2 between C and F up to 15 between B and D. Every town must reach every other, directly or through other towns, for the smallest total bill.

The cheapest network never has a loop: any one cable on a cycle could be left out and every town would still be connected. So the answer is a tree, five cables for six towns. Trying every tree is hopeless: ten towns that could all be linked to each other allow 100 million of them. Instead, two greedy algorithms, Kruskal's and Prim's, keep taking the cheapest cable that is safe to take. This lesson is about what makes a cable safe.

spanning tree

A set of a graph's edges that connects every node and contains no cycle. With V nodes it always has exactly V − 1 edges.

minimum spanning tree (MST)

A spanning tree with the least total weight, in a connected, undirected, weighted graph. A disconnected graph gets a minimum spanning forest, one tree per component.

component

A group of nodes joined by the edges chosen so far. Kruskal's starts with every node in a component of its own and tracks them with union-find.

cut

A split of the nodes into two groups. An edge crosses the cut when its two ends are in different groups.

key[v]

In Prim's algorithm, the weight of the cheapest single edge known from the tree to v, or ∞ while there is none.

Why should the cheapest edge be safe? Split the nodes into any two groups. Some edge must cross between them, or the groups could never be connected. Call the lightest crossing edge e, and suppose a cheapest tree leaves e out. Adding e to that tree makes a cycle, which crosses the split along e and so must cross back along another tree edge, f, at least as heavy as e. Swap f for e: still connected, no heavier, so a cheapest tree contains e. That swap is an exchange argument, as in the greedy algorithms lesson, and it proves the cut property.

Kruskal's algorithm sorts the edges by weight and tries them cheapest first. If an edge's ends are in different components, it keeps the edge and merges them. Every lighter edge was tried earlier and now has both ends in one component, so the new edge is the lightest leaving its component. If the ends are already in one component, the edge would close a cycle and is rejected. Union-find answers "same component?" in nearly constant amortised time.

Prim's algorithm grows one tree instead, from a start node. Its cut is always the tree against everything else, so the cheapest edge leaving the tree is safe. A min-heap finds that edge: every node outside the tree has a key, and when a node joins, its edges can lower its neighbours' keys. Old heap entries are skipped as stale.

Same six towns, but now Prim's starts from E. Before each step, predict which node joins the tree next, and whether an edge gives a node outside the tree a cheaper link.

From E, Prim's adds E–D, E–F, F–C, C–B and B–A: another order, but the same five edges as from A, since this graph has only one minimum spanning tree.

Here is Kruskal's algorithm on four nodes, 0 to 3, with the edges already sorted, each as [weight, u, v]. forest is a union-find parent list, every node starting as its own root. For each edge the code climbs from u to its root, a, and from v to its root, b. Equal roots mean the edge would close a cycle; different roots mean forest[b] = a joins two components.

edges = [[1, 0, 1], [2, 2, 3], [3, 1, 3], [4, 0, 2]]
forest = [0, 1, 2, 3]
total = 0
for w, u, v in edges:
    a = u
    while forest[a] != a:
        a = forest[a]
    b = v
    while forest[b] != b:
        b = forest[b]
    if a == b:
        print('skip ' + str(u) + '-' + str(v))
    else:
        forest[b] = a
        total += w
        print('keep ' + str(u) + '-' + str(v))
print(total)

To stay short, the code skips union by rank and path compression. With both, each climb is nearly O(1) amortised, so the sort dominates: Kruskal's is O(E log E), which is also O(E log V), since E is at most V². A real implementation also stops at V − 1 edges, as the visualiser does. Edge 1-3 is where a tempting shortcut goes wrong.

Stopping Kruskal's while k components remain is a simple clustering, the same as deleting the k − 1 heaviest edges of the finished tree: the closest members of different groups end up as far apart as possible. The finished tree also approximates the travelling salesman: when going direct is never longer than a detour, walking round it and skipping towns already seen gives a round trip at most twice the shortest.

Prim's has the shape of Dijkstra's algorithm, down to the min-heap, the stale entries and O(E log V) with a binary heap. What differs is the number each node holds. Dijkstra's asks whether dist[u] + w beats dist[v], a whole route from the start; Prim's asks whether w alone beats key[v], one edge into the tree.

When edges weigh the same, the order they are tried in is a tie-break, and another tie-break can give another tree.

• A spanning tree joins all V nodes with V − 1 edges and no cycle; a minimum spanning tree has the least total weight.
• The cut property: across any split of the nodes, the lightest edge belongs to a minimum spanning tree. It makes both greedy algorithms correct.
• Kruskal's tries edges cheapest first and keeps each one whose ends have different roots in union-find: O(E log E), for the sort. Touched ends can still be in different components.
• Prim's grows one tree from a start, adding the cheapest edge leaving it with a min-heap: O(E log V). It is Dijkstra's shape, comparing w with key[v] instead of dist[u] + w with dist[v].
• The tree minimises the total, not routes: its path between two nodes can be far longer than the shortest. Equal weights can give several minimum spanning trees; distinct weights give exactly one.
• Next: clustering, by stopping Kruskal's early or with k-means. Practise the component check with The Extra Edge and Count Connected Groups, and shortest routes, for contrast, with Signal Spread Time. In the Prim's and Kruskal's visualisers, try Two islands.