Prim's MST Algorithm

Build the minimum spanning tree of a weighted undirected graph by greedily extending a visited set with the lowest-weight crossing edge, achieving O(E log V) with a min-heap.

5 min read Level 3/5 #dsa#graph#mst

What you'll learn

Implement Prim's algorithm using a min-heap priority queue
Explain why Prim's always produces a minimum spanning tree
Compute the total MST weight from the priority queue extractions

A Minimum Spanning Tree (MST) of a weighted undirected graph is a spanning subgraph that connects all vertices with the minimum total edge weight and no cycles. MSTs appear in network design, cluster analysis, and approximation algorithms for NP-hard problems.

Prim’s algorithm grows the MST one edge at a time by always picking the cheapest edge that crosses the boundary between the current tree and the rest of the graph.

Algorithm Steps

Start from any seed vertex; mark it as in-tree.
Push all its edges onto a min-heap keyed by weight.
Pop the cheapest edge. If the destination is already in-tree, skip it.
Add the destination to the tree, push its outgoing edges onto the heap.
Repeat until the heap is empty or all vertices are in-tree.

// graph: Map<number, Array<{to: number, weight: number}>>  (undirected)
function primMST(graph, numVertices) {
  const inTree = new Set();
  const mstEdges = [];
  let totalWeight = 0;

  // [weight, from, to]
  const heap = [[0, -1, 0]]; // seed: vertex 0

  while (heap.length > 0 && inTree.size < numVertices) {
    heap.sort((a, b) => a[0] - b[0]);
    const [w, from, u] = heap.shift();

    if (inTree.has(u)) continue;
    inTree.add(u);
    if (from !== -1) {
      mstEdges.push([from, u, w]);
      totalWeight += w;
    }

    for (const { to: v, weight } of graph.get(u) ?? []) {
      if (!inTree.has(v)) heap.push([weight, u, v]);
    }
  }

  return { mstEdges, totalWeight };
}

// Undirected weighted graph
const g = new Map([
  [0, [{ to: 1, weight: 2 }, { to: 3, weight: 6 }]],
  [1, [{ to: 0, weight: 2 }, { to: 2, weight: 3 }, { to: 3, weight: 8 }, { to: 4, weight: 5 }]],
  [2, [{ to: 1, weight: 3 }, { to: 4, weight: 7 }]],
  [3, [{ to: 0, weight: 6 }, { to: 1, weight: 8 }, { to: 4, weight: 9 }]],
  [4, [{ to: 1, weight: 5 }, { to: 2, weight: 7 }, { to: 3, weight: 9 }]],
]);

const { mstEdges, totalWeight } = primMST(g, 5);
console.log(mstEdges);    // [[0,1,2],[1,2,3],[1,4,5],[0,3,6]]
console.log(totalWeight); // 16

Why It Works

Prim’s maintains a cut property: for any partition of vertices into in-tree and not-yet-in-tree, the minimum weight crossing edge is safe to add to the MST. Because the heap always provides the minimum crossing edge, each extraction is safe.

Complexity

Structure	Time	Space
Array (naive)	O(V²)	O(V)
Binary min-heap	O(E log V)	O(V)

Up Next

Kruskal’s algorithm reaches the same MST from the opposite direction — sorting all edges globally and using union-find to avoid cycles.

Kruskal's MST Algorithm →