Prim’s algorithm

The eight towns of the last lesson, to be joined by the cheapest set of roads. Watch a tree grow from town 0, one cheapest road at a time.

⋯91    bool in_tree[V] = { false };92    int total = 0, added = 0;93    heap_push((struct item){ 0, START, -1 });94    printf("added:");95    while (size > 0 && added < V) {96        struct item x = heap_pop();97        if (in_tree[x.v])98            continue;99        in_tree[x.v] = true;100        added++;101        total += x.key;102        if (x.from >= 0)103            printf(" %d-%d (%d)", x.from, x.v, x.key);104        for (const struct wnode *e = adj[x.v]; e != NULL; e = e->next)105            if (!in_tree[e->to])106                heap_push((struct item){ e->w, e->to, x.v });107    }108    printf("\ntotal %d, %d pushes\n", total, pushes);109    for (int u = 0; u < V; u++) {

Joining every town

Suppose each road can be built at a cost equal to its length, and every town must be reachable from every other. The cheapest choice never includes a loop: one road of a loop could be dropped and every town would still be connected. So the answer is a spanning tree, a set of roads that joins all V towns with no loop. A tree on V towns has exactly V − 1 roads. Its weight is the sum of their lengths, and the goal is a spanning tree of least weight.

Prim’s algorithm grows one tree. It starts with a single town, and at every step adds the cheapest road that leads from a town in the tree to a town outside it.

The code and its cost

The program

Everything before main in prim.c is the same as in dijkstra.c: the towns, the roads, add_arc, and the binary heap of items ordered by key, then town. Only the key changes. In Dijkstra’s algorithm an item’s key was the whole distance from the start; here it is the length of the one road that would join the town:

while (size > 0 && added < V) {
    struct item x = heap_pop();
    if (in_tree[x.v])
        continue;
    in_tree[x.v] = true;
    added++;
    total += x.key;
    if (x.from >= 0)
        printf(" %d-%d (%d)", x.from, x.v, x.key);
    for (const struct wnode *e = adj[x.v]; e != NULL; e = e->next)
        if (!in_tree[e->to])
            heap_push((struct item){ e->w, e->to, x.v });
}

Each town that joins offers every road out of it to a town not yet in the tree. The heap holds all the roads on offer, and gives back the shortest. An item whose town has joined since it was pushed is stale: its road would close a loop, and it is skipped. The loop stops as soon as all eight towns are in, so items still on the heap are never taken.

added: 0-2 (2) 2-1 (1) 1-3 (5) 3-4 (2) 4-5 (3) 5-7 (1) 7-6 (2)
total 16, 13 pushes

Why the cheapest road is safe

Split the towns into two groups, any way at all. The cut property says that if one road crossing between the groups is shorter than every other crossing road, it belongs to every least-cost spanning tree. If a tree left it out, adding it would close a loop that crosses between the groups somewhere else too; dropping that other, longer crossing road would give a spanning tree of smaller weight. Prim’s algorithm uses this split at every step: the towns in the tree against the towns outside it.

Here the tree is the only least-cost one: each of the five roads left out is longer than every tree road on the loop it would close. So every start finds the same seven roads.

Heap or array

With a heap, a road is pushed only from the end that joins first; when its other end joins, the first is already in the tree. So there are at most E + 1 pushes, counting the start, and as many pops, each about log E steps: O(E log V), since log E is less than 2 log V. Here E + 1 = 13, and the program makes 13 pushes.

Without a heap, an array can hold each outside town’s cheapest road into the tree. Each step scans the array for the least, V steps, and the joining town updates its neighbours’ entries. V steps of V each is O(V²), with no log. When nearly every pair of towns is joined, E is close to V²/2 and the array version is faster.

Prim against Dijkstra

The two programs share every line but one. Dijkstra’s algorithm settles the town nearest to the start, adding up distances along routes. Prim’s algorithm adds the town nearest to the tree, looking at one road at a time. The tree of shortest routes and the least-cost tree are different trees in general.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic prim.c -o prim
./prim
gcc -std=c11 -Wall -Wextra -pedantic -DSTART=5 prim.c -o prim5
./prim5

Worked example

Least cost is not shortest route. In the tree, the route from 0 to 7 is 0–2–1–3–4–5–7, 2 + 1 + 5 + 2 + 3 + 1 = 14, the same as Dijkstra’s shortest. But the tree’s route from 0 to 6 goes round through 7: 14 + 2 = 16. The shortest route, 0–2–1–3–4–6, costs 2 + 1 + 5 + 2 + 4 = 14 and uses the road 4–6, which the tree leaves out.

The same tree from every start. From town 5 the roads join in the order 5–7, 7–6, 5–4, 4–3, 3–1, 1–2, 2–0: the same seven roads, total 16.

A dense graph. With V = 1,000 towns and every pair joined, E = 1,000 · 999 / 2 = 499,500 roads. The array version takes about V² = 10⁶ steps. The heap version takes about E log₂ V ≈ 499,500 × 10 ≈ 5 × 10⁶.

Two checks. Why is the road 0–1, length 4, never added? (By the time its item is the shortest on offer, town 1 has joined through 2–1.) How many roads are in a spanning tree of 100 towns? (99.)

Where it’s used

Networks at least cost. Laying out cable, pipes or roads so that every site is connected and the total length is as small as possible.

Circuit wiring. Joining the points that must share a signal with the least total wire.

Clustering. Building the least-cost tree over data points and cutting its longest roads splits the points into groups.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.