Minimum spanning tree

You’ll recognise it when

• Every node must end up connected, and you choose which links to build: roads between towns, cables between servers, pipes to houses.
• Each possible link has a cost, and you want the smallest total.
• It doesn’t matter how long the route between any two nodes is, only that one exists.
• The problem says “minimum cost to connect all”, or asks for the cheapest set of edges that keeps a graph in one piece.

It’s easy to mix up with shortest paths. Dijkstra makes each route from one source as short as possible; a minimum spanning tree makes the whole network as cheap as possible, even if some routes in it are long.

The idea

You’re a council laying roads between villages, and you have a price list for every road you could build. Start with the cheapest road on the list and build it. Then the next cheapest, and so on. Whenever a road would join two villages that are already connected by roads you built, don’t build it: it adds cost and connects nothing new. Stop once every village is reachable.

That greedy plan is Kruskal’s algorithm, and the result is a minimum spanning tree (MST): a set of n − 1 edges that touches every node, has no cycles, and has the smallest possible total weight. The only tricky part is asking “are these two already connected?” quickly, and that’s exactly what union-find is for.

How it works

Sort the edges once, then look at each one in order and decide: add or skip. Scroll through the steps and the graphic follows along. Nodes share a colour when they’re already in the same tree; edit the edges or press random to try your own graph.

Why taking the cheapest edge is safe: split the nodes into any two sides, and look at the edges that cross between them. The lightest crossing edge always belongs to some minimum spanning tree. If a tree used a heavier crossing edge instead, you could swap it for the lighter one and still have a tree, only cheaper. When Kruskal adds a–b, take one side to be a’s current tree: no tree edge crosses it yet, and every lighter edge was already added or skipped as a cycle, so a–b is the lightest edge leaving it. This is the cut property.

def mst_weight(n, edges):
    """Weight of a minimum spanning tree of nodes 0..n-1, or -1 if the
    graph is disconnected. edges is a list of (w, a, b), undirected."""
    parent = list(range(n))

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

    total, used = 0, 0
    for w, a, b in sorted(edges):
        ra, rb = find(a), find(b)
        if ra == rb:                        # a and b are already connected
            continue
        parent[ra] = rb
        total += w
        used += 1
        if used == n - 1:                   # every node is in one tree
            break
    return total if used == n - 1 else -1

#include <algorithm>
#include <array>
#include <numeric>
#include <vector>
using namespace std;

// Weight of a minimum spanning tree of nodes 0..n-1, or -1 if the graph is
// disconnected. Each edge is {w, a, b}, undirected.
long long mstWeight(int n, vector<array<long long, 3>> edges) {
    vector<int> parent(n);
    iota(parent.begin(), parent.end(), 0);

    auto find = [&](int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];           // path halving
            x = parent[x];
        }
        return x;
    };

    long long total = 0;
    int used = 0;
    sort(edges.begin(), edges.end());
    for (auto [w, a, b] : edges) {
        int ra = find(a), rb = find(b);
        if (ra == rb) {                              // a and b are already connected
            continue;
        }
        parent[ra] = rb;
        total += w;
        used++;
        if (used == n - 1) break;                    // every node is in one tree
    }
    return used == n - 1 ? total : -1;
}

import java.util.*;

class Kruskal {
    // Weight of a minimum spanning tree of nodes 0..n-1, or -1 if the graph
    // is disconnected. Each edge is {a, b, w}, undirected.
    static long mstWeight(int n, int[][] edges) {
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;

        int[][] sorted = edges.clone();
        Arrays.sort(sorted, (x, y) -> Integer.compare(x[2], y[2]));
        long total = 0;
        int used = 0;
        for (int[] e : sorted) {
            int a = e[0], b = e[1], w = e[2];
            int ra = find(parent, a), rb = find(parent, b);
            if (ra == rb) {                                  // a and b are already connected
                continue;
            }
            parent[ra] = rb;
            total += w;
            used++;
            if (used == n - 1) break;                        // every node is in one tree
        }
        return used == n - 1 ? total : -1;
    }

    static int find(int[] parent, int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];                   // path halving
            x = parent[x];
        }
        return x;
    }
}

find uses path halving: every node it passes gets pointed at its grandparent, which keeps the trees shallow without a second loop. total is 64-bit in C++ and Java, because 10⁵ edges of weight 10⁹ add up to far more than 32 bits hold. Negative weights need no special care: Kruskal only ever compares weights, unlike Dijkstra, which adds them up.

Why it’s O(E log E)

Sorting the E edges costs O(E log E). After that, each edge does two find calls and at most one union. Those are close to constant time each, so the loop is roughly O(E), and the sort dominates.

Space is O(V) for parent plus the O(E) edge list you sort.

Common mistakes

return total                               # ✗ looks fine on a disconnected graph
return total if used == n - 1 else -1      # ✓

if parent[a] == parent[b]: continue        # ✗ misses 2–0–1–3
if find(a) == find(b): continue            # ✓

for a, b, w in sorted(edges):                      # ✗ sorted by a
for a, b, w in sorted(edges, key=lambda e: e[2]):  # ✓ sorted by weight

int total = 0;          // ✗ wraps around on big inputs
long long total = 0;    // ✓

Variations

• Prim’s algorithm grows one tree from a start node instead. Keep a min-heap of edges leaving the tree, pop the lightest, and if its far end is new, add it and push that node’s edges. It’s Dijkstra with “edge weight” in place of “distance from the source”, O(E log V). On a dense graph, like every pair of n points, an O(V²) version with a plain array and no heap is faster than sorting all n² edges.
• Maximum spanning tree. Sort the edges heaviest first; the same argument works in reverse. Negate the weights if you’d rather reuse the code.
• Minimum cost to connect cities with some cities able to build their own well or power station: add one extra node for “self-supply”, joined to each city by an edge with that city’s cost, and run Kruskal on the bigger graph.
• Fixed edges. If some links already exist or must be used, union their endpoints (and add their cost) before the loop, then run Kruskal as usual on the rest.
• Second-best MST. Try each non-tree edge a–b: adding it closes a cycle, and removing the heaviest tree edge on the path a–b gives another spanning tree. The cheapest of these swaps is the second-best tree. Precompute path maximums (for example with binary lifting) to make each try fast.