Kruskal's MST

Graphs

avgO(E log E)worstO(E log E)spaceO(V + E)

Each of the 8 nodes starts in its own set: it is its own parent

1 / 22

Code

function kruskal(graph: Graph) {  const parent = graph.nodes.map((v) => v); // every node starts as its own set  const find = (v: number): number => (parent[v] === v ? v : (parent[v] = find(parent[v])));  const edges = [...graph.edges].sort((a, b) => a.weight - b.weight);  const mst: Edge[] = [];  for (const edge of edges) {    const a = find(edge.from);    const b = find(edge.to);    if (a === b) continue; // same set already: this edge would close a cycle    parent[b] = a; // union: hang b's tree under a's root    mst.push(edge);    if (mst.length === graph.size - 1) break;  }  return mst;}

procedure Kruskal(G)  parent[v] ← v for every node v    ▷ n singleton sets  find(v): follow parent to the root, pointing visited nodes straight at it  sort the edges by weight, lightest first  mst ← []  for each edge (u, v) in sorted order do    a ← find(u)    b ← find(v)    if a = b then skip it    ▷ u and v are already connected    parent[b] ← a    ▷ union the two sets    add (u, v) to mst    if mst has n − 1 edges then stop  end for  return mstend procedure

Variables

sets=8

Counters

edges considered: 0
unions: 0

Nodes8

Source

Edgesweights 1 to 99

How it works

Kruskal's algorithm considers edges from lightest to heaviest and keeps each one that joins two different components, skipping any edge that would close a cycle. A union-find structure answers "are these already connected?" in near-constant time, so sorting the edges dominates the cost.

Complexity

Best: O(E log E)
Average: O(E log E)
Worst: O(E log E)
Space: O(V + E)

Kruskal's MST

How it works

Complexity

Search algorithms