Kruskal’s Algorithm

Kruskal’s is greedy at its most literal: line up every edge cheapest-first, and add each one unless it would close a loop. The only hard part — “would this edge form a cycle?” — is answered in near-constant time by the Union-Find you built two days ago. Sort, then union. That’s the whole algorithm.

Kruskal’s algorithm (1956) builds the MST by processing edges in order of increasing weight. At each step it asks: does adding this edge create a cycle? If not, add it; if yes, skip it.

This is a direct application of the cut property. When Kruskal’s adds edge (u, v), the two connected components containing u and v form a natural cut. The edge being considered is the lightest crossing edge for that cut (since all cheaper edges were already processed). By the cut property, it’s safe.

The algorithm

(A,B,4), (A,C,2), (B,C,1), (B,D,5), (C,E,8), (D,E,2), (D,F,6), (E,F,3)

Worked example

Graph: 6 vertices A–F, edges as above.

Total weight: 1 + 2 + 2 + 3 + 5 = 13.

Implementation

struct UnionFind {
    vector<int> parent, rank;
    UnionFind(int n) : parent(n), rank(n, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);  // path compression
        return parent[x];
    }
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank[px] < rank[py]) swap(px, py);
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        return true;
    }
};
 
int kruskal(int n, vector<tuple<int,int,int>>& edges) {
    // edges: (weight, u, v)
    sort(edges.begin(), edges.end());
    UnionFind uf(n);
    int totalWeight = 0, edgesAdded = 0;
    for (auto [w, u, v] : edges) {
        if (uf.unite(u, v)) {
            totalWeight += w;
            edgesAdded++;
            if (edgesAdded == n - 1) break;
        }
    }
    return edgesAdded == n - 1 ? totalWeight : -1;  // -1 if not connected
}

def kruskal(n, edges):
    # edges: list of (weight, u, v)
    parent = list(range(n))
    rank = [0] * n
 
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])  # path compression
        return parent[x]
 
    def unite(x, y):
        px, py = find(x), find(y)
        if px == py:
            return False
        if rank[px] < rank[py]:
            px, py = py, px
        parent[py] = px
        if rank[px] == rank[py]:
            rank[px] += 1
        return True
 
    edges.sort()
    total = edges_added = 0
    for w, u, v in edges:
        if unite(u, v):
            total += w
            edges_added += 1
            if edges_added == n - 1:
                break
    return total if edges_added == n - 1 else -1

int[] parent, rank;
 
int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
}
 
boolean unite(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return false;
    if (rank[px] < rank[py]) { int tmp = px; px = py; py = tmp; }
    parent[py] = px;
    if (rank[px] == rank[py]) rank[px]++;
    return true;
}
 
int kruskal(int n, int[][] edges) {
    // edges[i] = {weight, u, v}
    Arrays.sort(edges, (a, b) -> a[0] - b[0]);
    parent = new int[n];
    rank = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
 
    int total = 0, added = 0;
    for (int[] e : edges) {
        if (unite(e[1], e[2])) {
            total += e[0];
            if (++added == n - 1) break;
        }
    }
    return added == n - 1 ? total : -1;
}

Recall the two lines that make it Kruskal’s — process edges in the right order, and the condition for keeping one:

# ??? the order / the keep-condition
total = edges_added = 0
for w, u, v in edges:
  # ??? the order / the keep-condition
      total += w
      edges_added += 1
      if edges_added == n - 1:      # spanning tree complete
          break
return total if edges_added == n - 1 else -1

Correctness

At every step, the edge added by Kruskal’s satisfies the cut property:

• Let S = the component containing u (before the union).
• Let V − S = everything else (includes v’s component).
• The edge (u, v) is the lightest crossing edge for this cut — all lighter edges were already processed, and since none of them connected u’s component to v’s component (they were either inside a single component or already added), (u, v) is cheapest.
• By the cut property, (u, v) is in some MST. Since we greedily add the globally cheapest safe edge at each step, the result is the MST.

Complexity

α is the inverse Ackermann function — effectively constant (≤ 5 for any realistic input). The sort dominates. Note that O(E log E) = O(E log V) because E ≤ V² so log E ≤ 2 log V.

When to use Kruskal’s

Kruskal’s is optimal for sparse graphs where E ≈ V:

• Road networks (roughly planar — E ≈ 3V by Euler’s formula)
• Network cable layout with a given list of possible connections
• When edges are given as a list (not an adjacency matrix)

For dense graphs where E ≈ V², Prim’s with an adjacency matrix is faster: O(V²) vs Kruskal’s O(E log E) = O(V² log V).

Kruskal’s for minimum spanning forest

If the graph isn’t connected, Kruskal’s naturally builds a minimum spanning forest — one MST for each connected component. Just remove the edgesAdded == n - 1 early exit condition.

Quick check

Kruskal’s is the edge-centric MST builder — best when edges come as a list and the graph is sparse. Next: Prim’s algorithm — the vertex-centric alternative that grows one connected tree from a start node using a priority queue (the Day 7 heap again), and wins on dense graphs.