← All patterns
20 / 29
Graphs & Networks

Minimum Spanning Tree

🌉
Picture this

Bridge builders sort every possible bridge by price and accept only bridges that join separate islands.

When you see it

Signal words

If the prompt uses any of these, this pattern should come to mind first.

connect allminimum costspanning treeKruskalPrimedges

Ask yourself

  1. Must all nodes be connected with minimum total edge cost?
  2. Are edges undirected?
  3. Can sorted edges plus union find avoid cycles?

Canonical template

edges.sort((a, b) => a.cost - b.cost);
let total = 0;
for (const edge of edges) {
  if (union(edge.u, edge.v)) total += edge.cost;
}
return total;

Common pitfalls

Applying MST to shortest-path questions.

Forgetting to verify every node became connected.