Prim's MST

Overview

What this concept solves

Prim's algorithm grows a Minimum Spanning Tree from a single seed. Where Kruskal sorts all edges up front and walks them globally, Prim starts at one node and keeps pulling in the cheapest edge from the current tree to a new outside node. It's literally Dijkstra's algorithm with a different key — instead of 'distance from source,' the key is 'cheapest edge connecting this node to the current tree.'

The algorithm: pick any starting node and put it in the tree. Maintain a min-priority queue of every edge crossing the cut between the tree and the rest of the graph. Pop the cheapest such edge — that edge connects the tree to one new node. Add the new node to the tree, push its outgoing edges into the queue. Repeat until the tree has V nodes (or V-1 edges).

Prim's and Kruskal's both compute MSTs and both are justified by the cut property — but they explore the graph in opposite directions. Kruskal considers edges globally, in weight order. Prim grows a connected region locally, like ink spreading on paper. For dense graphs, Prim's tighter local frontier wins. For sparse graphs, Kruskal's global sort wins.

Mechanics

How it works

The algorithm in five lines

Put any starting node s into the tree. Mark it visited.
Push every edge (s, v, w) into a min-priority queue keyed by w.
Loop: pop the cheapest edge (u, v, w) from the queue. If v is already in the tree, discard the edge (it would form a cycle). Otherwise add v to the tree and add (u, v) to the MST.
Push every edge from the newly-added v to an outside node into the queue.
Stop when the tree has V nodes.

Why the greedy choice is safe (same cut property)

At each step, the 'cut' is (tree nodes, outside nodes). The priority queue's minimum is the cheapest edge crossing that cut.
Cut property: the cheapest edge crossing any cut is in some MST. So adding it is safe.
After V-1 such additions, every node is in the tree and you have an MST.
Same property that justifies Kruskal — Prim just considers cuts in a fixed order (always 'tree vs. outside') instead of Kruskal's 'whichever two components this edge bridges'.

Prim's vs Dijkstra's

Both are 'pop the cheapest frontier edge, add the node, push its new edges' algorithms. The only difference is the priority: Dijkstra uses distance-from-source dist[u] + w(u,v), Prim uses just the edge weight w(u,v). That's why Prim doesn't care about path length — only the cost of the one new edge.

Eager Prim removes stale entries

The straight 'push edge per neighbour' implementation can have multiple entries for the same destination node. Eager Prim keeps only the cheapest current edge to each outside node — slightly more code, but the heap shrinks from O(E) to O(V), giving O(E log V) instead of O(E log E). Most production implementations use the eager form.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › Prim's MST

About this simulation

Eight nodes, ten weighted edges, and a min-priority queue. Press Play to watch Prim grow the MST from a seed node, always pulling in the cheapest edge that reaches a new vertex. Step / Back advance one node-addition at a time. Start picks a different seed so you can confirm the MST cost stays the same.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Play through one MST build

Press Play from the default seed. Watch the tree grow ring-by-ring: each step, the cheapest cut-crossing edge fires and pulls in one new node. The heap on the right reorders as new edges enter and stale ones get skipped.

try 02

Step through one cut-edge at a time

Hit Step to pop the next cheapest edge from the heap. If both endpoints are already in the tree, the prototype shows the skip badge (stale entry). Otherwise the new node joins the tree. Back rewinds the addition.

try 03

Try a different seed node

Switch Start from A to F. The growth path and the order of node additions change completely — but check the Total weight stat: it stays the same. The MST is structurally fixed by the edge weights; the seed only changes the build order.

try 04

Compare with Kruskal

Open Kruskal on the same graph. You'll see the same set of edges chosen (assuming unique weights), in a totally different order: Kruskal walks cheapest-first regardless of location; Prim walks cheapest-from-the-current-frontier. Same destination, different path.

In practice

When to use it — and what you give up

When it's the right tool

Dense graphs — Prim with an array-based key is O(V²), which beats Kruskal's O(E log E) ≈ O(V² log V) when E ≈ V².
You have a natural seed node — network design from a hub, dendrogram clustering from a centroid, mesh generation around a vertex.
You don't have the whole edge set up front — Prim only needs each node's outgoing edges as that node enters the tree, so it works on graphs with a 'lazy-load' adjacency list.
Inside Dijkstra-flavoured infrastructure — if you've already got a binary heap and a relaxation loop, Prim is one line change away.
As a sub-step in approximation algorithms — the 2-approximation for metric Steiner tree starts with an MST built via Prim.

When to reach for something else

Sparse graphs — use Kruskal. Its O(E log E) is dominated by the sort, which is fine when E is small.
Edges already sorted — Kruskal can skip the sort and run in O(E · α(V)).
*You need to detect cycles for other reasons too* — Kruskal's DSU gives you connected components for free.
You only need part of the MST — Kruskal-with-early-stop is simpler if you want the K cheapest tree edges.

Pros

O((V + E) log V) with a binary heap, O(V²) with an array — well-suited to dense graphs.
Grows locally — useful when you want the partial tree at any point, e.g. visualisations or incremental layouts.
No DSU needed — just a visited set and a priority queue.
Dijkstra-shaped — easy to layer on top of existing shortest-path code.
Eager variant has the lowest priority-queue churn of the MST algorithms.

Cons

Needs a heap and a visited set — more bookkeeping than Kruskal's DSU.
Less natural for streaming edges — Prim wants to know each node's full neighbourhood as that node is added.
Tie-handling depends on heap order — same caveat as Kruskal: non-unique MSTs are visited in different orders.
Seed-dependent visit order — the final MST is the same, but the path the algorithm took to build it varies. Debugging is harder.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

prim.ts

// Prim's MST — lazy variant with a binary heap.
// Push every cut-crossing edge; skip stale entries on pop.
type Edge = { to: number; w: number };
type HeapEntry = [number, number, number];   // [weight, from, to]

function prim(graph: Map<number, Edge[]>, start: number): HeapEntry[] {
  const inTree = new Set<number>([start]);
  const heap: HeapEntry[] = [];

  // Seed: push every edge from start.
  for (const { to, w } of graph.get(start) ?? []) heap.push([w, start, to]);
  heap.sort((a, b) => a[0] - b[0]);   // real code: min-heap

  const mst: HeapEntry[] = [];
  while (heap.length > 0 && mst.length < graph.size - 1) {
    const e = heap.shift()!;          // real code: heap.pop()
    const [w, u, v] = e;
    if (inTree.has(v)) continue;      // stale — cycle would form

    inTree.add(v);
    mst.push(e);

    // Push every edge from v to a not-yet-in-tree node.
    for (const { to, w: ew } of graph.get(v) ?? []) {
      if (!inTree.has(to)) {
        heap.push([ew, v, to]);
        heap.sort((a, b) => a[0] - b[0]);    // real code: heap.push()
      }
    }
  }
  return mst;
}

// Real implementations: replace shift/sort with a proper binary heap
// (Python: heapq, Java: PriorityQueue, C++: priority_queue with reverse comparator).
// Eager variant: keep only the cheapest current edge per outside node — O(V) heap entries.

References & further reading

6 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

What's the structural difference between Prim's and Dijkstra's algorithms?

question 02 / 03

Prim's algorithm computes the same MST regardless of the starting node. Why?

question 03 / 03

When pop returns an edge (u, v) whose destination `v` is already in the tree, what does the algorithm do?

0/3 answered