Kruskal & Prim Algorithms

A Minimum Spanning Tree (MST) of a connected, weighted, undirected graph is a subset of edges that connects all vertices with the minimum possible total edge weight, using exactly V-1 edges with no cycles. MSTs appear in network design, cluster analysis, and as a subroutine in approximation algorithms for NP-hard problems.

Two classic greedy algorithms solve the MST problem: Kruskal's and Prim's. Both always produce a correct MST, but they approach the problem from opposite directions — Kruskal builds the MST edge-by-edge sorted by weight, while Prim grows the MST vertex-by-vertex from a starting node.

Kruskal's Algorithm

Kruskal's algorithm takes a global view: sort every edge in the graph by weight, then greedily pick the cheapest edges that don't form a cycle. It doesn't matter where in the graph the edge is — the only test is "does adding this edge create a cycle?"

Sort all edges in non-decreasing order of weight.
Initialize a Union-Find (DSU) structure with each vertex as its own component.
Iterate over sorted edges. For each edge (u, v, weight):
— If find(u) ≠ find(v), the edge connects two different components. Add it to the MST and call union(u, v).
— If find(u) === find(v), skip the edge — it would create a cycle.
Stop when V-1 edges have been added to the MST.

Why V-1 edges?

A spanning tree on V vertices always has exactly V-1 edges. Once you have V-1 edges with no cycles in a connected graph, you have a spanning tree.

Kruskal Step-by-Step Example

Consider this graph with 5 vertices (0–4) and 7 edges:

Graph structure

Text

      2       3
  0 ----- 1 ----- 2
  |  \    |       |
  6    4  5       1
  |      \|       |
  3 ----- 4 ----- 2
       2      (weight on edges)

Edges sorted by weight: (1,2,1), (1,4,2), (3,4,2), (0,1,2→actually 2), (2,4,2), (0,3,6), (1,3,5)

Let us use a cleaner concrete example with edges:

(A–B, 1), (C–D, 2), (A–C, 3), (B–D, 4), (B–C, 5), (A–D, 6)

Kruskal trace

Text

Graph:  A ---1--- B
        |  \     |
        3    5   4
        |      \ |
        C ---2--- D

Sorted edges: (A-B,1), (C-D,2), (A-C,3), (B-D,4), (B-C,5), (A-D,6)

Step 1: Pick (A-B, 1)  → find(A)=A, find(B)=B → different → ADD
        MST: {A-B}   Components: {A,B} {C} {D}

Step 2: Pick (C-D, 2)  → find(C)=C, find(D)=D → different → ADD
        MST: {A-B, C-D}  Components: {A,B} {C,D}

Step 3: Pick (A-C, 3)  → find(A)=A, find(C)=C → different → ADD
        MST: {A-B, C-D, A-C}  Components: {A,B,C,D}
        V-1 = 3 edges added → DONE!

Step 4: (B-D, 4) — skipped (would complete cycle, same component)

MST total weight: 1 + 2 + 3 = 6

Kruskal JavaScript Implementation

The key data structure is Union-Find (covered in depth on the Union-Find page). Here is a complete, self-contained implementation:

kruskal.js

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 compression
    }
    return this.parent[x];
  }

  union(x, y) {
    const rx = this.find(x);
    const ry = this.find(y);
    if (rx === ry) return false; // already connected — would form a cycle

    // union by rank: attach smaller tree under larger
    if (this.rank[rx] < this.rank[ry]) {
      this.parent[rx] = ry;
    } else if (this.rank[rx] > this.rank[ry]) {
      this.parent[ry] = rx;
    } else {
      this.parent[ry] = rx;
      this.rank[rx]++;
    }
    return true;
  }
}

/**
 * @param {number}     n      - number of vertices (0-indexed)
 * @param {number[][]} edges  - [[u, v, weight], ...]
 * @returns {{ mstEdges: number[][], totalWeight: number }}
 */
function kruskal(n, edges) {
  // Step 1: sort edges by weight ascending
  edges.sort((a, b) => a[2] - b[2]);

  const uf         = new UnionFind(n);
  const mstEdges   = [];
  let   totalWeight = 0;

  // Step 2: greedily add edges that don't form a cycle
  for (const [u, v, w] of edges) {
    if (uf.union(u, v)) {       // returns true if u and v were in different components
      mstEdges.push([u, v, w]);
      totalWeight += w;
      if (mstEdges.length === n - 1) break; // MST is complete
    }
  }

  // If mstEdges.length < n-1, the graph is disconnected (no spanning tree)
  return { mstEdges, totalWeight };
}

// Example
const n = 4;
const edges = [
  [0, 1, 1],  // A-B
  [2, 3, 2],  // C-D
  [0, 2, 3],  // A-C
  [1, 3, 4],  // B-D
  [1, 2, 5],  // B-C
  [0, 3, 6],  // A-D
];

const { mstEdges, totalWeight } = kruskal(n, edges);
console.log('MST edges:', mstEdges);
console.log('Total weight:', totalWeight);

MST edges: [ [0,1,1], [2,3,2], [0,2,3] ]
Total weight: 6

Time and Space Complexity

Sorting edges dominates: **O(E log E)**. Since E ≤ V², this is also O(E log V). Each Union-Find operation is nearly O(1) amortized with path compression + union by rank. Space is O(V + E) for the DSU and edge list.

Prim's Algorithm

Prim's algorithm takes a local view: start from any vertex, and repeatedly extend the MST by adding the cheapest edge that connects a vertex already in the MST to a vertex not yet in the MST. It grows the tree one vertex at a time.

Initialize: mark any starting vertex as visited; push all its edges into a min-heap.
While the heap is not empty and the MST has fewer than V vertices:
— Pop the minimum-weight edge (u, v, weight) from the heap.
— If v is already in the MST, skip (stale entry).
— Otherwise, add the edge to the MST, mark v as visited.
— Push all edges from v to unvisited neighbors into the heap.
Stop when V-1 edges have been added.

Lazy vs Eager Prim

The implementation below uses the **lazy** variant — we push stale entries into the heap and skip them when popped. The eager variant uses a decrease-key operation (fibonacci heap) for O(E + V log V), but is much harder to implement. For interviews, the lazy variant is standard.

Prim Step-by-Step Example

Prim trace (same graph as above)

Text

Graph:  A ---1--- B
        |  \     |
        3    5   4
        |      \ |
        C ---2--- D

Start at vertex A. MST = {}, visited = {A}
Heap: [(1, A-B), (3, A-C), (5, A-... wait, A-D=6)]

Step 1: Pop (1, A-B) → B not visited → ADD A-B
        MST = {A-B}, visited = {A, B}
        Push B's edges: (4, B-D), (5, B-C)
        Heap: [(2, C-D... not yet), (3, A-C), (4, B-D), (5, B-C)]
        Actually heap: [(3, A-C), (4, B-D), (5, B-C), (6, A-D)]

Step 2: Pop (3, A-C) → C not visited → ADD A-C
        MST = {A-B, A-C}, visited = {A, B, C}
        Push C's edges: (2, C-D), (5, B-C already handled)
        Heap: [(2, C-D), (4, B-D), (5, B-C), (6, A-D)]

Step 3: Pop (2, C-D) → D not visited → ADD C-D
        MST = {A-B, A-C, C-D}, visited = {A, B, C, D}
        V-1 = 3 edges → DONE!

MST total weight: 1 + 3 + 2 = 6  ✓ same as Kruskal

Prim JavaScript Implementation

JavaScript does not have a built-in min-heap, so we implement a minimal one. In interviews it is common to use a sorted array as a priority queue for clarity:

prim.js

// Minimal binary min-heap for [cost, node] pairs
class MinHeap {
  constructor() { this.heap = []; }

  push(item) {
    this.heap.push(item);
    this._bubbleUp(this.heap.length - 1);
  }

  pop() {
    const top  = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this._sinkDown(0);
    }
    return top;
  }

  get size() { return this.heap.length; }

  _bubbleUp(i) {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.heap[parent][0] <= this.heap[i][0]) break;
      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
      i = parent;
    }
  }

  _sinkDown(i) {
    const n = this.heap.length;
    while (true) {
      let smallest = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < n && this.heap[l][0] < this.heap[smallest][0]) smallest = l;
      if (r < n && this.heap[r][0] < this.heap[smallest][0]) smallest = r;
      if (smallest === i) break;
      [this.heap[smallest], this.heap[i]] = [this.heap[i], this.heap[smallest]];
      i = smallest;
    }
  }
}

/**
 * @param {number}     n     - number of vertices (0-indexed)
 * @param {number[][]} adj   - adjacency list: adj[u] = [[v, weight], ...]
 * @returns {{ mstEdges: number[][], totalWeight: number }}
 */
function prim(n, adj) {
  const visited     = new Array(n).fill(false);
  const mstEdges    = [];
  let   totalWeight = 0;

  // Start from vertex 0; push [weight, from, to]
  const heap = new MinHeap();
  heap.push([0, -1, 0]); // [cost, parent, node]  (-1 = no parent for start)

  while (heap.size > 0 && mstEdges.length < n - 1) {
    const [cost, from, node] = heap.pop();

    if (visited[node]) continue; // stale entry — skip
    visited[node] = true;

    if (from !== -1) {
      mstEdges.push([from, node, cost]);
      totalWeight += cost;
    }

    // Explore neighbors
    for (const [neighbor, weight] of adj[node]) {
      if (!visited[neighbor]) {
        heap.push([weight, node, neighbor]);
      }
    }
  }

  return { mstEdges, totalWeight };
}

// Build adjacency list for the same example graph
// A=0, B=1, C=2, D=3
const n = 4;
const adj = [
  [[1, 1], [2, 3], [3, 6]],  // A: connects to B(1), C(3), D(6)
  [[0, 1], [3, 4], [2, 5]],  // B: connects to A(1), D(4), C(5)
  [[0, 3], [3, 2], [1, 5]],  // C: connects to A(3), D(2), B(5)
  [[2, 2], [1, 4], [0, 6]],  // D: connects to C(2), B(4), A(6)
];

const { mstEdges, totalWeight } = prim(n, adj);
console.log('MST edges:', mstEdges);
console.log('Total weight:', totalWeight);

MST edges: [ [0,1,1], [0,2,3], [2,3,2] ]
Total weight: 6

Time Complexity

With a binary heap: **O(E log V)**. Each edge is pushed to the heap at most once, and each heap operation is O(log V) since the heap size is bounded by the number of edges from a vertex. Space: O(V + E).

Kruskal vs Prim — Comparison

Property	Kruskal's	Prim's
Approach	Edge-based (global sort)	Vertex-based (greedy grow)
Data structure	Union-Find + sorted edges	Min-heap (priority queue)
Time complexity	O(E log E)	O(E log V) with binary heap
Space complexity	O(V + E)	O(V + E)
Best for	Sparse graphs, edge list input	Dense graphs, adjacency matrix
Implementation difficulty	Medium (needs Union-Find)	Medium (needs min-heap)
Handles disconnected graphs	Yes (detects disconnection)	No (must check visited count)
Starts from	Any edge (global)	A specific start vertex

Choose Kruskal when:

The graph is sparse (E is close to V) — sorting fewer edges is fast.
You already have an edge list.
You need to detect whether the graph is connected (check if you got V-1 edges).

Choose Prim when:

The graph is dense (E is close to V²) — Prim visits each vertex once and processes edges as it goes, without sorting the entire edge list upfront.
You have an adjacency matrix — accessing neighbors directly by row is O(V), so Prim with an O(V²) matrix variant is efficient.

Classic Problems

1. Min Cost to Connect All Points (LeetCode 1584)

Given an array of points on a 2D plane, find the minimum cost to connect all points. The cost to connect two points is their Manhattan distance: |xi - xj| + |yi - yj|. This is a classic MST problem where every pair of points is a potential edge.

lc-1584-min-cost-connect-points.js

// Prim's approach — O(n²) time, ideal for dense complete graph
function minCostConnectPoints(points) {
  const n = points.length;
  if (n === 1) return 0;

  // minCost[i] = cheapest edge connecting vertex i to the current MST
  const minCost = new Array(n).fill(Infinity);
  const inMST   = new Array(n).fill(false);
  minCost[0]    = 0;

  let totalCost = 0;

  for (let added = 0; added < n; added++) {
    // Pick the vertex not yet in MST with the smallest minCost (O(n) scan)
    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 minCost for all neighbors of 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]);
        minCost[v] = Math.min(minCost[v], dist);
      }
    }
  }

  return totalCost;
}

console.log(minCostConnectPoints([[0,0],[2,2],[3,10],[5,2],[7,0]])); // 20
console.log(minCostConnectPoints([[3,12],[-2,5],[-4,1]]));           // 18

20
18

O(n²) Prim vs heap-based Prim

For a complete graph where E = n*(n-1)/2, the heap-based Prim would be O(n² log n). The O(n²) array-scan Prim is actually faster here — scanning a dense adjacency list is cheaper than heap bookkeeping. Use the simple O(n²) version for this problem.

2. Optimize Water Distribution in a Village (LeetCode 1168)

Each house can either dig a well (cost wells[i]) or connect to another house via a pipe (cost pipes[i]). Find the minimum total cost to supply water to all houses.

Key insight: Add a virtual node 0 representing an infinite water source. Add an edge from node 0 to each house i with weight wells[i-1]. Then the problem reduces to finding the MST on this augmented graph.

lc-1168-optimize-water-distribution.js

function minCostToSupplyWater(n, wells, pipes) {
  // Build the augmented edge list
  // Virtual node 0 → house i has cost wells[i-1]
  const edges = [];

  for (let i = 0; i < n; i++) {
    edges.push([0, i + 1, wells[i]]); // virtual node 0 to house i+1
  }
  for (const [house1, house2, cost] of pipes) {
    edges.push([house1, house2, cost]);
  }

  // Kruskal's on the augmented graph (n+1 nodes: 0..n)
  edges.sort((a, b) => a[2] - b[2]);

  // Union-Find
  const parent = Array.from({ length: n + 1 }, (_, i) => i);
  const rank   = new Array(n + 1).fill(0);

  function find(x) {
    if (parent[x] !== x) parent[x] = find(parent[x]);
    return parent[x];
  }

  function union(x, y) {
    const rx = find(x), ry = find(y);
    if (rx === ry) return false;
    if (rank[rx] < rank[ry]) parent[rx] = ry;
    else if (rank[rx] > rank[ry]) parent[ry] = rx;
    else { parent[ry] = rx; rank[rx]++; }
    return true;
  }

  let totalCost  = 0;
  let edgesAdded = 0;

  for (const [u, v, cost] of edges) {
    if (union(u, v)) {
      totalCost  += cost;
      edgesAdded++;
      if (edgesAdded === n) break; // n+1 nodes → n edges needed
    }
  }

  return totalCost;
}

console.log(minCostToSupplyWater(3, [1,2,2], [[1,2,1],[2,3,1]])); // 3
console.log(minCostToSupplyWater(2, [1,1], [[1,2,2]]));            // 2

3
2

3. Remove Max Number of Edges to Keep Graph Fully Traversable (LeetCode 1579)

Alice uses type-1 and type-3 edges; Bob uses type-2 and type-3 edges. Remove maximum edges while keeping both Alice and Bob able to traverse all nodes.

Key insight: Type-3 (shared) edges should be added first — they help both Alice and Bob simultaneously. Then add type-1 edges for Alice and type-2 for Bob. Use two separate Union-Find structures. Any edge that doesn't reduce the number of connected components can be removed.

lc-1579-remove-max-edges.js

function maxNumEdgesToRemove(n, edges) {
  class UnionFind {
    constructor(n) {
      this.parent    = Array.from({ length: n + 1 }, (_, i) => i);
      this.rank      = new Array(n + 1).fill(0);
      this.components = n; // track connected components
    }
    find(x) {
      if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
      return this.parent[x];
    }
    union(x, y) {
      const rx = this.find(x), ry = this.find(y);
      if (rx === ry) return false;
      if (this.rank[rx] < this.rank[ry]) this.parent[rx] = ry;
      else if (this.rank[rx] > this.rank[ry]) this.parent[ry] = rx;
      else { this.parent[ry] = rx; this.rank[rx]++; }
      this.components--;
      return true;
    }
    isConnected() { return this.components === 1; }
  }

  const alice = new UnionFind(n);
  const bob   = new UnionFind(n);
  let removed = 0;

  // Phase 1: add type-3 edges (shared) first — maximize benefit
  for (const [type, u, v] of edges) {
    if (type === 3) {
      const addedAlice = alice.union(u, v);
      const addedBob   = bob.union(u, v);
      // If neither benefited, this edge is redundant
      if (!addedAlice && !addedBob) removed++;
    }
  }

  // Phase 2: add type-1 (Alice only) and type-2 (Bob only)
  for (const [type, u, v] of edges) {
    if (type === 1) {
      if (!alice.union(u, v)) removed++;
    } else if (type === 2) {
      if (!bob.union(u, v)) removed++;
    }
  }

  // Check if both graphs are fully connected
  if (!alice.isConnected() || !bob.isConnected()) return -1;

  return removed;
}

console.log(maxNumEdgesToRemove(4,
  [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]])); // 2
console.log(maxNumEdgesToRemove(4,
  [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]));                  // 0
console.log(maxNumEdgesToRemove(4,
  [[3,2,3],[1,1,2],[2,3,4]]));                           // -1

2
0
-1

Key Takeaways

MST connects all V vertices with exactly V-1 edges and minimum total weight.
Kruskal's sorts edges globally and uses Union-Find for cycle detection — best for sparse graphs.
Prim's grows the MST greedily from a start vertex using a min-heap — best for dense graphs.
Both algorithms run in O(E log E) / O(E log V) time and produce the same MST weight.
A virtual node trick (like LeetCode 1168) often reduces a seemingly complex problem to a standard MST.
LeetCode 1579's two-DSU pattern is a classic: add shared edges first, then exclusive edges.
If the graph is disconnected, Kruskal will produce a minimum spanning forest (one tree per component).