vault

Kruskal's Algorithm

10 min read

Kruskal’s Algorithm

Kruskal’s algorithm computes a minimum spanning tree (MST) of a connected, undirected, weighted graph in O(E log E) time. The strategy is brutally simple: sort all edges by weight; greedily add the cheapest edge that doesn’t form a cycle, until you have V-1 edges. Cycle detection is done with Union-Find in essentially constant time per check, so the bottleneck is the initial sort. Kruskal’s is the canonical example of a provably optimal greedy algorithm — and a frequent interview question because it elegantly combines two foundational tools (sorting + DSU).

1. Intuition — Cheapest Roads First

Imagine you’re a town planner connecting V villages with paved roads. You have a list of every possible road and its cost. You need to make sure every village is reachable, while spending as little as possible.

Kruskal’s strategy:

  • Sort all candidate roads from cheapest to most expensive.
  • For each road in order:
    • If building it would connect two villages that are not yet connected (directly or via existing roads), build it.
    • If both villages are already connected (perhaps via a longer chain), skip this road — it would form a redundant cycle.
  • Stop when every village is connected (you’ve built exactly V-1 roads).

The result is the minimum spanning tree: a subset of edges that connects all vertices, has no cycles (it’s a tree), and has minimum total weight.

The “is it already connected?” check uses Union-Find — exactly the data structure designed for this question.

2. Tiny Worked Example

Graph (undirected, weighted):

       1
   A ──── B
   │ \    │
  4│ 2\  3│
   │   \  │
   D ──── C
       5

Edges: A-B(1), A-C(2), A-D(4), B-C(3), C-D(5).

Sort by weight: A-B(1), A-C(2), B-C(3), A-D(4), C-D(5).

Process:

  1. A-B (weight 1): A and B are in different components. Add. Components: {A,B}, {C}, {D}.
  2. A-C (weight 2): A and C are in different components. Add. Components: {A,B,C}, {D}.
  3. B-C (weight 3): B and C are in the same component (both in {A,B,C}). Skip — would create cycle A-B-C-A.
  4. A-D (weight 4): A and D are in different components. Add. Components: {A,B,C,D}. Done (V-1 = 3 edges).
  5. (We don’t even examine C-D.)

MST edges: A-B, A-C, A-D. Total weight: 1 + 2 + 4 = 7.

Every other spanning tree (e.g., A-B, A-C, C-D = 1+2+5 = 8, or A-B, B-C, A-D = 1+3+4 = 8) is more expensive. Kruskal’s found the optimum.

3. Pseudocode

kruskal(num_vertices, edges):
    sort edges by weight ascending
    uf := UnionFind(num_vertices)
    mst := empty list
    total_weight := 0
    for each (u, v, w) in sorted edges:
        if uf.union(u, v):                     # returns True iff actually merged
            mst.append((u, v, w))
            total_weight += w
            if length(mst) == num_vertices - 1:
                break                          # optimization: done
    if length(mst) < num_vertices - 1:
        return None                            # graph is disconnected — no MST exists
    return mst, total_weight

4. Python Implementation

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
 
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path halving
            x = self.parent[x]
        return x
 
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False
        if self.size[rx] < self.size[ry]: rx, ry = ry, rx
        self.parent[ry] = rx
        self.size[rx] += self.size[ry]
        return True
 
 
def kruskal(num_vertices, edges):
    """edges: list of (u, v, w) tuples (undirected, weighted)."""
    edges_sorted = sorted(edges, key=lambda e: e[2])
    uf = UnionFind(num_vertices)
    mst = []
    total = 0
    for u, v, w in edges_sorted:
        if uf.union(u, v):
            mst.append((u, v, w))
            total += w
            if len(mst) == num_vertices - 1:
                break
    if len(mst) < num_vertices - 1:
        return None                            # disconnected
    return mst, total

5. Why It Works (Cut Property + Exchange Argument)

The proof of correctness uses the cut property of MSTs:

Cut property: For any partition (cut) of the vertices into two non-empty sets, the lightest edge crossing the cut is in some MST.

Proof of cut property (exchange argument). Suppose e is the lightest edge across some cut, and suppose for contradiction that no MST contains e. Take any MST T; adding e creates a cycle (since T is connected). The cycle must cross the cut at least one other time — call that crossing edge f. Since e is the lightest edge crossing the cut, weight(e) ≤ weight(f). Remove f from T ∪ {e} to get a new spanning tree T' with weight(T') ≤ weight(T). So T' is also an MST — and it contains e. Contradiction.

Why Kruskal’s algorithm is correct: every edge it adds is the lightest edge crossing the cut between its current component and the rest of the graph (because we examine edges in weight order, and we only add an edge if its endpoints are in different components). By the cut property, every edge Kruskal adds is in some MST. So the final tree is an MST.

The proof is a model of clarity — it’s the kind of argument interviewers love asking candidates to reproduce.

6. Complexity

StepCost
Sort edgesO(E log E)
Initialize Union-FindO(V)
E iterations of union/findO(E · α(V)) ≈ O(E)
TotalO(E log E) = O(E log V)

Note: log E ≤ log V² = 2 log V, so O(E log E) = O(E log V). The two are interchangeable.

The sort dominates. If edges are pre-sorted (or come from a structure that allows linear-time sorting like radix sort on integer weights), Kruskal becomes essentially O(E α(V)).

Space: O(V) for the Union-Find structure, O(E) for the edge list (if not in place).

7. Comparison with Prim’s Algorithm

The other classic MST algorithm is Prim’s Algorithm: start from any vertex; repeatedly add the cheapest edge from the current MST to a vertex not yet in the MST.

PropertyKruskalPrim
ApproachEdge-centric (sort, scan)Vertex-centric (heap-based grow)
Data structureUnion-Find + sortMin-heap
Time (binary heap Prim)O(E log V)O((V+E) log V)
Time (Fibonacci heap Prim)n/aO(E + V log V)
Time (matrix Prim)n/aO(V²) — best for dense graphs
Best forSparse graphs, when Union-Find is naturalDense graphs, single-source-style growth
Disconnected graphsReturns minimum spanning forest naturallyStops at the first component

For most interview problems, Kruskal is the cleaner code: sort + DSU + 5 lines. Prim is preferred for very dense graphs (E ≈ V²) because the matrix variant is O(V²) vs Kruskal’s O(V² log V).

8. Variants

8.1 Maximum Spanning Tree

Sort edges in descending order. Same algorithm otherwise. Useful when “weight” is something we want to maximize (reliability, throughput).

8.2 Minimum Spanning Forest

If the graph is disconnected, Kruskal’s natural output is the minimum spanning forest — one MST per connected component. Just don’t stop at V-1 edges; let the loop finish.

8.3 Second-Best MST

The MST whose total weight is the smallest strictly greater than the MST’s. Algorithm: build MST; for each non-MST edge e, find the heaviest edge on the cycle it creates, swap them, take the minimum total. O(VE) straightforward; O(E log V) with care.

8.4 Bottleneck Spanning Tree

A spanning tree minimizing the maximum edge weight (rather than sum). It turns out: every MST is also a bottleneck ST. Specialized linear-time algorithms exist (Camerini’s), but for interview purposes, just compute the MST.

8.5 Constrained MST

E.g., “MST with at most k red edges.” Significantly harder; usually requires Lagrangian relaxation or specialized algorithms. Beyond standard interview scope.

9. Use Cases

9.1 Network Design

Lay cable, road, water pipe, fiber to connect a set of locations at minimum total cost. The original motivating application.

9.2 Clustering (Single-Linkage)

Build the MST of the data-point graph (distances as edge weights). Removing the k-1 heaviest MST edges produces k clusters with the property that within-cluster distances are all smaller than between-cluster distances. Equivalent to single-linkage hierarchical clustering. Used in image segmentation, anomaly detection, and recommender systems.

9.3 Approximation Algorithms

The MST is the basis of approximation algorithms for Travelling Salesman (the Christofides-Serdyukov algorithm has a 3/2-approximation guarantee and starts with the MST).

9.4 Boruvka Step in Parallel MST

Boruvka’s algorithm uses a parallel-friendly variation: each component finds its cheapest outgoing edge in parallel, then all are added at once. Used in distributed/parallel implementations.

10. Common Interview Problems

ProblemPattern
LC 1584 — Min Cost to Connect All PointsKruskal on Manhattan-distance complete graph
LC 1135 — Connecting Cities With Minimum CostPlain MST
LC 1168 — Optimize Water Distribution in a VillageAdd virtual source for “well” costs, then MST
LC 1489 — Find Critical and Pseudo-Critical Edges in MSTMST with edge ablation
Network reliability / minimum cost backboneDirect MST application

11. Pitfalls

11.1 Forgetting to Sort

Kruskal must process edges in weight order. Forgetting sorted(...) produces a spanning tree (since DSU still prevents cycles), but it’s not the minimum.

11.2 Not Checking for Disconnected Graph

If the graph is disconnected, Kruskal terminates with fewer than V-1 edges. Always check this case; some problems require returning -1, others want the spanning forest.

11.3 Bad DSU Implementation

Without path compression + union by rank/size, your Union-Find ops are O(log V) (or worse), pushing total time to O(E log V · log V). Use the proper DSU.

11.4 Counting Edges vs Vertices

The MST has exactly V-1 edges (not V). Off-by-one when checking the early-termination condition is a common bug.

11.5 Including Self-Loops

Edges from a vertex to itself (u == v) are useless in MST — union(u, u) returns False, no harm done. But if your input has many self-loops, the sort wastes time. Filter them out first.

11.6 Multi-Edges

If multiple edges exist between the same pair, Kruskal naturally takes only the cheapest (the first one sorted). No special handling needed.

11.7 Using Kruskal When Prim Is Better

For dense graphs (E ≈ V²), the O(E log V) of Kruskal might be worse than the O(V²) of matrix-Prim. Estimate before committing.

12. Diagram — Kruskal’s Greedy March

flowchart LR
  S0[Sort edges by weight] --> P1[Pick cheapest edge]
  P1 --> Q{Endpoints in same component?}
  Q -- yes --> Skip[Skip → cycle]
  Q -- no --> Add[Add to MST<br/>union endpoints]
  Skip --> Next[Next edge]
  Add --> Check{V-1 edges yet?}
  Check -- yes --> Done[MST complete]
  Check -- no --> Next
  Next --> Q

What this diagram shows. The control flow: sort once, then iterate edges in order, using Union-Find as the “is this a cycle?” oracle. Each edge is either added (decreasing component count) or skipped (would close a cycle). The algorithm halts the moment we have V-1 edges (the count needed for a spanning tree on V vertices).

13. Why This Greedy Algorithm Works (And Most Don’t)

Most “greedy” algorithms fail — local optimality doesn’t imply global optimality. Kruskal works because of a deep structural property of MST: the matroid structure. The set of forests on a graph forms a matroid; matroid theory tells us that the greedy algorithm produces an optimal solution iff the structure is a matroid. MSTs are the canonical matroid example.

You don’t need matroid theory for interviews — but if pressed on “why does this greedy work?” the answer is “the MST problem has the matroid optimality property; the cut-property proof above shows it concretely.” This level of depth distinguishes a senior candidate.

14. Open Questions

  • Is there a sub-O(E log V) MST? Yes — Karger’s randomized algorithm gives expected O(E). Chazelle (2000) gave deterministic O(E α(V)). Both are theoretical; not used in practice.
  • Boruvka vs Kruskal vs Prim — which is “the right one”? Depends on graph density and parallelism. For the typical interview, Kruskal wins on simplicity.

15. See Also

Graph View

Backlinks