Minimum Spanning Tree

A spanning tree of a connected undirected graph is a subgraph that:

Connects all V vertices
Uses exactly V−1 edges
Contains no cycles

A Minimum Spanning Tree (MST) is the spanning tree whose total edge weight is minimised. MSTs are not necessarily unique — there may be several with the same total weight.

Why V−1 Edges?

A tree with V nodes always has exactly V−1 edges. Any fewer and the graph is disconnected. Any more and it contains a cycle — which means you could remove an edge and still stay connected, so it would not be a spanning tree.

This is a useful sanity check: after running an MST algorithm, confirm you collected exactly V−1 edges. If you collect fewer, the original graph was not connected (no MST exists).

The Cut Property

The theoretical foundation of both MST algorithms is the cut property:

A cut partitions the vertices into two non-empty groups S and V∖S. The minimum weight edge that crosses the cut is guaranteed to be part of some MST.

This is why greedy algorithms work for MST: at every step, adding the globally cheapest safe edge is provably correct.

The Cycle Property

Complementary to the cut property:

For any cycle in the graph, the maximum weight edge in that cycle is never required in a minimum spanning tree (assuming distinct weights).

Equivalently: if you consider adding a heavy edge that would create a cycle, you can always remove the heaviest edge in the resulting cycle and get a lighter spanning tree.

Real-World Applications

Network wiring — connect all buildings in an office campus with minimum total cable length
Clustering — remove the k-1 heaviest MST edges to form k clusters (single-linkage clustering)
Approximation algorithms — MST cost is a lower bound for the Travelling Salesman Problem
Water/electricity supply networks — connect all consumers at minimum infrastructure cost
Image segmentation — pixels as vertices, edge weights as colour differences

Kruskal's Algorithm

Kruskal's greedily picks edges in order of increasing weight, adding each one only if it does not create a cycle. Cycle detection uses Union-Find (Disjoint Set Union): adding an edge (u, v) creates a cycle if and only if u and v are already in the same component.

Steps:

Sort all edges by weight — O(E log E).
For each edge (cheapest first): if its two endpoints are in different components, add it to the MST and union the components.
Stop when V−1 edges have been added.

// Union-Find with path compression and union by rank
class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank   = new Array(n).fill(0);
  }

  find(x) {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]); // path compress
    return this.parent[x];
  }

  union(x, y) {
    const px = this.find(x), py = this.find(y);
    if (px === py) return false; // already connected — would create a cycle
    if (this.rank[px] < this.rank[py])      this.parent[px] = py;
    else if (this.rank[px] > this.rank[py]) this.parent[py] = px;
    else { this.parent[py] = px; this.rank[px]++; }
    return true;
  }
}

function kruskal(numVertices, edges) {
  // edges: [[u, v, weight], ...]
  edges.sort((a, b) => a[2] - b[2]); // sort by weight

  const uf  = new UnionFind(numVertices);
  const mst = [];
  let totalWeight = 0;

  for (const [u, v, w] of edges) {
    if (uf.union(u, v)) { // no cycle
      mst.push([u, v, w]);
      totalWeight += w;
      if (mst.length === numVertices - 1) break; // MST complete
    }
  }

  return mst.length === numVertices - 1
    ? { edges: mst, totalWeight }
    : null; // graph not connected
}

const edges = [
  [0,1,10],[0,2,6],[0,3,5],[1,3,15],[2,3,4]
];
console.log(kruskal(4, edges));
// { edges: [[2,3,4],[0,3,5],[0,1,10]], totalWeight: 19 }

Note

Time: O(E log E) dominated by sorting. Union-Find operations are nearly O(1) each with path compression and union by rank. Space: O(V + E).

Prim's Algorithm

Prim's grows the MST from an arbitrary starting vertex, always extending with the cheapest edge that connects the current MST to a new vertex.

It is analogous to Dijkstra: use a min-heap containing (edgeWeight, vertex) pairs for the frontier, and greedily extract the minimum.

Steps:

Start from any vertex, add it to the MST.
Add all its edges to the min-heap.
Extract the cheapest edge. If the destination vertex is already in the MST, skip (would create a cycle).
Otherwise, add the vertex and its edges to the heap. Repeat until all vertices are included.

// Reusing MinHeap from the Dijkstra page
class MinHeap {
  constructor() { this.heap = []; }
  push(item) { this.heap.push(item); this._bubbleUp(this.heap.length-1); }
  pop() {
    const top = this.heap[0], last = this.heap.pop();
    if (this.heap.length) { this.heap[0] = last; this._siftDown(0); }
    return top;
  }
  get size() { return this.heap.length; }
  _bubbleUp(i) {
    while (i > 0) {
      const p = (i-1)>>1;
      if (this.heap[p][0] <= this.heap[i][0]) break;
      [this.heap[p],this.heap[i]] = [this.heap[i],this.heap[p]]; i=p;
    }
  }
  _siftDown(i) {
    const n = this.heap.length;
    while (true) {
      let s=i; const l=2*i+1,r=2*i+2;
      if (l<n && this.heap[l][0]<this.heap[s][0]) s=l;
      if (r<n && this.heap[r][0]<this.heap[s][0]) s=r;
      if (s===i) break;
      [this.heap[s],this.heap[i]]=[this.heap[i],this.heap[s]]; i=s;
    }
  }
}

function prim(numVertices, adjList) {
  // adjList: Map<vertex, Array<[neighbour, weight]>>
  const inMST  = new Set();
  const heap   = new MinHeap(); // [weight, vertex, fromVertex]
  const mst    = [];
  let totalWeight = 0;

  // Start from vertex 0
  heap.push([0, 0, -1]);

  while (heap.size > 0 && inMST.size < numVertices) {
    const [w, node, from] = heap.pop();
    if (inMST.has(node)) continue; // already in MST

    inMST.add(node);
    if (from !== -1) {
      mst.push([from, node, w]);
      totalWeight += w;
    }

    for (const [neighbour, edgeWeight] of (adjList.get(node) || [])) {
      if (!inMST.has(neighbour)) {
        heap.push([edgeWeight, neighbour, node]);
      }
    }
  }

  return inMST.size === numVertices
    ? { edges: mst, totalWeight }
    : null;
}

// Example: same graph as Kruskal above
const adj = new Map([
  [0, [[1,10],[2,6],[3,5]]],
  [1, [[0,10],[3,15]]],
  [2, [[0,6],[3,4]]],
  [3, [[0,5],[1,15],[2,4]]],
]);
console.log(prim(4, adj));
// { edges: [[0,3,5],[3,2,4],[0,1,10]], totalWeight: 19 }

Kruskal vs Prim — When to Use Each

Property	Kruskal's	Prim's
Time complexity	O(E log E)	O((V+E) log V) with heap
Space	O(E + V) for Union-Find	O(V + E) for heap
Best for	Sparse graphs (E ≈ V)	Dense graphs (E ≈ V²)
Core data structure	Union-Find + sorted edges	Min-heap
Handles disconnected graphs	Yes — detects via edge count	Yes — inMST.size check
Easier to implement from scratch	Yes (sort + union-find)	Slightly harder (heap)

Tip

In interviews: use Kruskal's when you see a list of edges to process. Use Prim's when you have an adjacency list and the graph is dense. Both give the same total MST weight.

LeetCode Problem — Min Cost to Connect All Points (LeetCode 1584)

Given n points on a 2D plane, find the minimum cost to connect all points where the cost of connecting two points is their Manhattan distance |xi-xj| + |yi-yj|.

This is a complete graph (every pair of points is connected), so Prim's with a lazy heap is ideal — E = O(V²) and we do not need to materialise all edges upfront.

function minCostConnectPoints(points) {
  const n = points.length;
  const inMST = new Array(n).fill(false);
  const minCost = new Array(n).fill(Infinity);
  minCost[0] = 0;
  let totalCost = 0;

  // Prim's with a simple array (O(V²)) — fine since E = O(V²) anyway
  for (let added = 0; added < n; added++) {
    // Pick the cheapest vertex not yet in MST
    let u = -1;
    for (let i = 0; i < n; i++) {
      if (!inMST[i] && (u === -1 || minCost[i] < minCost[u])) u = i;
    }
    inMST[u] = true;
    totalCost += minCost[u];

    // Update cost to reach each non-MST vertex via u
    for (let v = 0; v < n; v++) {
      if (!inMST[v]) {
        const dist = Math.abs(points[u][0]-points[v][0]) + Math.abs(points[u][1]-points[v][1]);
        if (dist < minCost[v]) minCost[v] = dist;
      }
    }
  }
  return totalCost;
}

console.log(minCostConnectPoints([[0,0],[2,2],[3,10],[5,2],[7,0]])); // 20

Practice Problems

LeetCode 1584 — Min Cost to Connect All Points (Prim or Kruskal)
LeetCode 1135 — Connecting Cities With Minimum Cost (Kruskal)
LeetCode 1489 — Find Critical and Pseudo-Critical Edges in MST
LeetCode 1168 — Optimize Water Distribution in a Village (add a virtual node)
LeetCode 684 — Redundant Connection (Union-Find cycle detection)