Home/Graphs/Kruskal
Search algorithmsCTRL K

Kruskal

· minimum spanning tree · lightest edges first
/graphs/kruskal
TREE EDGES
0/ 9
accepted so far
REJECTED
0
would close a cycle
TOTAL
0
weight of the tree
COMPONENTS
10
forests still apart
WEIGHT
—
of the edge considered
consideredacceptedin a treerejected (dashed)
10 nodes · 11 edges · seed 7 · 24 steps
step 0 / 23
Nodes10
kruskal.ts
1
function kruskal(graph: Graph) {
2
  const edges = [...graph.edges].sort((first, second) => first.weight - second.weight);
3
  const unionFind = new UnionFind(graph.nodes.length);
4
  const tree: Edge[] = [];
5
  for (const edge of edges) {
6
    if (unionFind.find(edge.from) === unionFind.find(edge.to)) continue;
7
    unionFind.union(edge.from, edge.to);
8
    tree.push(edge);
9
  }
10
  return tree;
11
}
CURRENT STEP
line 2

Sort the 11 edges by weight. Every node starts as its own component (the label is its representative).

// how it works

Understanding Kruskal

Kruskal · sort the edges, skip the ones that close a cycle
01

The idea

Kruskal's algorithm sorts every edge by weight and walks the list, accepting an edge whenever its two endpoints are still in different pieces of the forest, and rejecting it when they are already connected, because then it would close a cycle. After V − 1 acceptances the forest is one tree.

The 'already connected' question is answered by a union-find structure: each node points to a representative, find follows the pointers, union merges two sets. With path compression it is almost O(1), so sorting the edges is the whole cost.

02

The four stages

1
sortall edges, lightest first
2
considerthe next edge in the list
3
rejectsame component: it would close a cycle
4
acceptdifferent components: union them
03

Complexity

best
O(E log E)the sort dominates
average
O(E log E)union-find is near constant per edge
worst
O(E log E)same: the input order does not matter
space
O(V + E)sorted edges and the union-find
04

Versus its siblings

EDGE SCANS · 1 000 NODES, 3 000 EDGES
prim, scan
3M
prim, heap
30,000
kruskal
33,000
borůvka
30,000
kruskal's cost is the sort · heap versions count log-factor operations
05

Pseudocode

KRUSKAL(graph)
  sort edges by weight; every node its own set
  for each edge from–to in that order
    if find(from) ≠ find(to): union(from, to); add the edge to the tree
06

When to use

Sparse graphs, where sorting E edges is cheap and Prim's heap has nothing to gain.
Edges that arrive already sorted, or a forest instead of a tree: Kruskal handles disconnected graphs for free.
07

Pitfalls

Union-find without path compression or union by rank degrades to O(V) per find.
Stopping after V − 1 accepted edges saves the tail of the list; the naive loop scans it all.
On dense graphs sorting V² edges loses to Prim with a heap.
08

History

Joseph Kruskal published the algorithm in 1956, one year before Prim, as a proof about the shortest spanning subtree of a graph. The union-find structure that makes it fast was analysed by Tarjan in 1975, who showed its near-constant inverse-Ackermann bound.

Back to Graphs