Kruskal Minimum Spanning Tree — Greedy Edge Selection with Union-Find

Problem Statement#

Given a connected, undirected, weighted graph with n vertices and a list of edges [u, v, w] where w is the edge weight, find the Minimum Spanning Tree (MST) — a subset of edges that connects all vertices with the minimum possible total edge weight, containing no cycles.

Constraints:

• 2 <= n <= 1000
• n - 1 <= edges.length <= 10^4
• Edge weights can be positive or negative integers
• The graph is connected so an MST always exists

Input:  n = 4, edges = [[0,1,10],[0,2,6],[0,3,5],[1,3,15],[2,3,4]]
Output: 19   (MST edges: (2,3,4), (0,3,5), (0,1,10))

Why This Problem Matters#

Minimum spanning trees power network cable layouts, road construction planning, cluster analysis in machine learning, and circuit board routing. Kruskal is the canonical interview answer because it is short, provably correct via the cut property of matroids, and its bottleneck — Union-Find — is itself a frequently tested data structure.

In FAANG interviews Kruskal rarely shows up as a raw "implement an MST" prompt. It is embedded inside problems like LeetCode 1584 (Minimum Cost to Connect All Points), LeetCode 1135 (Connecting Cities with Minimum Cost), and LeetCode 1489 (Find Critical and Pseudo-Critical Edges in MST). Recognizing the problem as MST is half the battle; implementing Kruskal with path-compressed Union-Find is the other half.

Interviewers like Kruskal for two reasons. First, it demonstrates greedy reasoning — you must articulate why always picking the cheapest safe edge is globally optimal. Second, it exercises Union-Find, which appears on its own in connected-component, redundant-connection, and accounts-merge questions.

The Core Insight#

Kruskal applies the greedy cut property: for any cut splitting vertices into two non-empty sets, the minimum-weight edge crossing the cut belongs to some MST.

The algorithm is three steps:

1. Sort all edges by weight ascending.
2. Walk the sorted edges. For edge (u, v, w) use Union-Find: if u and v are in different components, accept the edge and merge them; otherwise skip (it would form a cycle).
3. Stop after accepting n - 1 edges. A spanning tree of n vertices always has exactly n - 1 edges.

Path compression plus union by rank makes each find/union nearly O(1) amortized (O(alpha(n)) inverse Ackermann, effectively constant). The sort is therefore the only super-linear step, giving O(E log E) overall.

Visual Dry Run#

Input: n = 4, sorted edges: (2,3,4), (0,3,5), (0,2,6), (0,1,10), (1,3,15)

The crucial observation is at step 3: vertices 0 and 2 are already connected through 0 - 3 - 2 from steps 1 and 2, so adding (0, 2) would create a cycle.

Solution (Optimal)#

class Solution:
    def kruskal(self, n: int, edges: list[list[int]]) -> int:
        # Sort edges by weight ascending so the greedy picks cheapest first
        edges.sort(key=lambda e: e[2])
 
        parent = list(range(n))  # each node starts in its own component
        rank = [0] * n           # rank tracks tree height for balanced unions
 
        def find(x: int) -> int:
            # Path compression: every node on the path points to the root
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x
 
        def union(x: int, y: int) -> bool:
            rx, ry = find(x), find(y)
            if rx == ry:
                return False  # already connected, edge would create a cycle
            # Union by rank: attach smaller tree under larger
            if rank[rx] < rank[ry]:
                rx, ry = ry, rx
            parent[ry] = rx
            if rank[rx] == rank[ry]:
                rank[rx] += 1
            return True
 
        mst_cost = 0
        edges_taken = 0
        for u, v, w in edges:
            if union(u, v):
                mst_cost += w
                edges_taken += 1
                if edges_taken == n - 1:
                    break  # MST is complete, no need to scan rest
 
        # If fewer than n-1 edges were accepted the graph is disconnected
        return mst_cost if edges_taken == n - 1 else -1

var kruskal = function(n, edges) {
    // Sort edges by ascending weight so greedy picks cheapest first
    edges.sort((a, b) => a[2] - b[2]);
 
    const parent = Array.from({ length: n }, (_, i) => i);
    const rank = new Array(n).fill(0);
 
    const find = (x) => {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]]; // path compression
            x = parent[x];
        }
        return x;
    };
 
    const union = (x, y) => {
        const rx = find(x), ry = find(y);
        if (rx === ry) return false; // cycle would form
        if (rank[rx] < rank[ry]) {
            parent[rx] = ry;
        } else if (rank[rx] > rank[ry]) {
            parent[ry] = rx;
        } else {
            parent[ry] = rx;
            rank[rx]++;
        }
        return true;
    };
 
    let cost = 0, taken = 0;
    for (const [u, v, w] of edges) {
        if (union(u, v)) {
            cost += w;
            if (++taken === n - 1) break;
        }
    }
    return taken === n - 1 ? cost : -1;
};

Time: O(E log E) dominated by the sort; Union-Find ops are O(alpha(V)) effectively constant Space: O(V) for parent and rank arrays

Common Mistakes#

• Skipping path compression so find degrades to O(V) and the algorithm becomes O(E times V).
• Forgetting to verify that n - 1 edges were actually accepted; on a disconnected input you must report no MST.
• Mixing 0-indexed and 1-indexed vertices between input and Union-Find arrays, producing silent wrong answers.
• Confusing MST with shortest path. MST minimizes total weight of the spanning tree; Dijkstra and Bellman-Ford answer single-source shortest path.
• Accumulating the MST cost into a 32-bit signed integer when weights and n are large; use 64-bit totals.

Interview Tips#

• Verbally state the recognition cue: "minimum cost to connect all vertices, this is MST."
• Compare Kruskal versus Prim before coding. Kruskal wins for sparse graphs (sort dominates), Prim wins for dense graphs with adjacency matrices.
• Implement Union-Find as a small helper class before the main loop; this makes the code reusable for redundant-connection or account-merge follow-ups.
• After accepting n - 1 edges break out early; do not iterate the rest unnecessarily.
• If asked to enumerate the MST edges, append (u, v, w) to a list inside the union branch.

Follow-up Questions#

• What if the graph has multiple MSTs of equal weight? Hint: Kruskal returns one valid MST; enumerating all requires backtracking over equal-weight edges.
• Can you find an MST when edge weights are negative? Hint: yes, only relative weights matter to the cut property.
• How would you solve LC 1584 Minimum Cost to Connect All Points? Hint: build the complete graph using Manhattan distances, then run Kruskal or Prim.
• How do you find the second-best spanning tree? Hint: remove each MST edge in turn and find the cheapest replacement edge that restores connectivity.
• Can Union-Find detect a cycle in an undirected graph? Hint: yes, the first edge whose endpoints share a root is the cycle-closing edge (LC 684 Redundant Connection).

Key Takeaways#

• Kruskal is greedy correctness made rigorous: pick the cheapest edge that does not create a cycle and the cut property guarantees optimality.
• Union-Find with path compression and union by rank reduces cycle detection to nearly constant per edge, leaving the sort as the bottleneck at O(E log E).
• Always verify n - 1 edges were accepted before returning a cost; otherwise the graph is disconnected and no MST exists.
• Choose Kruskal for sparse graphs, Prim for dense graphs; both produce a valid MST with the same total weight.
• Path compression is non-negotiable; without it the algorithm becomes O(E times V) and times out on stress tests.
• The same Union-Find helper powers MST, redundant-connection, account-merge, and connected-component problems; treat it as a reusable building block.
• Whenever you read "minimum cost to connect" in an interview, your first thought should be sort edges plus Union-Find.