Minimum spanning trees

Introduction

You must connect 5 villages with electricity lines, and each possible line has a cost. Which lines should you build so every village is connected, at the smallest total cost? A spanning tree of a connected, undirected, weighted graph is a set of n - 1 edges that joins all n vertices without a cycle; a minimum spanning tree (MST) has the smallest total weight.

Both classic algorithms are greedy, and both are provably correct.

Connecting everything as cheaply as possible is a different question from finding the shortest route between two points. The cheapest network may give some pairs a long way round, which is why these algorithms are different from Dijkstra's.

How it works

Kruskal's algorithm

#include <stdio.h>

typedef struct {
    int u, v, w;
} Edge;

int parent[5];

int find(int x) {   // the root of x's group
    while (parent[x] != x) x = parent[x];
    return x;
}

int main(void) {
    Edge edges[] = {{0, 1, 4}, {0, 2, 1}, {1, 2, 2}, {1, 3, 5}, {2, 3, 8}, {3, 4, 2}, {2, 4, 10}};
    int m = 7, n = 5;
    for (int i = 1; i < m; i++) {   // sort the edges by weight (insertion sort)
        Edge e = edges[i];
        int j = i - 1;
        while (j >= 0 && edges[j].w > e.w) {
            edges[j + 1] = edges[j];
            j--;
        }
        edges[j + 1] = e;
    }
    for (int i = 0; i < n; i++) parent[i] = i;   // every vertex is its own group
    int total = 0;
    for (int i = 0; i < m; i++) {
        int a = find(edges[i].u), b = find(edges[i].v);
        if (a != b) {   // different groups: no cycle
            parent[a] = b;
            total += edges[i].w;
            printf("take %d-%d (%d)\n", edges[i].u, edges[i].v, edges[i].w);
        }
    }
    printf("total weight: %d\n", total);
    return 0;
}

1. Sort the edges by weight.
2. Go through them from the cheapest: take an edge if it joins two vertices that are not yet connected; skip it if it would make a cycle.

To test "already connected?" quickly, Kruskal uses union-find: every vertex has a parent, and following parents leads to the root of its group. Two vertices are connected when they have the same root; taking an edge joins the two groups by pointing one root at the other. Watch parent change as groups merge, and the edge 0–1 being skipped.

Sorting dominates: O(m log m).

Syntax

if (find(u) != find(v)) { take(u, v); join(u, v); }   // Kruskal

if (w[u][v] && !in_tree[v] && w[u][v] < key[v])       // Prim
    key[v] = w[u][v];

Example

#include <stdio.h>
#define N 5
#define INF 1000000

int main(void) {
    int w[N][N] = {   // 0 = no edge
        {0, 4, 1, 0, 0},
        {4, 0, 2, 5, 0},
        {1, 2, 0, 8, 10},
        {0, 5, 8, 0, 2},
        {0, 0, 10, 2, 0},
    };
    int key[N], in_tree[N];
    for (int i = 0; i < N; i++) {
        key[i] = INF;
        in_tree[i] = 0;
    }
    key[0] = 0;
    int total = 0;
    for (int round = 0; round < N; round++) {
        int u = -1;
        for (int i = 0; i < N; i++)   // the cheapest vertex to join next
            if (!in_tree[i] && (u == -1 || key[i] < key[u])) u = i;
        in_tree[u] = 1;
        total += key[u];
        for (int v = 0; v < N; v++)
            if (w[u][v] && !in_tree[v] && w[u][v] < key[v]) key[v] = w[u][v];
    }
    printf("total weight: %d\n", total);
    return 0;
}

Prim grows one tree from vertex 0. At each step it adds the cheapest edge that leaves the tree, like Dijkstra, but comparing single edge weights instead of path lengths. key[v] holds the cheapest edge joining v to the tree so far. This array version is O(n²); with a heap it is O(m log n).

Both find an MST of the same total weight: 10 here. (If several edges have equal weights, there can be more than one MST.)

Line by line

1. w is the weight matrix, where 0 means there is no edge.
2. Every key starts at INF except key[0], so vertex 0 is chosen first.
3. Each round finds the vertex outside the tree with the smallest key.
4. That vertex joins the tree, and its key is added to total.
5. The inner loop gives each outside neighbour a better key if this new vertex offers a cheaper edge.
6. After five rounds, all the vertices are in the tree, and total is 10.

Expected result

total weight: 10

In the real world

Planning the cheapest layout of cables, pipes or roads is the direct use. Grouping similar items by repeatedly joining the two closest groups, called single-linkage clustering, is Kruskal's algorithm stopped early.

Common mistakes

• Using a shortest-path tree where a minimum spanning tree is needed: they answer different questions.
• Running either algorithm on a disconnected graph and treating the result as a single tree.
• Skipping the cycle check in Kruskal, so that the result is not a tree.

Best practices

• Check that exactly n - 1 edges were taken, which confirms the graph was connected.
• Use Kruskal for sparse graphs and array-based Prim for dense ones.
• Use path compression in union-find when the graph is large.

Summary

A minimum spanning tree connects every vertex at the lowest total weight. Kruskal adds cheap edges that join separate groups, Prim grows one tree, and both are greedy algorithms that are proven correct.

Mark lesson complete