Minimum Spanning Tree
Kruskal sorts edges and adds the cheapest edge that joins two different components. Prim grows one tree using a heap.
GraphsO(E log E)New2 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
connect all points at minimum cost
min cost to connect cities
The template
Get this into muscle memory, then adapt the condition per problem.
edges.sort((a, b) => a[2] - b[2]);
let cost = 0;
for (const [u, v, w] of edges)
if (find(u) !== find(v)) { union(u, v); cost += w; } Watch Kruskal Minimum Spanning TreeIf you are stuck
The generic hint ladder for this pattern, in order.
- 1You need every node connected, and total cost is what matters.
- 2The cheapest edge crossing any cut is always safe to take.
- 3Union-Find is what makes the cycle check cheap.
Drill it
Every problem in the bank that uses this pattern.
0 / 2 solved