Kruskal's algorithm

To connect every node as cheaply as possible, go through the edges from lightest to heaviest. Take an edge if it joins two separate groups; skip it if its ends are already connected, because it would only close a loop. Union-find answers that question almost instantly.

O(E log E)greedyuses union-find

edges, lightest first

A–D

C–E

D–F

A–B

B–E

B–C

E–F

B–D

E–G

F–G

D–E

Connect every node as cheaply as possible, with no loops: a minimum spanning tree.

step 0 / 24

1function kruskal(n, edges) {2  const parent = Array.from({ length: n }, (_, i) => i);3  const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x])));4  const tree = [];5  for (const [u, v, w] of [...edges].sort((a, b) => a[2] - b[2])) {6    const ru = find(u), rv = find(v);7    if (ru === rv) continue;8    parent[ru] = rv;9    tree.push([u, v, w]);10  }11  return tree;12}

Keys: Space play or pause, ← → step. The URL always points at the frame you are on.

What it costs

Case	Time	When
best	E log E	sorting the edges dominates
average	E log E	each find is almost constant with union-find
worst	E log E	the same: every edge is looked at once
space	V + E	the sorted edges and a parent per node

Where it breaks

Why greedy works here. The lightest edge across any split of the nodes into two sides must be in some cheapest tree. Every edge Kruskal takes is exactly that, so taking the cheapest safe edge first never needs undoing.
Ties give different trees. Pick Equal weights: any two of A–B, B–C and C–A work, at the same total. The minimum weight is unique; the tree is not.
A disconnected graph. Pick Two islands: no edge can join the two parts, so the result is a forest, one tree per island. Code that expects exactly V − 1 edges must check for this.