Minimum spanning tree — Kruskal and Prim
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
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).