Graph AlgosGraph Algorithms
Kruskal's Algorithm
Minimum spanning tree by sorting all edges and greedily adding each edge that joins two different components, tracked with union-find.
Edges by weight
B–G (1)A–C (2)G–E (2)E–F (3)G–D (3)A–B (4)B–D (5)D–F (6)C–G (8)C–E (10)
DSU parent
| node | parent | root |
|---|---|---|
| A | A | A |
| B | B | B |
| C | C | C |
| D | D | D |
| E | E | E |
| F | F | F |
| G | G | G |
1/15Sort the 10 edges by weight and put each node in its own set. Kruskal grows a forest by taking the cheapest edge that joins two different trees.
Edge under considerationAccepted (MST)Rejected (cycle)Node in some tree
PseudocodeLearn Kruskal's Algorithm →
1sort edges by weight ascending2make_set(v) for every node3for (u, v, w) in edges:4 if find(u) != find(v):5 union(u, v); mst.add((u, v, w))6 else: skip — u and v already connected, edge would close a cycle7return mstComplexity
best O(E log E)
avg O(E log E)
worst O(E log E)
space O(V + E)
Speed