Pattern Guide
Minimum Spanning Tree
"Connect all nodes with minimum total edge weight. Kruskal or Prim."
A minimum spanning tree (MST) connects all n nodes with exactly n-1 edges and minimum total weight. Two greedy algorithms: Kruskal's (sort edges, add if no cycle — uses Union-Find) and Prim's (grow MST from any node, always add cheapest edge — uses min-heap). Both O(E log E). Master MST for network design, clustering, and minimum cost connection problems.
Problems you can solve with this pattern
5 problems · click any to start solving
// ─── Kruskal's (sort edges + Union-Find) ───────────────────────────────────
function kruskal(n, edges) { // edges = [[weight, u, v], ...]
edges.sort((a, b) => a[0] - b[0]);
const parent = Array.from({length: n}, (_, i) => i);
const rank = new Array(n).fill(0);
function find(x) {
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
function union(x, y) {
const [px, py] = [find(x), find(y)];
if (px === py) return false;
if (rank[px] < rank[py]) parent[px] = py;
else if (rank[px] > rank[py]) parent[py] = px;
else { parent[py] = px; rank[px]++; }
return true;
}
let totalWeight = 0, edgesUsed = 0;
for (const [w, u, v] of edges) {
if (union(u, v)) { totalWeight += w; edgesUsed++; }
if (edgesUsed === n - 1) break;
}
return edgesUsed === n - 1 ? totalWeight : -1; // -1 if graph disconnected
}
// ─── Prim's (min-heap, grow from node 0) ────────────────────────────────────
function prim(n, adjList) { // adjList[u] = [[weight, v], ...]
const inMST = new Array(n).fill(false);
const heap = [[0, 0]]; // [cost, node], min-heap
let totalWeight = 0, count = 0;
while (heap.length && count < n) {
const [cost, node] = heap.shift(); // use actual min-heap in prod
if (inMST[node]) continue;
inMST[node] = true; totalWeight += cost; count++;
for (const [w, nei] of adjList[node]) {
if (!inMST[nei]) heap.push([w, nei]);
}
heap.sort((a, b) => a[0] - b[0]); // use priority queue in production
}
return count === n ? totalWeight : -1;
}MST algorithms are greedy: they never make a suboptimal local choice. Kruskal's sorts all edges by weight, then greedily picks the cheapest edge that doesn't create a cycle (use Union-Find to check). Prim's grows the MST outward from a starting node, always picking the cheapest edge that connects the current tree to a new node. Both produce the same MST weight (may differ in structure if ties exist).
// ─── Kruskal's (sort edges + Union-Find) ───────────────────────────────────
function kruskal(n, edges) { // edges = [[weight, u, v], ...]
edges.sort((a, b) => a[0] - b[0]);
const parent = Array.from({length: n}, (_, i) => i);
const rank = new Array(n).fill(0);
function find(x) {
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
function union(x, y) {
const [px, py] = [find(x), find(y)];
if (px === py) return false;
if (rank[px] < rank[py]) parent[px] = py;
else if (rank[px] > rank[py]) parent[py] = px;
else { parent[py] = px; rank[px]++; }
return true;
}
let totalWeight = 0, edgesUsed = 0;
for (const [w, u, v] of edges) {
if (union(u, v)) { totalWeight += w; edgesUsed++; }
if (edgesUsed === n - 1) break;
}
return edgesUsed === n - 1 ? totalWeight : -1; // -1 if graph disconnected
}
// ─── Prim's (min-heap, grow from node 0) ────────────────────────────────────
function prim(n, adjList) { // adjList[u] = [[weight, v], ...]
const inMST = new Array(n).fill(false);
const heap = [[0, 0]]; // [cost, node], min-heap
let totalWeight = 0, count = 0;
while (heap.length && count < n) {
const [cost, node] = heap.shift(); // use actual min-heap in prod
if (inMST[node]) continue;
inMST[node] = true; totalWeight += cost; count++;
for (const [w, nei] of adjList[node]) {
if (!inMST[nei]) heap.push([w, nei]);
}
heap.sort((a, b) => a[0] - b[0]); // use priority queue in production
}
return count === n ? totalWeight : -1;
}- Kruskal's: better for sparse graphs (E log E), uses Union-Find
- Prim's: better for dense graphs (V² with array, E log V with heap)
- Both produce same MST weight
MST properties:
- Unique if all edge weights are distinct
- n-1 edges for n nodes
- Cut property: lightest edge crossing any cut is in MST
- Cycle property: heaviest edge in any cycle is NOT in MST
Key applications: network design (cable laying), clustering (remove heaviest MST edges), Borůvka for parallel MST, Steiner tree (subset of nodes).