Minimum Spanning Trees

The problem

Given a connected weighted graph, choose a subset of edges that keeps everything connected while minimizing the total weight. The result is a tree: V - 1 edges, no cycles.

Statements that reduce to this:

• Connect all towns with the least total length of road
• Lay cable to every building as cheaply as possible
• Minimize the largest single connection in a network
• Group items so that similar ones end up together

The last two are less obvious and are covered below.

Kruskal’s algorithm

Sort all edges by weight, then add each one unless it would form a cycle. A union-find structure answers “would this form a cycle” in near-constant time.

static int[] parent, rank_;

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

static boolean union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return false;          // already connected — adding would cycle
    if (rank_[ra] < rank_[rb]) { int t = ra; ra = rb; rb = t; }
    parent[rb] = ra;
    if (rank_[ra] == rank_[rb]) rank_[ra]++;
    return true;
}

static long kruskal(int[][] edges, int n) {
    Arrays.sort(edges, (x, y) -> Integer.compare(x[2], y[2]));

    parent = new int[n + 1];
    rank_ = new int[n + 1];
    for (int i = 0; i <= n; i++) parent[i] = i;

    long total = 0;
    int used = 0;
    for (int[] e : edges) {              // {from, to, weight}
        if (union(e[0], e[1])) {
            total += e[2];
            if (++used == n - 1) break;  // tree complete
        }
    }
    return used == n - 1 ? total : -1;   // -1 means the graph was disconnected
}

The cost is O(E log E), dominated by the sort. Union-find contributes an almost-constant factor per operation.

Kruskal’s is usually the one to write. It is short, the union-find is reusable, and it works directly from an edge list — which is how weighted graphs are typically given.

Prim’s algorithm

Grow the tree from one node, repeatedly taking the cheapest edge that leaves the current tree. This is Dijkstra’s shape with a different comparison.

static long prim(List<List<Edge>> adj, int n) {
    boolean[] inTree = new boolean[n + 1];
    PriorityQueue<long[]> pq =
        new PriorityQueue<>((x, y) -> Long.compare(x[1], y[1]));

    pq.add(new long[]{1, 0});            // {node, cost to attach it}
    long total = 0;
    int count = 0;

    while (!pq.isEmpty()) {
        long[] top = pq.poll();
        int u = (int) top[0];
        if (inTree[u]) continue;         // stale entry

        inTree[u] = true;
        total += top[1];
        count++;

        for (Edge e : adj.get(u)) {
            if (!inTree[e.to]) {
                pq.add(new long[]{e.to, e.weight});
            }
        }
    }
    return count == n ? total : -1;
}

Note the difference from Dijkstra: the priority is the single edge weight, not the accumulated distance from the source. Using a running total here would compute something else entirely.

O(E log V). Prefer Prim’s when the graph is dense and given as an adjacency structure; prefer Kruskal’s otherwise.

Minimizing the largest edge

Find a route between two nodes that minimizes the heaviest single edge used.

This is not a shortest-path problem — the sum does not matter, only the maximum. The minimum spanning tree solves it: the path between any two nodes in the MST minimizes the largest edge on the path.

So a common pattern is to run Kruskal’s and stop as soon as the two nodes of interest become connected. The weight of the edge that connected them is the answer.

Arrays.sort(edges, (x, y) -> Integer.compare(x[2], y[2]));
for (int[] e : edges) {
    union(e[0], e[1]);
    if (find(source) == find(target)) {
        System.out.println(e[2]);        // this edge is the bottleneck
        break;
    }
}

Adding edges in increasing order means the first moment the two become connected uses the smallest possible maximum. This “bottleneck” framing appears often and is easy to miss.

Clustering

Split N points into K groups so that the smallest distance between two different groups is as large as possible.

Run Kruskal’s and stop after adding V - K edges. The remaining components are the groups, and the next unused edge weight is the answer. Building the MST and cutting the K - 1 heaviest edges produces exactly this grouping.

MST variants

The last row is a useful trick: pre-existing connections are just unions applied before the main loop, so they cost nothing and prevent redundant edges.

Related