templates · Shortest paths & spanning trees

Kruskal's minimum spanning tree

  • "Minimum total cost to connect everything" and the input is an edge list
  • The graph is sparse: far fewer edges than V²
  • You must ask "is this edge in some or every MST?" (build the MST with and without it)

Minimum spanning tree (Kruskal / Prim)Union-Find (DSU)

the one rule

The invariant

Every edge kept so far joined two different trees, so the kept edges never form a cycle.

write it from memory

The template

Kruskal

javajava.util.*
/** Total weight of a minimum spanning tree. edges[i] = {u, v, w}, undirected. -1 = graph not connected. */static long kruskalMst(int n, int[][] edges) {    int[][] sorted = edges.clone();    Arrays.sort(sorted, (a, b) -> Integer.compare(a[2], b[2])); // cheapest edge first    Dsu dsu = new Dsu(n);    long total = 0;    int used = 0;    int need = Math.max(n - 1, 0);                    // a tree on n nodes has n - 1 edges    for (int[] e : sorted) {        if (used == need) break;                      // tree complete: stop early        if (dsu.union(e[0], e[1])) {                  // joins two trees: keep it            total += e[2];            used++;        }                                             // same tree already: a cycle, skip it    }    return used == need ? total : -1;}

Cheapest edge first. Keep it only if it joins two different trees. Stop once you have V − 1 edges.

fill in the blanks — only these lines change per problem

  1. line 4The order of edges: by weight here. For a maximum spanning tree, sort in reverse.
  2. line 11What you do with a kept edge: add its weight, or save the edge itself.
  3. line 16What to return when fewer than V − 1 edges were kept (the graph is not connected).

the Union-Find it needs

javajava.util.*
/** Union-Find with path halving and union by size. */class Dsu {    private final int[] parent;    private final int[] size;     Dsu(int n) {        parent = new int[n];        size = new int[n];        for (int i = 0; i < n; i++) {            parent[i] = i;            size[i] = 1;        }    }     int find(int x) {        while (parent[x] != x) {            parent[x] = parent[parent[x]];            // skip a level on the way up            x = parent[x];        }        return x;    }     /** false if a and b were already connected (the edge would close a cycle). */    boolean union(int a, int b) {        int ra = find(a), rb = find(b);        if (ra == rb) return false;        if (size[ra] < size[rb]) {                    // hang the smaller tree under the bigger            int tmp = ra;            ra = rb;            rb = tmp;        }        parent[rb] = ra;        size[ra] += size[rb];        return true;    }}

union returns false when both ends are already connected. That one boolean is the whole cycle check.

complexity

What it costs

time O(E log E)
Sorting the edges costs E log E. Each Union-Find call after that is almost O(1) (inverse Ackermann, amortized).
space O(V + E)
The sorted copy of the edges and two arrays of size V in the Union-Find.

watch out

Common bugs

  • Comparing weights with a[2] - b[2]. With big or negative weights this overflows; use Integer.compare.
  • Forgetting the connectivity check at the end. A forest is not a spanning tree.
  • Sorting the caller's array in place when the problem needs the original edge indexes later.

use it

Practise it on

learn it properly