cf.completefrontend
GRAPHS · ADVANCED

Prim's algorithm (minimum spanning tree)

Connect every node with the lowest total edge cost by growing one tree outward, always adding the cheapest edge that reaches a new node.

Time O(e log e)Space O(n + e)2 practice problemsStep-through picture

The idea

A spanning tree of a connected graph is a set of edges that connects every node with no loops. With n nodes it always has exactly n - 1 edges. A minimum spanning tree (MST) is a spanning tree with the lowest total edge cost. Think of laying cable so every building is connected while spending as little as possible.

Prim's algorithm grows the tree from one node. At every step it looks at all edges that go from a node inside the tree to a node outside it, and adds the cheapest one. That new node joins the tree, and its edges become new options.

A min-heap holds the candidate edges as [weight, node] pairs, so finding the cheapest is fast. Edges that lead to a node already in the tree are skipped when they come out of the heap.

An everyday example

Spreading a garden hose network from one tap

You water a garden from one tap. You can lay hoses between plants, and longer hoses cost more. You always lay the cheapest hose that reaches a plant that doesn't have water yet. As each plant gets water, it becomes a new spot to run hoses from. When every plant has water, you've spent as little as possible.

How the example maps to the code
In the exampleIn the code
Plants with waterNodes with inTree[node] === true
Hoses you could lay next[w, next] entries in the heap
Laying the cheapest useful hosepop(heap) and adding its weight to total
A hose to a plant that already has waterAn entry skipped by if (inTree[node]) continue

From the slow way to prim's algorithm (minimum spanning tree)

  1. Start with the obvious way: list every spanning tree and keep the cheapest. A graph where every pair of nodes is linked has n to the power n - 2 spanning trees: 100 million for just 10 nodes. That's far too many to check.
  2. Here's the fact that saves us, called the cut property. Split the nodes into any two sides. The cheapest edge that crosses between the sides belongs to some cheapest spanning tree. So we can commit to that edge right away and never regret it.
  3. Use the split "nodes in the tree so far" against "everything else". The cheapest crossing edge is safe to add. Adding it moves one node into the tree, which makes a new split, so repeat until all n nodes are in. Scanning every edge each time to find the cheapest crossing one would cost about n · e steps.
  4. Instead, push each new node's edges into a min-heap as it joins, keyed by their weight. The heap hands back the cheapest edge offered so far. If its far end is already in the tree, it doesn't cross the split anymore, so skip it. That loop is Prim's algorithm.

How it works

  1. Build an undirected graph with [neighbor, weight] pairs.
  2. Start with node 0: push [0, 0], meaning "reach node 0 for cost 0".
  3. Pop the cheapest entry [weight, node]. If node is already in the tree, skip it.
  4. Otherwise add node to the tree, add weight to total, and count it in added.
  5. Push every edge from node to a node not yet in the tree.
  6. Stop when all n nodes are added. If the heap runs out first, the graph isn't connected: return -1.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function primMst(n, edges) {
  2. const graph = Array.from({ length: n }, () => []);
  3. for (const [a, b, weight] of edges) {
  4. graph[a].push([b, weight]);
  5. graph[b].push([a, weight]);
  6. }
  7. const inTree = new Array(n).fill(false);
  8. const heap = [[0, 0]];
  9. let total = 0;
  10. let added = 0;
  11. while (heap.length > 0 && added < n) {
  12. const [weight, node] = pop(heap);
  13. if (inTree[node]) continue;
  14. inTree[node] = true;
  15. total += weight;
  16. added++;
  17. for (const [next, w] of graph[node]) {
  18. if (!inTree[next]) push(heap, [w, next]);
  19. }
  20. }
  21. return added === n ? total : -1;
  22. }
  24. function push(heap, item) {
  25. heap.push(item);
  26. let i = heap.length - 1;
  27. while (i > 0 && heap[(i - 1) >> 1][0] > heap[i][0]) {
  28. const parent = (i - 1) >> 1;
  29. [heap[parent], heap[i]] = [heap[i], heap[parent]];
  30. i = parent;
  31. }
  32. }
  34. function pop(heap) {
  35. const top = heap[0];
  36. const last = heap.pop();
  37. if (heap.length === 0) return top;
  38. heap[0] = last;
  39. let i = 0;
  40. while (true) {
  41. let small = i;
  42. for (const child of [2 * i + 1, 2 * i + 2]) {
  43. if (child < heap.length && heap[child][0] < heap[small][0]) small = child;
  44. }
  45. if (small === i) return top;
  46. [heap[small], heap[i]] = [heap[i], heap[small]];
  47. i = small;
  48. }
  49. }

How fast it is

TimeO(e log e)
Extra memoryO(n + e)

Each edge is pushed at most twice, and each heap step costs O(log e). The graph and the heap hold every edge.

  • Best caseO(n + e)

    The graph is a simple chain 0-1-2-...: the heap never holds more than one entry, so each heap step is constant and building graph dominates.

  • Average caseO(e log e)

    A typical connected graph, where most edges get pushed and each heap step costs about log e.

  • Worst caseO(e log e)

    A dense graph where every pair of nodes has an edge, so about n² / 2 edges each get pushed and many are popped and skipped.

Common mistakes

  • Marking a node as in the tree when it is pushed rather than when it is popped. A cheaper edge to it might come later.
  • Adding the edge weight before checking inTree, so skipped edges are still paid for.
  • Forgetting to check that every node was added, and returning a total for a graph that isn't connected.
  • Confusing it with Dijkstra's algorithm. Prim compares single edge weights w; Dijkstra compares total path costs d + w.

When to use it

Look for these clues in a problem:

  • The question asks for the cheapest way to connect everything: cables, roads, pipes, or links.
  • Every node must end up connected, and the total cost should be as small as possible.
  • The graph is dense, or given as points where every pair can be connected.
  • There is no start or goal; only the total cost of connecting matters.

Check yourself

Answer each one in your head first, then open it.

Why can a node be pushed several times but added only once?

Each tree node that touches it pushes its own edge to it. The first entry popped is the cheapest; the rest are skipped by inTree.

How many edges does the finished tree have?

Exactly n - 1, one for each node that joined after the first.

Why do negative weights not break Prim's algorithm?

Its proof only compares edges crossing a split. It never adds up path costs, so a negative weight is just a very cheap edge.

In the trace, why was the edge 0-1 costing 7 never used?

Node 1 joined first through 1-2 costing 2. When [7, 1] was popped, node 1 was already in the tree, so it was skipped.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 2 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule: the edges chosen so far, one for each node that joined after node 0, are all part of some minimum spanning tree T. With no edges chosen, that's true for any minimum spanning tree.

Each step keeps the rule, by an exchange argument. Every edge from a tree node to an outside node was pushed when its tree end joined, and the heap returns the smallest entry, skipping the ones whose far end is already in. So the popped edge e is a cheapest edge crossing from the tree to the rest. If T doesn't contain e, adding e to T makes a loop, and that loop must cross the split a second time through some edge f. Since e is a cheapest crossing edge, f costs at least as much, so swapping f for e gives a spanning tree that costs no more and contains every chosen edge.

Each pop that isn't skipped adds one new node, so the loop ends after n additions or when the heap runs out. With n nodes added, the n - 1 chosen edges form a spanning tree inside a minimum spanning tree, so they are one. If the heap runs out first, some node can't be reached, and it returns -1.

Going deeper

3 more ideas

Why the cheapest crossing edge is always safe

Split the nodes into those in the tree and those outside. Any spanning tree must use at least one edge that crosses between the two sides. If a cheapest spanning tree didn't use the cheapest crossing edge e, adding e would make a loop that crosses the split twice; removing the other crossing edge in that loop gives a tree that costs no more. So some cheapest tree contains e, and adding it is never a mistake. This is called the cut property.

Cost, and the version without a heap

With a heap, each edge is pushed at most twice and each push or pop costs O(log e), so the time is O(e log e). When every pair of points can be connected (a complete graph, with about n² edges), a version without a heap is better: keep a minCost array for nodes outside the tree and scan it for the smallest each round. That's O(n²) with no need to list the edges.

Ties and disconnected graphs

When several edges have the same cost, there can be several different cheapest trees, but they all have the same total. So asking for the total gives a unique answer. If the graph has more than one piece, no spanning tree exists; check that all n nodes were added.

Work it by hand

Every step in a table, with why

Six nodes, nine edges. Three heap entries go out of date and get skipped before the last node joins.

n = 6, edges = [[0,1,7], [0,2,3], [1,2,2], [1,3,6], [2,3,8], [2,4,4], [3,4,5], [3,5,10], [4,5,9]]

StepPop [weight, node]totaladdedPushedWhat happensWhy
1[0, 0]01[7, 1], [3, 2]Node 0 joins for freeThe starting entry costs nothing. Node 0's two edges become candidates.
2[3, 2]32[2, 1], [8, 3], [4, 4]Node 2 joins by edge 0-23 is the cheapest crossing edge. Node 2 offers a cheaper way to node 1, cost 2, than the 7 already in the heap.
3[2, 1]53[6, 3]Node 1 joins by edge 1-2The edge 0-1 costing 7 is never used. Node 1 offers node 3 for 6.
4[4, 4]94[5, 3], [9, 5]Node 4 joins by edge 2-4Node 4 offers a cheaper edge to node 3, cost 5, and the first edge to node 5.
5[5, 3]145[10, 5]Node 3 joins by edge 3-4Three outdated entries are still in the heap: [6, 3], [7, 1], and [8, 3].
6[6, 3]145-Skip: 3 is in the treeinTree[3] is true, so this edge would close a loop. Nothing is paid.
7[7, 1]145-Skip: 1 is in the treeThe edge 0-1 from the very first step is finally popped and thrown away.
8[8, 3]145-Skip: 3 is in the treeAnother outdated entry.
9[9, 5]236-Node 5 joins; added === nThe cheapest edge to node 5 is 4-5. All 6 nodes are in, so the loop stops.

It returns 23, using edges 0-2 (3), 1-2 (2), 2-4 (4), 3-4 (5), and 4-5 (9). The entry [10, 5] is left in the heap, never needed.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Prim's algorithm (minimum spanning tree)O(e log e)O(n + e)The graph comes as adjacency lists, or you want to grow the tree from one place.
Kruskal's algorithmO(e log e)O(n + e)The input is already a list of edges, or you also want to stop early to form clusters.
Prim's with an array instead of a heapO(n²)O(n)Every pair of nodes can be linked, like points on a plane, so there are about n² edges anyway.

Extra memory: O(n + e): the adjacency lists hold each edge twice, and the heap can hold up to one entry per edge.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Prim's algorithm (minimum spanning tree) and the other approaches, on a scale where each line up is 10 times more steps.
  • Prim's algorithm (minimum spanning tree), Kruskal's algorithm O(e log e)
  • Prim's with an array instead of a heap O(n²)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Prim's algorithm (minimum spanning tree)339,96620 million
Kruskal's algorithm339,96620 million
Prim's with an array instead of a heap1001 million1 trillion

Inputs that need care

5 tricky inputs
A graph in two pieces
The heap runs out with added < n, and it returns -1. No spanning tree exists.
One node and no edges, n = 1
It pops [0, 0], sets added = 1, and returns 0.
Negative edge weights
They work. The cut property doesn't need weights to be 0 or more, unlike Dijkstra's argument.
Two edges between the same pair, costing 3 and 8
Both are pushed. The cheaper one is popped first; the other is skipped later because its node is already in.
Several edges with equal weight
Different trees can result depending on heap order, but they all have the same total.

Variations and follow-ups

Twists interviewers add

Array version for complete graphs

When every pair of points can be linked, like houses on a map, keep minCost[v] for every outside node and scan it for the smallest each round. That's O(n²) with no heap and no edge list, which beats O(e log e) when e is about n².

Maximum spanning tree

To connect everything while keeping the total as large as possible, push -w instead of w, or flip the heap's comparison. The same exchange argument works with the opposite order.

Spanning forest

If the graph has several pieces and you want the cheapest tree in each, restart from any node not yet in a tree each time the heap runs out, instead of returning -1.

A heap that can lower keys

An indexed heap keeps one entry per outside node and lowers its key when a cheaper edge appears. The heap then never holds more than n entries, giving O(e log n), at the cost of more code.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "connect all", "minimum cost to connect", "lay cable", or points that can each be joined at some cost, with no start or goal mentioned.
  • Explain the cut property in one sentence: "the cheapest edge leaving the tree so far is always part of some cheapest tree, because swapping it in never costs more".
  • Test by hand a graph where a cheaper edge to a node shows up after a more expensive one was pushed, like node 1 in the trace, and a disconnected graph that must return -1.
  • Expect "how is this different from Dijkstra?". Answer: the code is almost the same, but Prim compares single edge weights w, while Dijkstra compares whole path costs d + w.

Where frontend code uses it

The same idea in real UI code
  • Network and infrastructure planning dashboards that suggest the cheapest set of links to connect offices or servers.
  • Data visualization tools that draw a minimum spanning tree over points to show clusters and outliers in a scatter plot.
  • Procedural maze and map generators in browser games, which build a random spanning tree over grid cells (often with randomized Prim's).

Related algorithms