Kruskal's Algorithm
Build MST by greedily adding cheapest edges that don't form cycles.
How it works
Kruskal's algorithm finds a Minimum Spanning Tree (MST) of a connected, undirected, weighted graph — the subset of edges that connects all vertices with the lowest possible total weight and no cycles.
The algorithm is purely greedy: sort all edges by weight, then iterate through them. For each edge (u, v), add it to the MST if u and v are not already connected; otherwise skip it. The Union-Find (disjoint-set) data structure makes "are u and v connected?" queries and the subsequent merge nearly O(1) (amortised O(α(n)) with path compression and union by rank).
Because edges are processed in non-decreasing weight order, the first time two components are bridged, the cheapest possible bridge is used — the classic greedy exchange argument proves this is always optimal. The algorithm stops as soon as n−1 edges have been added (a spanning tree on n nodes has exactly n−1 edges).
Compared to Prim's algorithm, Kruskal is generally preferred for sparse graphs where E is much smaller than V², because sorting dominates at O(E log E), whereas Prim with a binary heap runs in O((V + E) log V). For dense graphs, Prim with an adjacency matrix can be faster.
Complexity
Visualizer
Where it's used in the real world
Network infrastructure design
Laying the minimum length of cable to connect all offices or data centersPhysical network design is an MST problem: each potential link has a cost (cable length, leased-line price) and the goal is full connectivity at minimum total cost. Kruskal is natural here because the edge list is sparse and can be sorted offline.
Cluster analysis (single-linkage hierarchical clustering)
Building dendrograms and cutting them at a threshold to form clustersSingle-linkage clustering is equivalent to building an MST on the distance matrix and cutting edges above a threshold. Kruskal's sorted-edge pass computes this MST in O(E log E), enabling efficient hierarchical clustering of large point sets.
Power grid and circuit board routing
Connecting components or substations with minimum total wire lengthBoth problems reduce to finding an MST on a complete graph whose edge weights are Euclidean distances. Kruskal with a pre-sorted edge list (or computed only for nearby pairs via Delaunay triangulation) is the standard baseline approach.
Implementation
// Union-Find helpers
function makeUF(n: number) {
return { parent: Array.from({length: n}, (_, i) => i), rank: new Array(n).fill(0) };
}
function find(uf: {parent: number[]}, x: number): number {
while (uf.parent[x] !== x) { uf.parent[x] = uf.parent[uf.parent[x]]; x = uf.parent[x]; }
return x;
}
function union(uf: {parent: number[]; rank: number[]}, a: number, b: number): boolean {
const ra = find(uf, a), rb = find(uf, b);
if (ra === rb) return false;
if (uf.rank[ra] < uf.rank[rb]) uf.parent[ra] = rb;
else if (uf.rank[ra] > uf.rank[rb]) uf.parent[rb] = ra;
else { uf.parent[rb] = ra; uf.rank[ra]++; }
return true;
}
function kruskal(
n: number,
edges: {from: number; to: number; weight: number}[]
): {edges: typeof edges; totalWeight: number} {
const sorted = [...edges].sort((a, b) => a.weight - b.weight);
const uf = makeUF(n);
const mst: typeof edges = [];
let totalWeight = 0;
for (const e of sorted) {
if (union(uf, e.from, e.to)) {
mst.push(e);
totalWeight += e.weight;
if (mst.length === n - 1) break;
}
}
return { edges: mst, totalWeight };
}