☕ DSA Java Articles

Topics › Graphs › MinimumSpanningTree/Disjoint Set and Problems

Find the MST weight

Hard TUF ID 517 A2Z

Java source ↗ Edit this article ↗

Problem

Given a connected, undirected, weighted graph with V vertices numbered 0 to V - 1 and its edges [u, v, w], return the sum of the edge weights of a minimum spanning tree: V - 1 edges that connect every vertex with the smallest possible total weight. On the A2Z sheet this row is solved with Kruskal’s algorithm, the edge-centric counterpart to Prim’s. If the graph is disconnected, the Java methods return -1.

Constraints (GeeksforGeeks “Minimum Spanning Tree”): 2 ≤ V ≤ 1000, V - 1 ≤ E ≤ V(V-1)/2, 1 ≤ w ≤ 1000.

Example 1

V = 3, edges = [[0,1,5], [1,2,3], [0,2,1]]
answer = 4          // take 0-2 (1) and 1-2 (3); 0-1 (5) would close a cycle

Example 2

V = 6, edges = [[5,4,9], [5,1,4], [4,1,1], [4,3,5], [1,2,2], [2,3,3], [2,0,7], [1,0,4]]
answer = 14         // 4-1 (1), 1-2 (2), 2-3 (3), 5-1 (4), 1-0 (4)

The idea behind Kruskal’s algorithm

Sort all edges from lightest to heaviest and walk through them. Take an edge if it joins two vertices that are not yet connected by the edges taken so far. Skip it if they already are, because then the edge would close a cycle. Stop after V - 1 edges have been taken.

Why does this produce a minimum spanning tree? When Kruskal’s takes edge e = (u, v), u and v lie in different components of the current forest. Let S be u’s component. Every edge lighter than e has already been examined: it was either taken (and so lies inside a component, not crossing out of S) or skipped (because its endpoints were already in the same component). So e is the lightest edge crossing the cut between S and the rest of the graph, and the cut property says it belongs to some MST. When Kruskal’s skips an edge, that edge would close a cycle, and because edges arrive in sorted order it is at least as heavy as every other edge on that cycle, so by the cycle property dropping it costs nothing.

The only question is how to answer “are u and v already connected?” quickly. That is the whole difference between the two approaches.

Approach 1: Kruskal with a DFS connectivity check

Intuition. Keep the chosen edges in an adjacency list (a forest). For each candidate edge, run a DFS from u inside that forest and see whether it reaches v. It is direct and obviously correct, but it repeats a lot of work: every check re-explores components that have not changed.

Algorithm.

  1. Sort a copy of the edges by weight.
  2. For each edge (u, v, w): if a DFS over the chosen edges reaches v from u, skip it. Otherwise add it to the forest in both directions, add w to the total, and count it.
  3. Return the total if V - 1 edges were taken, else -1.
static int kruskalWithDfs(int n, int[][] edges) {
    int[][] sorted = edges.clone();
    Arrays.sort(sorted, (a, b) -> Integer.compare(a[2], b[2]));
    List<List<Integer>> forest = new ArrayList<>();
    for (int i = 0; i < n; i++) forest.add(new ArrayList<>());
    int total = 0, used = 0;
    for (int[] e : sorted) {
        if (connected(forest, e[0], e[1])) continue; // already joined: this edge would close a cycle
        forest.get(e[0]).add(e[1]);
        forest.get(e[1]).add(e[0]);
        total += e[2];
        used++;
    }
    return used == n - 1 ? total : -1;
}

static boolean connected(List<List<Integer>> forest, int s, int t) {
    boolean[] seen = new boolean[forest.size()];
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(s);
    seen[s] = true;
    while (!stack.isEmpty()) {
        int u = stack.pop();
        if (u == t) return true;
        for (int v : forest.get(u)) {
            if (!seen[v]) {
                seen[v] = true;
                stack.push(v);
            }
        }
    }
    return false;
}

Complexity. Sorting costs O(E log E). Each of the E checks is a DFS over a forest with fewer than V edges, so it costs O(V). Total O(E log E + E · V). For V = 1000 and E ≈ 500,000 that is about 5 × 10^8 steps, too slow. Space O(V + E).

Approach 2: Optimal, Kruskal with a disjoint set

Intuition. “Are u and v in the same component?” and “merge their components” are exactly the two operations a disjoint set union supports. With union by size and path compression, each costs amortised O(α(V)), effectively constant. We let union return false when the two vertices already share a root. Then one call both answers the question and performs the merge. We can also stop as soon as V - 1 edges are taken, since the tree is complete and no later edge can be used.

Algorithm.

  1. Sort a copy of the edges by weight. Create a DSU on V elements.
  2. For each edge (u, v, w): if union(u, v) returns false, skip the edge. Otherwise add w to the total, count the edge, and stop once the count reaches V - 1.
  3. Return the total if V - 1 edges were taken, else -1.
static int kruskalWithDsu(int n, int[][] edges) {
    int[][] sorted = edges.clone();
    Arrays.sort(sorted, (a, b) -> Integer.compare(a[2], b[2]));
    DSU dsu = new DSU(n);
    int total = 0, used = 0;
    for (int[] e : sorted) {
        if (!dsu.union(e[0], e[1])) continue;        // same component: skip
        total += e[2];
        if (++used == n - 1) break;                  // a spanning tree is complete
    }
    return used == n - 1 ? total : -1;
}

static class DSU {
    final int[] parent, 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) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    /** Merge the sets of a and b; false if they were already the same set. */
    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;
        if (size[ra] < size[rb]) {
            int tmp = ra;
            ra = rb;
            rb = tmp;
        }
        parent[rb] = ra;
        size[ra] += size[rb];
        return true;
    }
}

Dry run on Example 2. Sorted edges: 4-1 (1), 1-2 (2), 2-3 (3), 5-1 (4), 1-0 (4), 4-3 (5), 2-0 (7), 5-4 (9).

edge same component? action total taken
4-1 (1) no take 1 1
1-2 (2) no take 3 2
2-3 (3) no take 6 3
5-1 (4) no take 10 4
1-0 (4) no take 14 5 = V - 1, stop

The edges 4-3, 2-0 and 5-4 are never examined. Had we continued, all three would have been rejected, since their endpoints are already connected. The answer is 14.

Arrays.sort on objects is stable, so 5-1 comes before 1-0 because it appears earlier in the input. Ties can change which MST is built, but never its weight.

Complexity. Time O(E log E), dominated by the sort. The DSU work is O(E · α(V)). Space O(V) for the DSU, plus O(E) for the sorted copy.

Kruskal or Prim?

Both are greedy and both are correct for the same reason, the cut property. Kruskal’s thinks in edges: sort once, then a nearly free check per edge. It is the natural choice when the input is an edge list, when the graph is sparse, or when you also want the components along the way (it builds a minimum spanning forest of a disconnected graph for free). Prim’s thinks in vertices: it grows one tree from a start vertex and suits adjacency lists and dense graphs, where the O(V²) array version wins.

Edge cases and pitfalls