Kruskal's MST Algorithm

Build the minimum spanning tree by sorting edges by weight and using a union-find structure to skip edges that would form a cycle, running in O(E log E) time.

5 min read Level 3/5 #dsa#graph#mst

What you'll learn

Implement Kruskal's algorithm with edge sorting and union-find
Explain how union-find prevents cycle formation during edge addition
Compare Kruskal's and Prim's and know when each is preferred

Kruskal’s algorithm builds the MST edge by edge using a global sort: examine every edge in ascending weight order and add it if its two endpoints are in different components. A union-find (disjoint set) structure tracks which vertices are connected.

Algorithm Steps

Sort all edges by weight ascending.
Initialize a union-find with one component per vertex.
For each edge (u, v, w) in sorted order:
- If find(u) !== find(v), add the edge and union(u, v).
Stop when V-1 edges have been added (the MST is complete).

// Minimal union-find for Kruskal's
class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }
  find(x) {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }
  union(x, y) {
    const px = this.find(x), py = this.find(y);
    if (px === py) return false;
    if (this.rank[px] < this.rank[py]) this.parent[px] = py;
    else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
    else { this.parent[py] = px; this.rank[px]++; }
    return true;
  }
}

// edges: Array<[from, to, weight]>  (undirected)
function kruskalMST(numVertices, edges) {
  const sorted = [...edges].sort((a, b) => a[2] - b[2]);
  const uf = new UnionFind(numVertices);
  const mstEdges = [];
  let totalWeight = 0;

  for (const [u, v, w] of sorted) {
    if (uf.union(u, v)) {
      mstEdges.push([u, v, w]);
      totalWeight += w;
      if (mstEdges.length === numVertices - 1) break;
    }
  }

  return { mstEdges, totalWeight };
}

const edges = [
  [0, 1, 2], [0, 3, 6],
  [1, 2, 3], [1, 3, 8], [1, 4, 5],
  [2, 4, 7], [3, 4, 9],
];
const { mstEdges, totalWeight } = kruskalMST(5, edges);
console.log(mstEdges);    // [[0,1,2],[1,2,3],[1,4,5],[0,3,6]]
console.log(totalWeight); // 16

Kruskal’s vs Prim’s

Aspect	Kruskal’s	Prim’s
Input form	Edge list (sorted)	Adjacency list + heap
Best for	Sparse graphs	Dense graphs
Time	O(E log E)	O(E log V)
Core data str.	Union-find	Min-heap

For sparse graphs Kruskal’s is often simpler to code; for dense graphs where E is close to V², Prim’s with a heap is faster.

Up Next

The union-find structure used inside Kruskal’s is powerful on its own — learn how path compression and union by rank make it nearly O(1) per operation.

Union-Find (Disjoint Set Union) →