Minimum spanning tree — Kruskal and Prim

Medium

Problem

Given a connected, weighted, undirected graph, choose a subset of edges that connects every node with the minimum total weight (a spanning tree with no cycles). Return that weight. Min Cost to Connect All Points is the same problem with Manhattan distance as the edge weight.

Example 1

Input:  edges (u, v, w) = [[0,1,10], [0,2,6], [0,3,5], [1,3,15], [2,3,4]]
Output: 19

Edges 2–3 (4), 0–3 (5) and 0–1 (10).

Also asked as: Implement Kruksal’sAlgorithm · Implement Prim’s Algorithm · Total no. of Spanning tree in a graph

Test cases

Case 1

Input:    4, [[0,1,10],[0,2,6],[0,3,5],[1,3,15],[2,3,4]]
Expected: 19

Case 2

Input:    3, [[0,1,1]]
Expected: -1

Case 3

Input:    1, []
Expected: 0

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. Kruskal — sort edges, Union-Find to avoid cycles

Time O(E log E)Space O(V)

Add the cheapest edge that connects two different components; stop after V−1 edges.

function kruskal(n, edges) { // edges: [u, v, w]
edges.sort((a, b) => a[2] - b[2]);
const parent = Array.from({ length: n }, (_, i) => i);
const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x])));
let cost = 0, used = 0;
for (const [u, v, w] of edges) {
const ru = find(u), rv = find(v);
if (ru !== rv) { parent[ru] = rv; cost += w; used++; }
}
return used === n - 1 ? cost : -1; // -1 ⇒ disconnected
}

2. Prim — grow the tree from one node, always take the cheapest crossing edge

Time O(E log V)Space O(V + E)

Min-priority queue of edges leaving the current tree; repeatedly add the lightest edge to a new node.

function prim(adj) { // adj[u] = [[v, w], ...]
const n = adj.length;
const inMST = new Array(n).fill(false);
const pq = [[0, 0]];
let cost = 0;
while (pq.length) {
pq.sort((a, b) => a[0] - b[0]);
const [w, u] = pq.shift();
if (inMST[u]) continue;
inMST[u] = true; cost += w;
for (const [v, w2] of adj[u]) if (!inMST[v]) pq.push([w2, v]);
}
return cost;
}

Counting all spanning trees uses Kirchhoff’s Matrix-Tree Theorem: the determinant of any cofactor of the Laplacian (degree matrix − adjacency matrix).