Kruskal Minimum Spanning Tree

Medium

Sort every edge by weight and take it whenever it joins two different components. Union-Find makes the cycle check cheap.

greedyunion findMST

TimeO(E log E)

SpaceO(V)

Inputweighted edges u-v:w

edges

0-2:1

1-2:2

3-4:3

0-1:4

1-3:5

2-4:7

2-3:8

Edges sorted by weight: 0-2(1), 1-2(2), 3-4(3), 0-1(4), 1-3(5), 2-4(7), 2-3(8).

cost0

1 / 12

sort edges by weight

for (u, v, w) in edges:

if find(u) != find(v):

union(u, v); total += w

stop once V-1 edges are taken

Why it matters

The cheapest edge crossing any cut is always safe, which is what makes the greedy choice correct.

Practise this

Keyboard

space play← → stepr restartctrl K search

More in Graphs