☕ DSA Java Articles

Topics › Graphs › MinimumSpanningTree/Disjoint Set and Problems

MST using Kruskal's Algo

Hard TUF ID 2823 SDE

Java source ↗ Edit this article ↗

Problem

You are given an undirected weighted graph with V vertices numbered 0 to V - 1 and a list of edges {u, v, w}. Return the total weight of a minimum spanning tree (MST): a set of V - 1 edges that connects every vertex, contains no cycle, and has the smallest possible total weight. The sheet’s version (GFG, “Minimum Spanning Tree”) guarantees a connected graph; the code here returns -1 when the graph is disconnected.

Constraints in the usual version: V up to about 1000, E up to V(V - 1) / 2, weights up to about 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 = 5, edges = [0-1 (2), 0-3 (6), 1-2 (3), 1-3 (8), 1-4 (5), 2-4 (7), 3-4 (9)]
answer = 16         // 0-1 (2) + 1-2 (3) + 1-4 (5) + 0-3 (6)

Why Kruskal’s greedy rule works

Kruskal’s algorithm is one sentence: go through the edges from lightest to heaviest and take an edge whenever its two ends are not yet connected by the edges taken so far.

Taking an edge is safe because of the cut property: for any split of the vertices into two groups, the lightest edge crossing the split belongs to some MST. (Exchange argument: if an MST T avoids that edge e, adding e closes a cycle that must cross the split a second time through some edge f with w(f) ≥ w(e); swapping f for e gives a spanning tree that is no heavier.) When Kruskal takes e = u - v, let A be the piece containing u. Every lighter edge was already examined. A lighter edge crossing out of A would have joined two different pieces at that time (pieces only grow), so it would have been taken and would now be inside A. Hence e is the lightest edge crossing the split between A and everything else, and it is safe.

Skipping an edge is safe because its ends are already connected: adding it would close a cycle in which it is the heaviest edge, and some MST always avoids the heaviest edge of a cycle.

All three approaches below run exactly this rule. They differ only in how they answer the question “are u and v already connected?”. Each one first sorts a copy of the edges by weight:

static int[][] sortedByWeight(int[][] edges) {
    int[][] sorted = edges.clone();
    Arrays.sort(sorted, (a, b) -> Integer.compare(a[2], b[2]));
    return sorted;
}

Approach 1: Kruskal with a DFS connectivity check

Intuition. The most direct way to answer “are u and v connected?” is to search for a path: keep the chosen edges as an adjacency list (a forest) and run a DFS from u, looking for v.

Algorithm.

  1. Sort the edges by weight.
  2. For each edge u - v: if a DFS in the forest finds v from u, skip the edge. Otherwise add it to the forest and add its weight to the total.
  3. Return the total if exactly V - 1 edges were taken, else -1.
static int bruteForce(int V, int[][] edges) {
    List<List<Integer>> forest = new ArrayList<>();
    for (int i = 0; i < V; i++) forest.add(new ArrayList<>());
    int total = 0, used = 0;
    for (int[] e : sortedByWeight(edges)) {
        if (connected(forest, e[0], e[1], V)) continue;    // adding e would close a cycle
        forest.get(e[0]).add(e[1]);
        forest.get(e[1]).add(e[0]);
        total += e[2];
        used++;
    }
    return used == V - 1 ? total : -1;
}

static boolean connected(List<List<Integer>> forest, int s, int t, int V) {
    boolean[] seen = new boolean[V];
    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. Time O(E log E + E · V): the sort, then one DFS over a forest of fewer than V edges for every edge. Space O(V + E). For a dense graph with V = 1000, that is around 5 × 10^8 steps. Most of the work is wasted, because the DFS rebuilds connectivity information that never changes between merges.

Approach 2: Better, component labels

Intuition. Store the answer instead of recomputing it. Give each vertex a label naming its component. Two vertices are connected exactly when their labels match, an O(1) check. Merging two components relabels every vertex of one of them, which costs O(V), but a spanning tree has only V - 1 merges. The many rejected edges now cost O(1) each.

Algorithm.

  1. label[x] = x for all x.
  2. For each edge in sorted order: if label[u] == label[v], skip it. Otherwise rewrite every occurrence of label[v] to label[u] and take the edge.
static int better(int V, int[][] edges) {
    int[] label = new int[V];                              // label[x]: id of the component containing x
    for (int i = 0; i < V; i++) label[i] = i;
    int total = 0, used = 0;
    for (int[] e : sortedByWeight(edges)) {
        int a = label[e[0]], b = label[e[1]];
        if (a == b) continue;                              // same component already
        for (int i = 0; i < V; i++) if (label[i] == b) label[i] = a;
        total += e[2];
        used++;
    }
    return used == V - 1 ? total : -1;
}

Complexity. Time O(E log E + V^2): the sort, O(1) per rejected edge, and V - 1 relabels of O(V). Space O(V) beyond the sorted copy.

Approach 3: Optimal, Disjoint Set Union

Intuition. A Disjoint Set Union (DSU, also called union-find) makes both operations nearly constant time. Each component is a tree of parent pointers whose root is the component’s representative. find(x) follows parents up to the root; union(a, b) links one root under the other. Two tricks keep the trees flat:

Together they give an amortised cost of O(α(V)) per operation, where α is the inverse Ackermann function, at most 4 for any input that fits in memory.

static final class DisjointSet {
    final int[] parent, size;

    DisjointSet(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]];                 // path halving: skip a level on the way up
            x = parent[x];
        }
        return x;
    }

    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) return false;                        // already in the same set
        if (size[ra] < size[rb]) {
            int t = ra;
            ra = rb;
            rb = t;
        }
        parent[rb] = ra;                                   // hang the smaller tree under the larger
        size[ra] += size[rb];
        return true;
    }
}

Algorithm.

  1. Sort the edges by weight; create a DSU over V vertices.
  2. For each edge, union(u, v) returns true exactly when the ends were in different sets; then take the edge.
  3. Stop early once V - 1 edges are taken. Return the total, or -1 if fewer than V - 1 edges were taken.
static int optimal(int V, int[][] edges) {
    DisjointSet ds = new DisjointSet(V);
    int total = 0, used = 0;
    for (int[] e : sortedByWeight(edges)) {
        if (used == V - 1) break;                          // tree complete, the rest cannot be used
        if (ds.union(e[0], e[1])) {
            total += e[2];
            used++;
        }
    }
    return used == V - 1 ? total : -1;
}

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

Edge Roots of the two ends Action Total Taken
0-1 (2) 0 and 1 union 2 1
1-2 (3) 0 and 2 union 5 2
1-4 (5) 0 and 4 union 10 3
0-3 (6) 0 and 3 union 16 4 = V - 1
remaining not examined early stop 16 4

Without the early stop, 2-4 (7) would find both ends with root 0 and be rejected, and so would the rest.

Complexity. Time O(E log E) for the sort plus O(E · α(V)) for the unions, so O(E log E) overall. Space O(V) for the DSU plus O(E) for the sorted copy. Compared with Prim, Kruskal is the natural choice when the graph already comes as an edge list and is sparse; Prim with an array wins on very dense graphs.

Edge cases and pitfalls