Prim's algorithm

Overview

Prim's algorithm also builds a minimum spanning tree, but grows a single tree outward from a start vertex. At each step it adds the cheapest edge that connects a vertex inside the tree to a vertex outside it, using a min-heap of candidate edges.

It resembles Dijkstra, except the heap key is the weight of the single connecting edge rather than the total distance from the source. For dense graphs, a simple O(V^2) version without a heap is often the fastest option.

When to use it

• Minimum spanning tree on a dense graph or complete graph (all pairs of points).
• The graph is given as an adjacency list or matrix rather than an edge list.
• You want to grow the tree incrementally from one vertex.

Problem patterns it solves

Where it is used in real software

Key terms

In-tree set

Vertices already connected by the growing tree.

Frontier edge

An edge from an in-tree vertex to an outside vertex.

key[v]

Cheapest known edge weight connecting v to the tree (dense version).

Lazy Prim

Push edges into the heap and skip those leading to in-tree vertices.

How it works, step by step

1. 1
   Start from any vertex

   Mark it in the tree; push its edges into a min-heap.

2. 2
   Pop the cheapest edge

   If it leads to a vertex already in the tree, skip it.

3. 3
   Add the new vertex

   Add the edge weight to the total, mark the vertex in the tree.

4. 4
   Push its edges

   Add edges from the new vertex to outside vertices.

5. 5
   Stop at V vertices

   The tree is complete; if the heap empties first, the graph is disconnected.

Prim from A on the same graph as Kruskal

Edges: A-B 1, B-C 4, A-C 3, C-D 2, B-D 5

Same MST weight, 6, as Kruskal, but built by expanding one tree. Remaining heap entries point to vertices already in the tree and are discarded.

Implementation

1// Lazy Prim with a heap (PriorityQueue from the Heap guide)2function prim(n, graph) { // graph[u] = [[v, w], ...]3  const inTree = new Array(n).fill(false);4  const heap = new PriorityQueue((a, b) => a[0] - b[0]);5  heap.push([0, 0]); // [weight, vertex]6  let total = 0, count = 0;7  while (heap.size && count < n) {8    const [w, u] = heap.pop();9    if (inTree[u]) continue;10    inTree[u] = true;11    total += w;12    count++;13    for (const [v, weight] of graph[u]) if (!inTree[v]) heap.push([weight, v]);14  }15  return count === n ? total : -1;16}17 18// O(V^2) dense Prim: best for complete graphs like 158419function minCostConnectPoints(points) {20  const n = points.length;21  const key = new Array(n).fill(Infinity);22  const inTree = new Array(n).fill(false);23  key[0] = 0;24  let total = 0;25  for (let step = 0; step < n; step++) {26    let u = -1;27    for (let v = 0; v < n; v++) if (!inTree[v] && (u === -1 || key[v] < key[u])) u = v;28    inTree[u] = true;29    total += key[u];30    for (let v = 0; v < n; v++) {31      if (inTree[v]) continue;32      const d = Math.abs(points[u][0] - points[v][0]) + Math.abs(points[u][1] - points[v][1]);33      if (d < key[v]) key[v] = d;34    }35  }36  return total;37}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Using dist[u] + w as the key.

  Fix: That is Dijkstra. Prim's key is only the connecting edge weight w.

• Not skipping in-tree vertices when popping.

  Fix: Lazy Prim leaves stale edges in the heap; check inTree first.

Interview questions

Practice problems