☕ DSA Java Articles

Topics › Graphs › MinimumSpanningTree/Disjoint Set and Problems

MST theory

Easy TUF ID 1221 A2Z

Java source ↗ Edit this article ↗

What this covers

A minimum spanning tree (MST) is the cheapest way to connect every vertex of a weighted, undirected graph. Think of laying cable between towns: every town must be connected to every other one, directly or indirectly, and you want to pay for as little cable as possible. This article defines spanning trees and MSTs, works through an example by hand, and explains the two properties (the cut property and the cycle property) that make the fast algorithms, Prim’s and Kruskal’s, correct. Everything is checked in the Java file by brute force on small graphs, so every claim below is backed by an assertion.

Spanning trees

A spanning tree of a connected undirected graph with n vertices is a subset of its edges that

  1. touches all n vertices,
  2. is connected, and
  3. contains no cycle.

Any tree on n vertices has exactly n - 1 edges. That gives a convenient test: a set of edges is a spanning tree if and only if it has n - 1 edges and connects all n vertices. With fewer edges it cannot be connected. With exactly n - 1 edges and connected, it cannot contain a cycle, because removing a cycle edge would leave a connected graph with only n - 2 edges, which is impossible.

The Java file represents a chosen subset of edges as a bitmask (bit i set means edge i is chosen) and tests it exactly that way: count the bits, then run a DFS over the chosen edges and check that every vertex was reached.

static boolean isSpanningTree(int n, int[][] edges, int mask) {
    if (Integer.bitCount(mask) != n - 1) return false;
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int i = 0; i < edges.length; i++) {
        if ((mask >> i & 1) == 0) continue;
        adj.get(edges[i][0]).add(edges[i][1]);
        adj.get(edges[i][1]).add(edges[i][0]);
    }
    boolean[] seen = new boolean[n];
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(0);
    seen[0] = true;
    int reached = 1;
    while (!stack.isEmpty()) {
        int u = stack.pop();
        for (int v : adj.get(u)) {
            if (!seen[v]) {
                seen[v] = true;
                reached++;
                stack.push(v);
            }
        }
    }
    return reached == n;                             // n - 1 edges + connected => no cycle
}

static int weight(int[][] edges, int mask) {
    int total = 0;
    for (int i = 0; i < edges.length; i++) if ((mask >> i & 1) == 1) total += edges[i][2];
    return total;
}

A graph usually has many spanning trees, and a spanning tree is never unique unless the graph itself is already a tree.

A worked example

Take this graph on vertices 0..4 (edges are numbered in the order listed, which is how the Java masks refer to them):

edge:   #0    #1    #2    #3    #4    #5    #6
        0-1   0-3   1-2   1-3   1-4   2-4   3-4
weight:  2     6     3     8     5     7     9

This graph has 21 different spanning trees, with weights ranging from 16 to 30. The lightest one is {0-1, 1-2, 1-4, 0-3} with weight 2 + 3 + 5 + 6 = 16. That is the minimum spanning tree.

Minimum spanning trees and why brute force fails

The weight of a spanning tree is the sum of its edge weights, and a minimum spanning tree is a spanning tree of the smallest possible weight. The most direct way to find one is to try every subset of n - 1 edges, keep those that are spanning trees, and take the lightest.

static int countSpanningTrees(int n, int[][] edges) {
    int count = 0;
    for (int mask = 0; mask < (1 << edges.length); mask++) if (isSpanningTree(n, edges, mask)) count++;
    return count;
}

static int bruteForceMst(int n, int[][] edges) {
    int best = -1;
    for (int mask = 0; mask < (1 << edges.length); mask++) {
        if (isSpanningTree(n, edges, mask) && (best == -1 || weight(edges, mask) < weight(edges, best))) best = mask;
    }
    return best;
}

This is correct, and useful for checking other code on tiny graphs, but hopeless in general. The number of spanning trees explodes. By Cayley’s formula, the complete graph on n vertices has n^(n-2) spanning trees: 16 for n = 4, 125 for n = 5 (both asserted in the Java file), and already 10^8 for n = 10. The brute force above even tries all 2^E edge subsets, not just the trees. We need structure that lets us build the MST greedily, one safe edge at a time.

The cut property

A cut splits the vertices into two non-empty groups, S and the rest. An edge crosses the cut if it has one endpoint on each side.

Cut property. For any cut, the lightest edge crossing it belongs to some MST. If it is the unique lightest crossing edge, it belongs to every MST.

Why: take any spanning tree T that does not use the lightest crossing edge e = (u, v). Since T is connected, its path from u to v must cross the cut somewhere, using a crossing edge f. Swap them: remove f, add e. The result is still a spanning tree (the two halves that f held together are now joined by e), and its weight changed by w(e) - w(f) ≤ 0. So a tree containing e is at least as light as T.

In the example, take S = {0, 1}. The crossing edges are 0-3 (6), 1-2 (3), 1-3 (8) and 1-4 (5). The lightest is 1-2, and indeed it is in the MST.

static int lightestCrossingEdge(int[][] edges, boolean[] inS) {
    int best = -1;
    for (int i = 0; i < edges.length; i++) {
        boolean crosses = inS[edges[i][0]] != inS[edges[i][1]];
        if (crosses && (best == -1 || edges[i][2] < edges[best][2])) best = i;
    }
    return best;
}

Prim’s algorithm is the cut property applied repeatedly. Let S be the vertices already in the tree, and always add the lightest edge leaving S.

The cycle property

Cycle property. For any cycle in the graph, if one edge on it is strictly heavier than all the others, that edge is in no MST.

Why: if an MST contained that heaviest edge h, removing it would split the tree into two parts. The rest of the cycle still connects the two endpoints of h, so some other cycle edge crosses between the parts. Adding that lighter edge reconnects the tree with smaller total weight, which contradicts minimality.

In the example, 0-1-3 is a cycle with weights 2, 6 and 8. The heaviest edge, 1-3 (8), is not in the MST.

static int heaviestOnCycle(int[][] edges, int[] cycle) {
    int best = cycle[0];
    for (int i : cycle) if (edges[i][2] > edges[best][2]) best = i;
    return best;
}

Kruskal’s algorithm is the cycle property in action. It scans edges from lightest to heaviest and skips any edge whose endpoints are already connected. Such an edge would close a cycle, and because the edges are processed in sorted order, it is at least as heavy as every other edge on that cycle, so dropping it never makes the tree worse.

Uniqueness and ties

If all edge weights are distinct, the MST is unique (the example has exactly one). With equal weights there can be several. A square of four weight-1 edges has four MSTs, one for each side you leave out, all of weight 3. The weight of an MST is always unique, even when the tree is not. That is why problems ask for “the MST weight” rather than “the MST”.

static int countMinimumSpanningTrees(int n, int[][] edges) {
    int best = bruteForceMst(n, edges);
    if (best == -1) return 0;
    int count = 0;
    for (int mask = 0; mask < (1 << edges.length); mask++) {
        if (isSpanningTree(n, edges, mask) && weight(edges, mask) == weight(edges, best)) count++;
    }
    return count;
}

An MST is not a shortest-path tree

A common confusion: the MST minimises the total weight of the edges, not the distance from any particular vertex. Take a triangle a-b (2), b-c (2), a-c (3). The MST is {a-b, b-c} with weight 4. In it, the route from a to c costs 4, although the direct edge costs only 3. The shortest-path tree from a (what Dijkstra builds) is {a-b, a-c} with total weight 5. Each tree is optimal for its own question.

Disconnected graphs and other edge cases