Kruskal's Minimum Spanning Tree

Add edges in increasing weight, skipping those that form a cycle. Greedy is optimal by the cut property: the lightest edge crossing any cut belongs to an MST.

Algorithm Steps

Sort edges by increasing weight.
Initialize DSU (disjoint set union).
Scan edges: add if endpoints are in different components.
Stop after V−1 edges added.

Speed (ms)

Nodes

Pseudocode

1procedure KRUSKAL(G)
2  sort all edges by weight
3  create DSU for vertices
4  MST ← ∅
5  for each edge (u, v, w) in increasing weight do
6    if find(u) ≠ find(v) then
7      MST ← MST ∪ {(u, v)}; union(u, v)
8    else
9      skip edge // would form cycle
10    end if
11  end for
12  return MST
13end procedure

Practice Problems

Use Cases

Network design: laying cables/roads to connect cities at minimum cost.
Cluster analysis: building hierarchical clusters (single-linkage).
Approximation algorithms (e.g., for TSP variants).

Back to Coin Change Greedy Next: Prim's MST