MSTO(E log E)· Level 05

Kruskal's MST

Greedy minimum spanning tree via Union-Find.

Intuition

Sort all edges from cheapest to most expensive. Walk the list and add each edge — but only if it doesn't form a cycle. Union-Find tells you in near-constant time whether two endpoints already share a component.

Step-by-step

1
Sort all edges by weight ascending.
2
Initialise a Union-Find (Disjoint Set Union) over all vertices.
3
For each edge (u,v,w) in order: if `find(u) ≠ find(v)`, accept the edge and `union(u,v)`.
4
Stop after V−1 edges have been accepted — that's your MST.

Pseudocode

pseudocode

KRUSKAL(G):
  sort edges by weight asc
  init DSU over V
  MST = []
  for (u,v,w) in edges:
    if find(u) != find(v):
      union(u,v)
      MST.append((u,v,w))
  return MST

Implementation (Python)

python

class DSU:
    def __init__(self, n):
        self.p = list(range(n))
    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]
            x = self.p[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        self.p[ra] = rb
        return True

def kruskal(n, edges):
    edges = sorted(edges, key=lambda e: e[2])
    dsu = DSU(n)
    mst = []
    for u, v, w in edges:
        if dsu.union(u, v):
            mst.append((u, v, w))
    return mst

Real-world applications

Designing low-cost network backbones
Clustering (single-linkage)
Approximation algorithms for TSP