Kruskal's Minimum Spanning Tree

Sort every edge cheapest-first and add each one unless it would form a cycle — union-find checks that instantly.

Kruskal's algorithm builds the same minimum spanning tree as Prim, but thinks edge-first instead of growing one tree. Sort *every* edge from cheapest to most expensive, then walk that list and add each edge — unless it would connect two vertices that are *already* linked, which would make a cycle.

Merge separate pieces into one

Early on, the graph is a scatter of single vertices. Each accepted edge merges two separate pieces into one larger piece. The danger is adding an edge *within* a piece that's already connected — a wasted cycle. The whole problem reduces to one fast question, asked for every edge: *are these two endpoints already in the same piece?*

Union-find answers it instantly

A union-find (disjoint-set) structure tracks which vertices share a group. find(x) returns x's group representative; union(a, b) merges two groups. If find(u) === find(v), the edge would close a cycle — skip it. Otherwise accept it and union the two ends. Both operations are near-O(1).

1Sort all edges by weight, cheapest first.
2Start with every vertex in its own one-element set.
3For each edge (u, v) in order: if find(u) ≠ find(v), accept it and union(u, v).
4If they're already in the same set, skip — it would form a cycle.
5Stop once V − 1 edges are accepted; that's a complete spanning tree.

function kruskal(vertices, edges) {
  edges.sort((a, b) => a.w - b.w);     // cheapest first
  const uf = new UnionFind(vertices);
  const mst = [];
  for (const { u, v, w } of edges) {
    if (uf.find(u) !== uf.find(v)) {   // different pieces -> no cycle
      uf.union(u, v);
      mst.push({ u, v, w });
    }
  }
  return mst;                          // V - 1 edges when connected
}

OperationTimeSpace

Sort edges · dominates the running timeO(E log E)O(V)

Union-find checks · α is the near-constant inverse-Ackermann≈ O(E α(V))O(V)

Check yourself

How does Kruskal's algorithm tell, instantly, whether adding an edge would create a cycle?