Kruskal's MST

How it works, step by step

1. 1

   Sort every edge by weight, cheapest first. This order is the whole idea.

2. 2

   Give each node its own group. A union-find structure tracks the groups fast.

3. 3

   Take the next cheapest edge and look up the group of each endpoint.

4. 4

   Different groups? Take the edge and merge the two groups into one.

5. 5

   Same group? The edge would close a loop - skip it, and never look at it again.

6. 6

   Stop after V - 1 edges are kept. Until that moment you have a *forest* of separate trees - the last merge turns it into one spanning tree.

The code, in JavaScript

function find(parent, x) {
  while (parent[x] !== x) {
    parent[x] = parent[parent[x]];   // path halving: point at grandparent
    x = parent[x];
  }
  return x;
}

function kruskal(nodes, edges) {
  const parent = {};
  for (const n of nodes) parent[n] = n; // everyone starts alone

  // Cheapest first - this order is the whole idea.
  const sorted = [...edges].sort((a, b) => a.w - b.w);
  const tree = [];
  let total = 0;

  for (const { u, v, w } of sorted) {
    const ru = find(parent, u);
    const rv = find(parent, v);
    if (ru === rv) continue;         // same group: would close a loop
    parent[ru] = rv;                 // merge the two groups
    tree.push([u, v, w]);
    total += w;
    if (tree.length === nodes.length - 1) break;  // tree complete
  }

  return { tree, total };
}

const nodes = ["A", "B", "C", "D", "E", "F", "G"];
const edges = [
  { u: "A", v: "B", w: 2 },  { u: "D", v: "F", w: 3 },
  { u: "C", v: "E", w: 4 },  { u: "A", v: "C", w: 5 },
  { u: "B", v: "C", w: 6 },  { u: "F", v: "G", w: 7 },
  { u: "D", v: "G", w: 8 },  { u: "B", v: "D", w: 9 },
  { u: "D", v: "E", w: 11 }, { u: "E", v: "G", w: 12 },
  { u: "E", v: "F", w: 14 },
];

kruskal(nodes, edges).total;
// → 30  (6 edges kept: A-B, D-F, C-E, A-C, F-G, B-D)

Dry run: building the MST edge by edge

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

• Kruskal builds a forest, not a tree, for most of its run. Separate components floating around mid-way is normal and correct - they only merge into one tree at the very end. Do not "fix" it.
• It needs union-find. Checking "would this close a loop?" with a DFS per edge works but costs O(E·V) - people ship that by accident and wonder why big inputs crawl. DSU makes the check near O(1).
• Equal weights make the MST non-unique: two runs (or two libraries) can return different edge sets, both optimal. Tests that compare exact edges are brittle - compare the total weight instead.
• A disconnected graph has no spanning tree - Kruskal does not throw, it silently returns a forest. Always check that you kept exactly V - 1 edges; fewer means the graph was not connected.

Kruskal's MST vs. its closest relatives