Graph AlgosAlgorithmaka MST by sorting edges, union-find MST

Kruskal's Algorithm

Minimum spanning tree by sorting all edges and greedily adding each edge that joins two different components, tracked with union-find.

▶ VisualizePattern: Union-FindPractice (3)
Progress

Overview

Kruskal's algorithm builds a minimum spanning tree edge-by-edge in global weight order: sort every edge, walk through them from lightest to heaviest, and keep an edge iff its endpoints are currently in different components. A Union-Find (Disjoint Set Union) structure answers "same component?" and merges components in near-constant amortised time, so the whole algorithm is dominated by the sort: O(E log E) = O(E log V).

Where Prim's Algorithm grows a single tree from a seed, Kruskal grows a forest of many small trees that merge. That makes it the natural choice for sparse graphs given as an Edge List, for problems that want a spanning forest of a disconnected graph, and for any question phrased as "process edges by weight and track connectivity" (bottleneck paths, threshold connectivity, clustering).

minimum spanning treeMSTgreedyunion-findsortingsparse graphscut property

Intuition

A mental model before the formal terms.

Spread all the cables on a table sorted by price. Pick up the cheapest; if it connects two islands that are not yet connected (by any chain of cables you already chose), keep it, otherwise it would only create a loop — throw it away. Keep going until every island is connected. You never need to know *where* the tree is growing, only *which islands are already joined*, and that is exactly what union-find remembers.

How it works

  1. Sort the edges by weight, ascending: O(E log E).
  2. Initialise union-find with each node in its own set.
  3. For each edge (u, v, w) in sorted order: if find(u) ≠ find(v), add the edge to the MST and union(u, v). Otherwise skip — it would close a cycle.
  4. Stop early once V - 1 edges are chosen. If the loop ends with fewer, the graph is disconnected and you have a minimum spanning forest.
  5. Union by rank/size plus path compression makes each find/union O(α(V)) ≈ constant, so the loop is O(E · α(V)).

Why it works

Cut property applied at each accepted edge: when (u, v) is accepted, consider the cut S = component of u, V \ S = the rest. Every other crossing edge is heavier or equal (edges are processed in sorted order and lighter crossing edges would already have merged the sides). So (u, v) is a lightest crossing edge and belongs to some MST containing the edges chosen so far.

Cycle property for rejected edges: a rejected edge is the heaviest on the cycle it would close (all cycle edges accepted earlier are lighter or equal), and the heaviest edge on a cycle is never needed in an MST.

Since every accepted edge is safe and every rejected edge is unnecessary, the final V - 1 edges form an MST. Correctness of union-find guarantees no cycles are ever created.

Recognition

How to tell a problem wants this.

  • "Minimum cost to connect everything" with the input already given as a list of weighted edges.
  • Sparse graphs: E close to V — sorting E edges is cheap.
  • Questions about when two nodes become connected as edges are added in weight order (minimum bottleneck, "smallest threshold so that all queries are connected").
  • You need the MST of a possibly disconnected graph (spanning forest) or want to count components as a by-product.
“connected groups” → Union-Find“maximum number of non-overlapping” → Greedy

Interactive visualization

Play, step, change the input. ← → and space work too.

42518103263ABCDEFG
Edges by weight
B–G (1)A–C (2)G–E (2)E–F (3)G–D (3)A–B (4)B–D (5)D–F (6)C–G (8)C–E (10)
DSU parent
nodeparentroot
AAA
BBB
CCC
DDD
EEE
FFF
GGG
1/15Sort the 10 edges by weight and put each node in its own set. Kruskal grows a forest by taking the cheapest edge that joins two different trees.
Edge under considerationAccepted (MST)Rejected (cycle)Node in some tree
PseudocodeLearn Kruskal's Algorithm →
1sort edges by weight ascending
2make_set(v) for every node
3for (u, v, w) in edges:
4  if find(u) != find(v):
5    union(u, v); mst.add((u, v, w))
6  else: skip — u and v already connected, edge would close a cycle
7return mst
Complexity
best O(E log E)
avg O(E log E)
worst O(E log E)
space O(V + E)
Speed

Pseudocode

1sort edges by weight ascending
2uf = UnionFind(n); mst = []; total = 0
3for (u, v, w) in edges:
4  if uf.find(u) != uf.find(v):
5    uf.union(u, v); mst.append((u, v, w)); total += w
6    if len(mst) == n - 1: break
7return total, mst

Implementations

1from typing import NamedTuple
2 
3 
4class WEdge(NamedTuple):
5    w: float
6    u: int
7    v: int
8 
9 
10class DSU:
11    """Disjoint-set with union by size and path halving."""
12 
131 · Disjoint-set with union by size and path halving
14    def __init__(self, n: int) -> None:
15        self.parent = list(range(n))
16        self.size = [1] * n
17 
18    def find(self, x: int) -> int:
19        while self.parent[x] != x:
20            self.parent[x] = self.parent[self.parent[x]]  # path halving
21            x = self.parent[x]
22        return x
23 
24    def unite(self, a: int, b: int) -> bool:
25        a, b = self.find(a), self.find(b)
26        if a == b:
27            return False  # already connected: accepting would close a cycle
28        if self.size[a] < self.size[b]:
29            a, b = b, a
30        self.parent[b] = a
31        self.size[a] += self.size[b]
32        return True
33 
34 
352 · Sort edges by weight; the greedy scan then never needs to reconsider
36def kruskal(n: int, edges: list[WEdge]) -> tuple[float, list[WEdge]]:
37    ordered = sorted(edges, key=lambda e: e.w)
38 
39    dsu = DSU(n)
40    chosen: list[WEdge] = []
41    total: float = 0
42 
433 · Accept an edge only when it joins two different components
44    for e in ordered:
45        if dsu.unite(e.u, e.v):
46            chosen.append(e)
47            total += e.w
48            if len(chosen) == n - 1:
49                break  # tree complete
50 
514 · Fewer than n-1 accepted edges means the graph was disconnected
52    if len(chosen) != n - 1:
53        return -1, []
54    return total, chosen
55 
56 
575 · Stopping early is what makes the sort the dominant cost, not the scan
58def mst_weight(n: int, edges: list[WEdge]) -> float:
59    return kruskal(n, edges)[0]
Walkthrough
  1. list(range(n)) is the identity parent list, and [1] * n the initial sizes.
  2. a, b = self.find(a), self.find(b) resolves both roots in one tuple assignment.
  3. sorted(edges, key=lambda e: e.w) returns a new list, so the caller list is untouched — the opposite default from list.sort().
  4. WEdge(NamedTuple) gives an immutable record with named fields; because it is also a tuple, sorted(edges) without a key would order by (w, u, v), which happens to be correct here but is worth being explicit about.
  5. The len(chosen) == n - 1 early break stops the scan once the tree is complete.
Complexity (this implementation)
time O(E log E) dominated by the sort; the DSU scan is effectively linear · space O(V) for the DSU plus O(E) for the sorted copy

sorted runs TimSort in C, so on large edge lists the Python version is far closer to C++ than the union-find loop alone would suggest.

Language notes
  • sorted() returns a new list while list.sort() sorts in place — choosing the former is what keeps this function free of side effects.
  • key= evaluates the projection once per element, unlike a comparator, and operator.attrgetter("w") is marginally faster than the lambda.
  • NamedTuple fields are immutable; e._replace(w=...) produces a modified copy if needed.
  • networkx.minimum_spanning_edges(G, algorithm="kruskal") is the library version, and scipy.sparse.csgraph.minimum_spanning_tree works on a sparse matrix.
Common mistakes in this language
  • Using edges.sort(key=...) and mutating the callers list when sorted() was intended.
  • Writing find recursively and hitting RecursionError on a long parent chain.
  • Returning the total without checking len(chosen) == n - 1, so a disconnected graph reports a forest weight.
Language differences that matter here
  • Sorting API and defaults diverge sharply: Python sorted(key=...) returns a copy, C++ std::sort mutates and is unstable, and JS/TS sort mutates and — uniquely — is actively wrong without an explicit comparator because it stringifies.
  • Stability differs: Python and JS/TS sorts are stable, C++ std::sort is not, which can change *which* minimum spanning tree comes out when weights tie (never the total weight).
  • Immutable edge records come free in Python (NamedTuple); C++ uses a plain aggregate struct, TypeScript an interface plus readonly on the parameter, and JavaScript has no way to express it at all.
  • The recursive find is a genuine hazard only in Python (RecursionError near 1000 frames); the iterative path-halving loop used here sidesteps it in every language.

Complexity

Best
O(E log E)
Average
O(E log E)
Worst
O(E log E)
Space
O(V + E)

Sorting dominates; the union-find loop is O(E · α(V)), effectively linear. log E ≤ 2 log V so O(E log E) = O(E log V). If edges arrive pre-sorted or weights are small integers (counting sort), the whole algorithm is near-linear.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Sparse graphs (E is O(V) or O(V log V)) given as an edge list.
  • Disconnected graphs where a minimum spanning forest is acceptable or desired.
  • Connectivity-threshold questions: "smallest w such that s and t are connected using only edges ≤ w" — stop when find(s) == find(t).
  • Edges already sorted, or sortable in linear time — Kruskal becomes O(E α(V)).
  • Offline processing of edge additions in weight order (Kruskal reconstruction tree, single-linkage clustering).
Avoid it when
  • Dense graphs / complete graphs on points: E = V² edges must be materialised and sorted, O(V² log V); Prim's Algorithm with a matrix is O(V²).
  • Edges are only available through per-node adjacency queries — Prim's node-centric loop fits better.
  • Directed graphs — no MST; use a minimum arborescence algorithm.
  • Shortest paths — same warning as Prim: MST paths are not shortest paths.

Alternatives

Prim's AlgorithmUnion-Find (Disjoint Set Union)
Compare: Kruskal vs Prim

Common mistakes

  • Using union-find without rank/size or without path compression — find degrades to O(V) and the loop becomes O(E · V).
  • Comparing parent[u] == parent[v] instead of find(u) == find(v).
  • Forgetting to sort, or sorting descending (that gives a maximum spanning tree — sometimes wanted, e.g. maximum bottleneck).
  • Returning the MST weight for a disconnected graph without checking that V - 1 edges were chosen.
  • Materialising all O(V²) edges for a complete geometric graph when V is large — memory blows up; switch to Prim.

Interview patterns

  • Min cost to connect all points / connecting cities — the direct application.
  • Redundant connection: the first edge whose endpoints are already connected (Kruskal loop without sorting).
  • Minimum bottleneck / "path with minimum maximum edge": process edges by weight until s and t join.
  • Critical and pseudo-critical MST edges: rerun Kruskal excluding / forcing each edge.
  • Number of connected components after adding edges — union-find is the reusable half of Kruskal.
Interview questions on this
Mock interviews

Example problems

Number of Connected ComponentsmediumMin Cost to Connect All PointsmediumRedundant Connectionmedium