Kruskal’s algorithm

The same eight towns, joined another way: every road in order of length, kept only if it joins two groups. Watch the groups merge into one tree.

⋯38static int by_weight(const void *x, const void *y)39{40    const struct edge *a = x;41    const struct edge *b = y;42    if (a->w != b->w)43        return (a->w > b->w) - (a->w < b->w);44    if (a->u != b->u)45        return (a->u > b->u) - (a->u < b->u);46    return (a->v > b->v) - (a->v < b->v);47}⋯61    qsort(edges, E, sizeof edges[0], by_weight);62    int total = 0, kept = 0, examined = 0;63    printf("kept:");64    for (int i = 0; i < E && kept < N - 1; i++) {65        examined++;66        if (unite(edges[i].u, edges[i].v)) {67            printf(" %d-%d (%d)", edges[i].u, edges[i].v, edges[i].w);68            total += edges[i].w;69            kept++;70        }71    }72    printf("\ntotal %d, %d of %d edges examined\nparents:", total, examined, E);73    for (int i = 0; i < N; i++)74        printf(" %d", parent[i]);75    printf("\n");76    return 0;

Cheapest first

Prim’s algorithm grows one tree out from a start town. Kruskal’s algorithm starts from the other end: every town is a group of its own, and the roads are taken from cheapest to dearest. A road whose towns are in different groups joins two groups into one, and is kept. A road whose towns are already in one group would close a loop, and is skipped. After V − 1 roads are kept, every town is in one group.

So Kruskal’s algorithm does not grow one tree. It keeps a forest, many small trees, that merge until one is left.

The code and its cost

Sorting with qsort

The roads are a plain array of structs, each with its two towns and its length:

struct edge {
    int u, v, w;
};

The C library’s qsort sorts any array, given the number of elements, the size of each, and a function that compares two of them. It returns a negative number, zero or a positive number as the first should come before, with or after the second:

static int by_weight(const void *x, const void *y)
{
    const struct edge *a = x;
    const struct edge *b = y;
    if (a->w != b->w)
        return (a->w > b->w) - (a->w < b->w);
    if (a->u != b->u)
        return (a->u > b->u) - (a->u < b->u);
    return (a->v > b->v) - (a->v < b->v);
}

(a > b) - (a < b) is 1, 0 or −1, and never overflows the way a - b can. The standard does not say qsort is stable: roads of equal length may come out in any order. So the comparison breaks ties by the towns, and the sorted order is the same on every system.

Keep or skip with union–find

for (int i = 0; i < E && kept < N - 1; i++) {
    examined++;
    if (unite(edges[i].u, edges[i].v)) {
        printf(" %d-%d (%d)", edges[i].u, edges[i].v, edges[i].w);
        total += edges[i].w;
        kept++;
    }
}

The groups are kept by union–find: parent, rank, find and unite are copied from that lesson unchanged, with eight towns. unite answers both questions at once. It returns false when the two towns already have the same root, and the road is skipped; otherwise it joins the groups and returns true, and the road is kept. The loop stops at seven roads, so 3–5, 2–3 and 2–4 are never looked at.

kept: 1-2 (1) 5-7 (1) 0-2 (2) 3-4 (2) 6-7 (2) 4-5 (3) 1-3 (5)
total 16, 9 of 12 edges examined
parents: 1 3 1 3 3 3 3 5

These are the seven roads of Prim’s algorithm, with the same total, 16, found in a different order.

The cost

Sorting E roads takes O(E log E) steps. The union–find work, at most two finds and a link for each road, takes O(E α(V)), nearly linear. So the sort dominates: O(E log E) in all, which is the same as O(E log V), since E is less than V².

Prim against Kruskal

Both find a least-cost spanning tree, and when that tree is unique, as here, both find the same one. Prim’s algorithm grows one tree outwards from a town and needs each town’s roads to hand, so it suits a graph stored by town, and with an array instead of a heap it suits dense graphs. Kruskal’s algorithm needs nothing but the list of roads, and merges a forest.

Running it yourself

gcc -std=c11 -Wall -Wextra -pedantic kruskal.c -o kruskal
./kruskal

Worked example

By hand, with the parents. Start with parent = 0 1 2 3 4 5 6 7. Keep 1–2: 2 goes under 1, 0 1 1 3 4 5 6 7. Keep 5–7: 0 1 1 3 4 5 6 5. Keep 0–2: 2’s root is 1, of higher rank, so 0 goes under 1, 1 1 1 3 4 5 6 5. Keep 3–4: 1 1 1 3 3 5 6 5. Keep 6–7: 7’s root is 5, so 6 goes under 5, 1 1 1 3 3 5 5 5. Keep 4–5: the roots 3 and 5 have equal rank, 5 goes under 3, 1 1 1 3 3 3 5 5. Skip 0–1: both roots are 1. Skip 4–6: find(6) climbs 6 → 5 → 3 and points 6 at 3, 1 1 1 3 3 3 3 5; both roots are 3. Keep 1–3: 1 goes under 3, of higher rank, 1 3 1 3 3 3 3 5.

A cheaper road. If 0–1 cost 1 instead of 4, the sorted list would begin 0–1 1, 1–2 1, 5–7 1. The tree keeps 0–1 and 1–2 instead of 0–2 and 1–2, and weighs 16 − 2 + 1 = 15.

A graph in two pieces. Without the roads 1–3, 2–3 and 2–4, nothing joins 0, 1 and 2 to the other towns. Kruskal’s algorithm looks at every road, keeps six, not seven, and returns a least-cost forest of total 11: one tree for each piece.

Two checks. Why is 4–6 skipped? (4 and 6 are already in one group, through 5 and 7.) How many roads are never looked at? (3: 3–5, 2–3 and 2–4.)

Where it’s used

Network design. Cable, pipes or roads joining every site at the least total length.

Clustering. Stopping Kruskal’s algorithm before the last few joins, or cutting the dearest roads of the finished tree, leaves the points in groups of near neighbours.

Approximate tours. Visiting the towns in the order a walk around the least-cost tree meets them gives a tour at most twice as long as the shortest, when the distances obey the triangle inequality.

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.