Kruskal's Minimum Spanning Tree

Connect every node as cheaply as possible: sort the edges by weight and take each one unless it would close a cycle. Union-find answers 'would this close a cycle?' in near-constant time.

time O(E log E)

space O(V)

Input

Press Tab out of the box or click Resetto regenerate frames from the current input.

Visualization

No frames yet — edit input and click Run.

—

Pseudocode

sort edges by weight
for (u, v, w) in edges:
  if find(u) != find(v):
    union(u, v)
    mst.append((u, v, w))