Kruskal's Algorithm: A Step-by-Step Interview Walkthrough

Jun 10

11 min read

Minimum Spanning Tree problems are a staple of technical interviews because they sit at the intersection of greedy reasoning and the Union-Find data structure — two things interviewers love to test together. The task sounds simple: connect every node in a weighted graph as cheaply as possible, without redundant edges. But the interesting part is why the greedy approach works. It's tempting to grab the cheapest edges and hope, but a candidate who can explain why always taking the cheapest cycle-free edge is provably optimal — and who can wire up Union-Find to enforce the cycle-free part — demonstrates a deeper grasp than someone who just memorized "Kruskal's algorithm." The signal here is whether you understand greedy correctness and can apply Union-Find fluently, not just whether you can recite the steps.

Minimum spanning trees underpin real infrastructure everywhere. Network designers use them to lay out cabling, fiber, or circuit connections at minimum cost while keeping everything connected. Utility companies plan electrical grids, water pipelines, and road networks the same way. Clustering algorithms in machine learning (single-linkage clustering) are built directly on MSTs. Image segmentation, circuit design, and even approximation algorithms for the traveling salesman problem all lean on MST construction. Any time you need to connect a set of points as cheaply as possible without redundancy, you're building a minimum spanning tree.

Problem Statement

You are given a connected, undirected, weighted graph with n nodes labeled 0 to n - 1. Each edge is [u, v, weight].

Find the minimum spanning tree (MST): a subset of edges that connects all nodes, contains no cycles, and has the minimum possible total weight. Return the total weight of the MST.

Example:

n = 4, edges = [[0,1,1],[0,2,4],[1,2,2],[1,3,5],[2,3,3]]

result → 6 (the MST uses edges of weight 1, 2, and 3).

1. Clarify Requirements Before Jumping Into Code

Before writing a single line, we should restate the problem in our own words and ask the kinds of questions that would change our approach.

Input: the number of nodes n and a list of weighted undirected edges.

Output: the total weight of the minimum spanning tree.

Details to clarify:

Is the graph connected? Yes — which guarantees an MST exists. (A disconnected graph has no spanning tree at all.)
Is it undirected? Yes — edges work in both directions.
Can edge weights be negative? The problem says weights are non-negative, but worth noting: Kruskal's actually works fine with negative weights too, since it only compares weights relative to each other.
Can there be multiple edges between the same pair of nodes, or equal weights? Yes to both — the algorithm handles them naturally.
Do we return the edge set or just the total weight? Just the total weight here.

The thing to flag is the structure of an MST: it connects all n nodes using exactly n - 1 edges with no cycles. That n - 1 edge count is the same tree invariant we've seen before — a spanning tree is a tree, so it has exactly n - 1 edges. Knowing we'll stop once we've added n - 1 edges gives us a clean termination condition.

2. Identify the Category of the Question

A few signals jump out:

We have a weighted undirected graph.
We want to select a subset of edges minimizing total weight.
The selected edges must form a tree (connected, acyclic).

That combination — minimum-weight edge subset forming a spanning tree — is the definition of a minimum spanning tree problem. There are two classic algorithms: Kruskal's (sort all edges, greedily add the cheapest that doesn't form a cycle) and Prim's (grow the tree outward from a starting node, always adding the cheapest edge leaving the current tree). We'll focus on Kruskal's because it's the most natural fit for the greedy framing and showcases Union-Find, which is what this kind of problem typically tests. Same Union-Find machinery as Graph Valid Tree and the dynamic-connectivity follow-up to Number of Islands.

3. Brute Force Solution

Let's think about the naive approach to understand the problem. By definition, an MST is a subset of n - 1 edges forming a tree with minimum total weight. So the brute force is: enumerate every subset of n - 1 edges, check which ones form a valid spanning tree (connected, acyclic, touching all nodes), and keep the cheapest.

The number of ways to choose n - 1 edges from E edges is combinatorial — astronomically large for any real graph. Completely infeasible.

The brute force does crystallize the goal, though: we want to pick edges that are (a) as cheap as possible, (b) never form a cycle, and (c) end up connecting everything with exactly n - 1 edges. Those three requirements — cheapest, no cycles, n - 1 edges — are exactly what a smarter, greedy algorithm needs to satisfy. The question is whether we can satisfy them without searching all subsets.

4. Brainstorm More Solutions

Step 1: Follow the greedy instinct

The most natural idea for "minimize total weight" is greedy: build the tree up by repeatedly grabbing the cheapest edge available. If we want the total to be small, surely we should prefer cheap edges over expensive ones.

But greedy strategies are dangerous — they're often almost right but fail on edge cases. So let's pin down exactly what could go wrong with "just keep adding the cheapest edge." The obvious failure: if we blindly add the cheapest edges, we might add an edge between two nodes that are already connected through edges we picked earlier. That edge would create a cycle and add weight without connecting anything new — pure waste.

So the greedy instinct needs one guardrail: add the cheapest edge that doesn't create a cycle. Take cheap edges, but skip any that would connect two nodes already linked. That refinement turns a naive greedy into a correct one.

Step 2: Get the edges in cheapest-first order

To "always take the cheapest available edge," we need to consider edges in order of increasing weight. The simplest way to guarantee that is to sort all edges by weight ascending up front. Then we just walk the sorted list from cheapest to most expensive, considering each edge in turn.

Sorting once at the start is cleaner than repeatedly searching for the minimum, and it costs O(E log E) — which, as we'll see, dominates the algorithm's runtime.

Step 3: Detect cycles efficiently with Union-Find

Now the crux: as we walk the sorted edges, for each edge (u, v) we need to ask, "are u and v already connected by the edges I've picked so far?" If yes, adding this edge would form a cycle — so we skip it. If no, the edge links two previously-separate pieces — and we add it.

How do we answer "are these two nodes already connected?" efficiently, as the set of picked edges grows? This is exactly the problem Union-Find (Disjoint Set Union) solves.

Think of each connected group of nodes as a set. Union-Find supports two operations:

find(x): which set does node x belong to?
union(x, y): merge the sets containing x and y.

So the cycle test becomes: find(u) == find(v)? If they're in the same set, they're already connected — adding this edge makes a cycle, so skip it. Otherwise, add the edge and union(u, v) to record that these two groups are now one.

This is a perfect fit because building an MST is fundamentally about progressively merging groups of nodes into one connected whole — which is precisely what Union-Find tracks. Each edge we add merges two groups; each edge we skip would have been redundant within a group.

Step 4: Assemble Kruskal's algorithm

Putting the pieces together:

Sort all edges by weight ascending.
Initialize Union-Find with each node in its own set.
Walk the sorted edges. For each (u, v, w): if find(u) != find(v), add the edge (add w to the total) and union(u, v).
Stop once we've added n - 1 edges — the tree is complete.

This is Kruskal's algorithm. It satisfies all three brute-force requirements: cheapest-first (the sort), no cycles (the Union-Find check), and exactly n - 1 edges (the stopping condition).

Step 5: Why is greedy correct here?

It's worth pausing on why this greedy strategy actually produces the optimal MST, not just a valid spanning tree — because "greedy gives the optimum" is rare and deserves justification. Interviewers often ask exactly this.

The justification is the cut property: for any way of splitting the nodes into two groups (a "cut"), the cheapest edge crossing that split is always safe to include in some MST. Here's the intuition. Suppose the cheapest edge crossing a cut were not in the MST. Then the MST must cross that cut using some other, more expensive edge (it has to cross somehow, to stay connected). Swap that expensive crossing edge for the cheapest one — the tree stays connected and acyclic, but its total weight goes down. That contradicts it being minimum. So the cheapest crossing edge must be safe.

Kruskal's exploits this repeatedly. Every time it adds the cheapest edge connecting two separate groups, that edge is the cheapest one crossing the cut between "these two groups" and "everything else." By the cut property, it's always a safe, optimal choice. Stack up those locally-safe choices and you get a globally optimal tree. That's why the greedy works — it's not luck, it's the cut property applied at every step.

Step 6: Walk through the example

Let's trace n = 4, edges = [[0,1,1],[0,2,4],[1,2,2],[1,3,5],[2,3,3]].

Sort by weight: [0,1,1], [1,2,2], [2,3,3], [0,2,4], [1,3,5].

Initialize: each node {0}, {1}, {2}, {3} in its own set. Total = 0, edges used = 0.

Edge (0,1,1): find(0) != find(1) → add. Union {0,1}. Total = 1, used = 1.
Edge (1,2,2): find(1) != find(2) → add. Union {0,1,2}. Total = 3, used = 2.
Edge (2,3,3): find(2) != find(3) → add. Union {0,1,2,3}. Total = 6, used = 3.
Used == n - 1 == 3. Stop.

Total weight: 6. Correct. (We never even looked at edges (0,2,4) and (1,3,5) — the stopping condition cut us off, and both would have formed cycles anyway.)

Step 7: Complexity

Let E be the number of edges and V = n the number of nodes.

Sorting the edges is O(E log E) — this is the dominant cost. Initializing Union-Find is O(V). The main loop processes each edge once, performing a find and possibly a union; with path compression and union by rank, each of these is O(α(V)) amortized, where α is the inverse Ackermann function — effectively a small constant. So the loop is O(E α(V)), which is dwarfed by the sort.

Total time: O(E log E). Since E ≤ V², log E is O(log V), so this is sometimes written O(E log V) — they're equivalent.

Space is O(V) for the Union-Find arrays.

The transferable note: Kruskal's runtime is dominated by sorting the edges, not by the connectivity work. The Union-Find operations are nearly free, which is why sorting is the bottleneck.

5. Discuss Trade-Offs Between Solutions

Approach	Time	Space	When I'd use it
Brute-force edge subsets	Exponential	High	Never — combinatorial blowup
Prim's algorithm	O(E log V)	O(V)	Strong on dense graphs; grows one tree with a priority queue
Kruskal's algorithm	O(E log E)	O(V)	My default — simple, greedy, showcases Union-Find

Both Kruskal's and Prim's are optimal MST algorithms with the same asymptotic cost. Kruskal's is often cleaner to explain in an interview because the greedy logic ("sort edges, add the cheapest cycle-free one") is so direct, and it exercises Union-Find, which is a commonly-tested structure. Prim's can have an edge on very dense graphs with the right heap, but Kruskal's is the more natural teaching choice.

6. Pseudocode

sort edges by weight ascending
initialize Union-Find with each node in its own set
totalWeight = 0
edgesUsed = 0

for each edge (u, v, w) in sorted order:
    if find(u) != find(v):          # endpoints in different groups → no cycle
        union(u, v)
        totalWeight += w
        edgesUsed++
        if edgesUsed == n - 1:       # tree complete
            break

return totalWeight

7. Edge Cases

Things to verify before claiming we're done:

Single-node graph (n = 1) → no edges needed; n - 1 = 0 edges, total weight 0. ✓
Graph with exactly n - 1 edges → it's already a tree; every edge gets added, total is the sum of all weights.
Multiple edges between the same pair → after the first connects them, the rest are detected as cycles (same set) and skipped.
Equal-weight edges → the sort breaks ties arbitrarily; any valid ordering still yields a correct (possibly different but equal-weight) MST.
Already-connected nodes encountered mid-run → the find(u) == find(v) check skips them cleanly.

The n - 1 stopping condition is a nice optimization: once the tree is complete, we can stop early without examining the remaining (more expensive) edges.

8. Write Full Code

import java.util.*;

public class MinimumSpanningTree {

    public static int kruskalMST(int n, int[][] edges) {
        // Sort edges cheapest-first — 
        // the heart of the greedy strategy
        Arrays.sort(edges, Comparator.comparingInt(a -> a[2]));

        UnionFind uf = new UnionFind(n);
        int totalWeight = 0;
        int edgesUsed = 0;

        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];

            // Add the edge only if its endpoints are in different 
            // groups, i.e. it doesn't create a cycle
            if (uf.find(u) != uf.find(v)) {
                uf.union(u, v);
                totalWeight += w;
                edgesUsed++;

                // A spanning tree has exactly n - 1 edges — 
                // stop once complete
                if (edgesUsed == n - 1) {
                    break;
                }
            }
        }

        return totalWeight;
    }

    static class UnionFind {
        int[] parent;
        int[] rank;

        UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;   // each node starts in its own set
            }
        }

        // Find with path compression: flattens the tree for 
        // fast future lookups
        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }

        // Union by rank: attach the shorter tree under 
        // the taller one
        void union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);
            if (rootX == rootY) return;

            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
}

9. Test the Code

int[][] edges = {
    {0, 1, 1},
    {0, 2, 4},
    {1, 2, 2},
    {1, 3, 5},
    {2, 3, 3}
};
System.out.println(kruskalMST(4, edges));   // 6 (edges of weight 1 + 2 + 3)

// Single node — no edges needed
System.out.println(kruskalMST(1, new int[][]{}));   // 0

// Already a tree (n - 1 edges, no choices) — sum of all weights
int[][] tree = {{0,1,5},{1,2,3},{2,3,2}};
System.out.println(kruskalMST(4, tree));   // 10

// Multiple edges between the same pair — cheaper one wins, dup is skipped
int[][] multi = {{0,1,10},{0,1,1},{1,2,2}};
System.out.println(kruskalMST(3, multi));   // 3 (uses the weight-1 and weight-2 edges)

// Equal weights — ties broken arbitrarily, still a valid MST
int[][] ties = {{0,1,1},{1,2,1},{0,2,1}};
System.out.println(kruskalMST(3, ties));   // 2 (any two of the three weight-1 edges)

These hit the meaningful cases: the canonical example, a single-node graph, a graph that's already a tree, multiple edges between the same pair (where the cheaper one is chosen and the duplicate is skipped as a cycle), and equal-weight edges (where ties don't affect the total).

10. Key Lessons

A spanning tree connects all n nodes with exactly n - 1 edges and no cycles. That n - 1 invariant gives you a clean stopping condition: once you've added n - 1 edges, you're done.
The greedy "always take the cheapest cycle-free edge" strategy isn't just intuitive — it's provably optimal, by the cut property. The cheapest edge crossing any cut is always safe to include, because swapping in a cheaper crossing edge could only lower the total. Be ready to explain why greedy works, not just that it does.
Union-Find is the natural tool whenever a problem is about progressively merging groups and detecting whether two elements are already connected. Building an MST is exactly that — each added edge merges two groups, each skipped edge is a within-group redundancy.
Kruskal's runtime is dominated by sorting the edges (O(E log E)), not the connectivity work — the Union-Find operations are nearly constant. When analyzing such algorithms, find the dominant step rather than summing everything blindly.
When a greedy approach feels right, stress-test it for the failure mode before trusting it. Here, naive greedy fails by creating cycles; adding the single cycle-check guardrail fixes it. The discipline of asking "what's the simplest case that breaks this?" turns a risky greedy into a correct one.

The thing that makes Minimum Spanning Tree click is understanding why the greedy choice is safe (the cut property) and recognizing that progressively merging connected groups is precisely what Union-Find is built for. Once you see MST construction as "repeatedly merge the two cheapest-to-connect groups until everything is one," the algorithm stops being a memorized procedure and becomes an obvious consequence of how trees and greedy choices interact.

Good Luck and Happy Coding!