Kruskal's algorithm - DSA Learning Guide

Overview

Kruskal's algorithm builds a minimum spanning tree (MST): a set of V - 1 edges that connects all vertices with the smallest possible total weight and no cycles. It sorts all edges by weight and adds them cheapest first, skipping any edge whose endpoints are already connected.

Union Find makes the 'already connected?' check nearly O(1), so the total cost is dominated by sorting: O(E log E). The greedy choice is correct because of the cut property: the cheapest edge crossing any partition of the vertices always belongs to some MST.

Building the cheapest road network

A government lists every possible road with its cost and builds the cheapest one first, then the next cheapest, but never builds a road between two towns already connected through existing roads, because that would be wasted money.

When to use it

Connect all points, cities, or computers with minimum total cost.
Edges are given as a list (or are easy to generate) and the graph is sparse.
You need to know which edges are critical or pseudo-critical to the MST.
Clustering: stop early to leave k components.

Problem patterns it solves

Minimum cost to connect everything

Recognize it when: connect all points / cities with minimal total cost.

1584. Min Cost to Connect All Points
1135. Connecting Cities With Minimum Cost
1168. Optimize Water Distribution in a Village

Critical edges

Recognize it when: edges whose removal increases MST cost.

1489. Find Critical and Pseudo-Critical Edges in MST

Clustering by stopping early

Recognize it when: group points into k clusters maximizing spacing.

Maximum spacing k-clustering

Where it is used in real software

Network design

Laying fiber, electrical grids, or water pipes to connect all locations with minimum cable length.

Clustering

Single-linkage hierarchical clustering is equivalent to running Kruskal and stopping at k components.

Image segmentation

Felzenszwalb's graph-based segmentation merges pixel regions in Kruskal order of edge weights.

Key terms

Spanning tree: A subset of edges connecting all V vertices with exactly V - 1 edges and no cycle.
MST: The spanning tree with minimum total weight.
Cut property: The lightest edge crossing any cut belongs to an MST.
Cycle property: The heaviest edge on any cycle is not needed in the MST.

How it works, step by step

1
Sort edges by weight
Ascending order.
2
Initialize Union Find
Each vertex starts in its own component.
3
Scan edges
If union(u, v) succeeds (different components), add the edge and its weight.
4
Skip edges inside a component
They would create a cycle.
5
Stop at V - 1 edges
If fewer are added after all edges, the graph is disconnected.

MST of 4 nodes

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

Edge (sorted)	Weight	Same component?	Action	Total
A-B	1	no	add	1
C-D	2	no	add	3
A-C	3	no	add (joins {A,B} and {C,D})	6
B-C	4	yes	skip (cycle)	6
B-D	5	yes	skip (cycle)	6

NOWEdge (sorted): A-B | Weight: 1 | Same component?: no | Action: add | Total: 1

MST weight 6 with edges A-B, C-D, A-C: exactly V - 1 = 3 edges. The algorithm could stop as soon as the third edge was added.

Implementation

1// Uses the UnionFind class from the Union Find guide2function kruskal(n, edges) {3  const sorted = [...edges].sort((a, b) => a[2] - b[2]);4  const uf = new UnionFind(n);5  let total = 0;6  const used = [];7  for (const [u, v, w] of sorted) {8    if (uf.union(u, v)) {9      total += w;10      used.push([u, v, w]);11      if (used.length === n - 1) break;12    }13  }14  return used.length === n - 1 ? { total, used } : null; // null: disconnected15}16 17// 1584. Min Cost to Connect All Points (Manhattan distance)18function minCostConnectPoints(points) {19  const edges = [];20  for (let i = 0; i < points.length; i++) {21    for (let j = i + 1; j < points.length; j++) {22      const d = Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]);23      edges.push([i, j, d]);24    }25  }26  return kruskal(points.length, edges).total;27}

Complexity and performance

TimeO(E log E)

Sorting dominates; DSU is near O(1).

SpaceO(V + E)

Edges plus DSU.

Complete graphO(V^2 log V)

All pairs as edges; Prim may be better.

Trade-offs

Kruskal vs Prim

Kruskal is natural for edge lists and sparse graphs. Prim is better for dense graphs or adjacency matrices, and can be O(V^2) without a heap.

Uniqueness

If all weights are distinct, the MST is unique. With ties, several MSTs may have the same total.

Variants and related techniques

Virtual node trick

Model 'build a well here' as an edge to a virtual source node.

Maximum spanning tree

Sort in descending order.

Critical edge test

Remove an edge and recompute; if the cost grows, it is critical. Force-include it to test pseudo-critical.

Common mistakes

Skipping the disconnected-graph check.
Fix: If fewer than V - 1 edges were added, no spanning tree exists.
Using a MST for shortest paths.
Fix: An MST minimizes total edge weight, not the distance between two specific nodes.

Interview questions

Why is Kruskal's greedy choice correct?

By the cut property, the cheapest edge connecting two different components is always safe to add: some MST contains it. Kruskal only ever adds such edges.

Is the MST the same as shortest paths?

No. The MST minimizes the sum of all chosen edges; the path between two nodes inside the MST may be longer than their shortest path.

Practice problems

Problem	Difficulty	What it trains
1584. Min Cost to Connect All Points	Medium	Generate edges then Kruskal.
1135. Connecting Cities With Minimum Cost	Medium	Disconnected check.
1168. Optimize Water Distribution in a Village	Hard	Virtual node.
1489. Find Critical and Pseudo-Critical Edges	Hard	Repeated MST runs.