jsschools

Kruskal's Algorithm

Builds a minimum spanning tree by sorting all edges by weight and greedily adding each edge that does not form a cycle, using a Union-Find (Disjoint Set Union) structure.

Spec ↗

Syntax

kruskal(edges, V)

Parameters

NameTypeRequiredDescription
edges Array<{u: number, v: number, w: number}> Yes List of undirected weighted edges.
V number Yes Total number of vertices (0-indexed).

Returns

{ weight: number, edges: Array<{u,v,w}> } — Total MST weight and the list of edges included.

Examples

function kruskal(edges, V) {
  const parent = Array.from({length: V}, (_, i) => i);
  const rank = new Array(V).fill(0);

  function find(x) {
    if (parent[x] !== x) parent[x] = find(parent[x]); // path compression
    return parent[x];
  }
  function union(a, b) {
    const ra = find(a), rb = find(b);
    if (ra === rb) return false;
    if (rank[ra] < rank[rb]) parent[ra] = rb;
    else if (rank[ra] > rank[rb]) parent[rb] = ra;
    else { parent[rb] = ra; rank[ra]++; }
    return true;
  }

  const sorted = [...edges].sort((a, b) => a.w - b.w);
  let weight = 0;
  const mstEdges = [];
  for (const e of sorted) {
    if (union(e.u, e.v)) { weight += e.w; mstEdges.push(e); }
  }
  return { weight, edges: mstEdges };
}

const edges = [
  {u:0,v:1,w:10},{u:0,v:2,w:6},{u:0,v:3,w:5},
  {u:1,v:3,w:15},{u:2,v:3,w:4},
];
const result = kruskal(edges, 4);
console.log(result.weight);
console.log(result.edges.map(e=>`${e.u}-${e.v}`).join(', '));
Output 
19
2-3, 0-3, 0-1

// Forest of components: Kruskal produces a spanning forest
function kruskal(edges, V) {
  const par = Array.from({length:V},(_,i)=>i);
  const find = x => par[x]===x ? x : (par[x]=find(par[x]));
  const union = (a,b) => { const ra=find(a),rb=find(b); if(ra===rb)return false; par[ra]=rb; return true; };
  return [...edges].sort((a,b)=>a.w-b.w).filter(e=>union(e.u,e.v));
}

// Two disconnected components: 0-1 and 2-3
const edges = [{u:0,v:1,w:1},{u:2,v:3,w:2}];
console.log(kruskal(edges, 4).map(e=>`${e.u}-${e.v}:${e.w}`));
Output 
[ '0-1:1', '2-3:2' ]

Notes

| Case | Time | Space | |---------|---------------|-------| | Best | O(E log E) | O(V) | | Average | O(E log E) | O(V) | | Worst | O(E log E) | O(V) | Dominated by the edge sort. With Union-Find using path compression and union by rank, the union/find operations are near-O(1) (amortized O(α(V)) where α is the inverse Ackermann function). Kruskal's is efficient for sparse graphs (small E). For dense graphs (E ≈ V²) Prim's with an adjacency matrix runs in O(V²). Both algorithms produce valid MSTs for any connected undirected weighted graph.

See also