Prim's Algorithm

How Prim's algorithm works

Maintain a set T of vertices already in the MST and a priority queue of candidate edges crossing from T to V \ T. Repeat V − 1 times: extract the cheapest crossing edge, add the new vertex to T, and update candidate weights for the new vertex's neighbors.

• Initialize: pick any start vertex s. Set key[s] = 0; key[v] = ∞ for all other v. Place all vertices in a min-priority-queue keyed by key[v].
• Extract: pull u with smallest key. Add u to MST. The edge of weight key[u] (if u ≠ s) connects u to its parent in the tree.
• Relax: for each neighbor v of u with weight w(u, v) < key[v], update key[v] = w(u, v) and parent[v] = u.
• Repeat until the priority queue is empty (all vertices in T).

The structure mirrors Dijkstra's shortest-path algorithm exactly — the only difference is the relaxation rule (Prim's uses edge weight; Dijkstra's uses distance from source).

Why it produces an optimal MST

The cut property: in a connected weighted graph with all edge weights distinct, for any cut (A, V \ A), the unique minimum-weight crossing edge is in every MST. Prim's invariant: after each step, the grown tree T is contained in some MST. Initially T = {s}, trivially in any MST. At each step, pick the minimum crossing edge from cut (T, V \ T) — the cut property says this edge is in some MST containing the partial T. Add it; invariant preserved. After V − 1 steps, T is a complete MST.

For graphs with repeated weights, the same argument gives "some MST" (not necessarily unique). Tie-breaking by edge id makes the choice deterministic.

JavaScript implementation (binary heap)

// Adjacency list: graph[u] = [[v, w], ...]
function primMST(graph, start = 0) {
  const n = graph.length;
  const key = new Array(n).fill(Infinity);
  const parent = new Array(n).fill(-1);
  const inMST = new Array(n).fill(false);
  key[start] = 0;
  const pq = new MinHeap();           // (key, vertex)
  pq.push([0, start]);
  let totalWeight = 0;
  while (pq.size() > 0) {
    const [k, u] = pq.pop();
    if (inMST[u]) continue;            // stale entry
    inMST[u] = true;
    totalWeight += k;
    for (const [v, w] of graph[u]) {
      if (!inMST[v] && w < key[v]) {
        key[v] = w;
        parent[v] = u;
        pq.push([w, v]);              // lazy decrease-key
      }
    }
  }
  return { parent, totalWeight };
}

The "lazy decrease-key" trick — push duplicate entries instead of decreasing — keeps the heap simple and runs in O(E log E) = O(E log V), since E ≤ V².

Python implementation

import heapq

def prim_mst(graph, start=0):
    n = len(graph)
    key = [float('inf')] * n
    parent = [-1] * n
    in_mst = [False] * n
    key[start] = 0
    pq = [(0, start)]
    total = 0
    while pq:
        k, u = heapq.heappop(pq)
        if in_mst[u]:
            continue
        in_mst[u] = True
        total += k
        for v, w in graph[u]:
            if not in_mst[v] and w < key[v]:
                key[v] = w
                parent[v] = u
                heapq.heappush(pq, (w, v))
    return parent, total

Dense O(V²) variant — no heap

For dense graphs the binary-heap version is wasteful. A simpler O(V²) loop scans all vertices each iteration to find the next minimum-key one, then relaxes its row of the adjacency matrix:

// Adjacency matrix: w[u][v] = weight, Infinity if no edge
function primDense(w, start = 0) {
  const n = w.length;
  const key = new Array(n).fill(Infinity);
  const parent = new Array(n).fill(-1);
  const inMST = new Array(n).fill(false);
  key[start] = 0;
  for (let i = 0; i < n; i++) {
    let u = -1;
    for (let v = 0; v < n; v++) {
      if (!inMST[v] && (u === -1 || key[v] < key[u])) u = v;
    }
    inMST[u] = true;
    for (let v = 0; v < n; v++) {
      if (!inMST[v] && w[u][v] < key[v]) {
        key[v] = w[u][v];
        parent[v] = u;
      }
    }
  }
  return { parent };
}

For V = 5000 dense graphs (~25M edges), this beats the heap version: 5000² = 25M operations versus 25M log 5000 ≈ 300M operations.

Prim's vs Kruskal's vs Borůvka's

Algorithm	Strategy	Time (binary heap / DSU)	Best for
Prim's	Grow tree from one vertex	O(E log V) or O(V²) dense	Dense graphs, single-tree growth
Kruskal's	Globally sort edges, use DSU	O(E log E) = O(E log V)	Sparse graphs, edge-list input
Borůvka's	Each component picks its lightest edge in parallel	O(E log V)	Parallel/distributed setting
Karger-Klein-Tarjan (1995)	Randomized linear-time MST	O(E + V) expected	Theoretical interest

Famous Prim's-style problems

Minimum-cost network cabling

Connect n cities with bidirectional cables of given installation cost. Build the complete weighted graph, run Prim's, total weight is the minimum cabling cost. For n = 100 cities Prim's dense runs in 100² = 10⁴ operations — instantaneous.

k-clustering by MST

function kClusters(graph, k) {
  const { mstEdges } = primAndReturnEdges(graph);
  mstEdges.sort((a, b) => b.weight - a.weight);   // heaviest first
  const cut = mstEdges.slice(0, k - 1);            // remove k−1 heaviest
  // Remaining MST forms k connected components — the clusters
  return cut;
}

Build the MST, then cut the k − 1 heaviest edges. Remaining trees are the k clusters. This minimizes the maximum-spacing objective (Kleinberg-Tardos chapter 4).

TSP lower bound

Any Hamiltonian cycle of an n-vertex graph contains a spanning tree (drop any one edge). So MST weight ≤ TSP cost. Christofides' algorithm uses MST + min-weight perfect matching of odd-degree vertices to give a 1.5-approximation for metric TSP.

Why Prim's matters

• Network backbone design. MST = telecommunications backbone, minimum-cost pipeline, road system planning. The 1956 paper by Prim was motivated by the Bell System's question of how to lay cables economically.
• Cluster analysis. MST-based hierarchical clustering (single-linkage) is the duality of Kruskal's algorithm. Cutting heaviest k − 1 edges yields k clusters minimizing maximum intra-cluster spacing.
• Approximation algorithms. MST gives a 2-approximation to TSP for metric graphs; combined with matching, Christofides achieves 1.5-approximation. Both rely on the existence of an efficient MST algorithm.
• VLSI and PCB routing. Connect chip pads with minimum total wire length; rectilinear-MST variants (Steiner trees) build on Prim's and Kruskal's primitives.
• Image segmentation. Felzenszwalb-Huttenlocher (2004) builds MST on the pixel-similarity graph and merges segments while edges remain "internal." Linear time after MST.
• Phylogenetic trees. Single-linkage clustering on distance matrices yields evolutionary trees — Prim's algorithm under another name in computational biology.
• Robot exploration / SLAM. Build a minimum-coverage map by visiting nearest unknown frontiers; Prim's-style frontier expansion guides exploration.

Common misconceptions

• "Always slower than Kruskal's." On dense graphs (E close to V²), Prim's dense O(V²) beats Kruskal's O(E log E) = O(V² log V) by a log factor. Density determines which wins.
• "Needs sorted edges." Kruskal's sorts edges globally. Prim's needs only local edge enumeration around the current tree — adjacency lists are enough.
• "Start vertex affects MST weight." The MST weight is unique (assuming distinct edge weights). Choice of start affects only the order of edges added, not the total or the resulting tree shape (when weights are distinct).
• "Decrease-key is essential." The "lazy decrease-key" trick — push duplicates and skip stale entries on extract — gives O(E log V) without explicit decrease-key support. It's what most textbook implementations do.
• "Works on directed graphs." Plain MST is for undirected graphs. The directed analogue (minimum spanning arborescence) is Edmonds-Chu-Liu, a different algorithm with O(VE) time.
• "Identical to Dijkstra's." Same skeleton, different relaxation. Dijkstra's: dist[v] = min(dist[v], dist[u] + w). Prim's: key[v] = min(key[v], w). Sums vs single edges — different objectives, different correctness proofs.
• "Only one MST exists." If edge weights are distinct, the MST is unique. With ties, multiple MSTs may exist with the same total weight.