Prim's Algorithm: Build a Minimum Spanning Tree Greedily
Prim's algorithm builds a minimum spanning tree by greedily adding the cheapest edge crossing out of the tree — with a walkthrough, JavaScript, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
You have a set of cities and a price to lay cable between certain pairs. You want every city connected — but for the least total cost. That's the Minimum Spanning Tree (MST) problem, and Prim's algorithm solves it with one stubbornly greedy rule: grow one tree from a single seed, and at every step swallow the cheapest edge that reaches a city you don't have yet.
The magic is that this locally greedy choice is provably globally optimal. No backtracking, no second-guessing. Once you internalize the cut property that makes it work, the same reasoning carries into shortest-path and connectivity problems across the graph world.
The problem
Given a weighted, undirected graph, find a subset of edges that connects all vertices with the minimum possible total edge weight and no cycles. That subset is a tree spanning every vertex — a minimum spanning tree.
Input here is an adjacency list: graph[u] is a list of [neighbor, weight] pairs.
Input: graph = [
[[1, 2], [3, 6]], // node 0
[[0, 2], [2, 3], [3, 8], [4, 5]], // node 1
[[1, 3], [4, 7]], // node 2
[[0, 6], [1, 8], [4, 9]], // node 3
[[1, 5], [2, 7], [3, 9]] // node 4
]
Output: 16The five nodes connect for a total weight of 16, using edges 0–1 (2), 1–2 (3), 1–4 (5), and 0–3 (6). Any other spanning tree costs more.
The brute force baseline
The definition-driven approach is to enumerate every spanning tree and keep the cheapest. A connected graph on n vertices can have up to n^(n−2) distinct spanning trees (Cayley's formula), so even generating them is hopeless.
// Conceptual brute force — DO NOT ship this.
function mstBruteForce(n, edges) {
let best = Infinity;
for (const subset of allEdgeSubsetsOfSize(edges, n - 1)) {
if (connectsAll(subset, n) && isAcyclic(subset)) {
best = Math.min(best, totalWeight(subset));
}
}
return best;
}For 5 nodes that's 125 candidate trees; for 15 nodes it's over 20 billion. The number explodes exponentially, and the connectivity check inside each iteration only makes it worse. We need to build the tree directly instead of searching all of them.
The key insight: the cut property
Split the vertices into two groups: those already in your tree, and those still outside. Any edge with one endpoint in each group is a crossing edge. The cut property says: the cheapest crossing edge is always safe to add to the MST.
Why? Suppose the optimal MST didn't use that cheapest crossing edge. Adding it would create a cycle, and that cycle must contain some other crossing edge that is at least as expensive. Swap them — remove the pricier crossing edge, keep the cheaper one — and you get a spanning tree that costs no more. So a minimum spanning tree using the cheapest crossing edge always exists.
Prim's algorithm applies this repeatedly. Start with one vertex as the tree. Each step, find the cheapest edge crossing out of the tree and absorb its far endpoint. After n−1 such steps every vertex is in, and greed has assembled a provably minimum tree.
The one operation we repeat constantly is "give me the cheapest crossing edge." A min-heap answers that in logarithmic time, which is exactly what the optimal solution leans on.
The optimal solution
The visualizer teaches the lazy priority-queue form. Push candidate edges as [weight, node] pairs, always pop the smallest weight, and skip anything whose node is already in the tree.
function primMST(n, graph) {
let visited = new Array(n).fill(false);
let pq = new MinPriorityQueue({ priority: (x) => x[0] });
pq.enqueue([0, 0]); // [weight, startNode] — cost 0 to reach the seed
let edgesUsed = 0;
let mstCost = 0;
while (!pq.isEmpty() && edgesUsed < n) {
let [weight, node] = pq.dequeue().element;
if (visited[node]) continue; // stale entry — already absorbed
visited[node] = true;
edgesUsed++;
mstCost += weight;
for (let [edge, edgeWt] of graph[node]) {
if (!visited[edge]) {
pq.enqueue([edgeWt, edge]);
}
}
}
return mstCost;
}Three details carry the whole algorithm:
- We seed with
[0, 0]— reaching the start node costs nothing, so it pops first and its weight adds 0 to the total. if (visited[node]) continueis what makes the lazy heap correct. The same node can sit in the heap under several weights; we take the first (cheapest) one that pops and ignore the rest.edgesUsed < nlets us stop the moment all vertices are in, without draining leftover heap entries.
Walkthrough
Tracing the 5-node graph above, one row per while iteration. mstCost accumulates the weight of each edge we commit to.
| Iter | Popped [wt, node] | visited? | Action | mstCost | Heap after (sorted) |
|---|---|---|---|---|---|
| 1 | [0, 0] | no | add 0; push (2,1),(6,3) | 0 | (2,1),(6,3) |
| 2 | [2, 1] | no | add 1; push (3,2),(5,4),(8,3) | 2 | (3,2),(5,4),(6,3),(8,3) |
| 3 | [3, 2] | no | add 2; push (7,4) | 5 | (5,4),(6,3),(7,4),(8,3) |
| 4 | [5, 4] | no | add 4; push (9,3) | 10 | (6,3),(7,4),(8,3),(9,3) |
| 5 | [6, 3] | no | add 3; nothing new to push | 16 | (7,4),(8,3),(9,3) |
After iteration 5, edgesUsed === 5 === n, so the loop exits and returns 16.
Notice the heap still holds (7,4), (8,3), (9,3) — all pointing at nodes 3 and 4, which are already in the tree. Those are the stale entries. If the loop kept going, the visited[node] check would discard each one instead of adding a duplicate. That guard is why we can push freely without ever cleaning the heap.
Complexity
Let V be vertices and E edges.
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force (all trees) | O(V^(V−2)) | O(V) | enumerates every spanning tree |
| Array-scan Prim's | O(V²) | O(V) | linear min-search, V times |
| Lazy heap Prim's | O(E log E) | O(E) | each edge is pushed and popped once |
Every edge gets enqueued at most twice (once from each endpoint) and dequeued once, and each heap operation is O(log E). So the total is O(E log E), which equals O(E log V) since E ≤ V². The heap can hold up to O(E) entries, giving the space bound. On dense graphs where E ≈ V², the plain O(V²) array-scan version is actually competitive; on sparse graphs the heap wins comfortably.
Common mistakes
- Forgetting the
visitedcheck after popping. Without it, a node gets added twice and its extra weight corruptsmstCost. The lazy heap requires this gate. - Marking a node visited when you push it. Prim's finalizes a node only when it's popped as the current cheapest. Marking on push locks in a possibly-worse edge and breaks optimality.
- Storing
[node, weight]instead of[weight, node]. The heap orders by the first element. Swap them and it sorts by node id, not cost. - Assuming the graph is connected. If the loop ends with
edgesUsed < n, some vertices were never reachable — no spanning tree exists. Check for that instead of returning a partial cost silently. - Confusing Prim's with Dijkstra. They look almost identical, but Dijkstra pushes cumulative distance from the source; Prim's pushes the single edge weight crossing into the tree. Adding
weightto a running distance turns an MST into a shortest-path tree.
Where this pattern shows up next
The heap-driven greedy expansion and the "process nodes in order of cheapest frontier edge" idea recur across graph problems:
- Network Delay Time — the same priority-queue frontier, but ordered by cumulative distance (Dijkstra) instead of single-edge weight.
- Shortest Path in Binary Matrix — frontier expansion on a grid, where uniform edge costs let BFS stand in for the heap.
- Redundant Connection — the cycle-detection side of spanning trees, solved with the union-find that powers Kruskal's alternative to Prim's.
- Course Schedule II — a different ordering constraint over a graph, resolved by topological sort rather than edge weight.
You can also step through Prim's algorithm interactively to watch the key array shrink and each cheapest crossing edge get locked into the tree.
FAQ
What is the difference between Prim's and Kruskal's algorithm?
Both build a minimum spanning tree greedily, but they grow it differently. Prim's grows a single connected tree from one seed vertex, always adding the cheapest edge that reaches an outside vertex, and uses a priority queue to find that edge. Kruskal's instead sorts all edges by weight up front and adds them one by one, skipping any that would form a cycle, using union-find to detect cycles. Prim's tends to be preferred on dense graphs, Kruskal's on sparse ones where sorting edges is cheap.
Why does the greedy choice in Prim's produce the optimal tree?
Because of the cut property. At every step, the vertices split into "in the tree" and "outside." The cheapest edge crossing that boundary is guaranteed to belong to some minimum spanning tree — if an optimal tree skipped it, you could swap in the cheaper crossing edge without increasing total cost. Since every edge Prim's adds is a cheapest crossing edge, the accumulated tree is always minimum. No single local choice can be improved by looking ahead.
What time complexity does Prim's algorithm have?
With a binary heap (priority queue), Prim's runs in O(E log E), which is equivalent to O(E log V) because the number of edges is at most V². Each edge is pushed and popped from the heap at most a constant number of times, and each heap operation costs O(log E). A simpler version that scans an array for the minimum key each round runs in O(V²), which is actually faster on dense graphs where E is close to V².
Does Prim's algorithm work on disconnected graphs?
Not directly. Prim's grows one connected tree, so it can only span the component containing its start vertex. If the graph is disconnected, the main loop ends with fewer than n vertices added — you can detect this by checking whether edgesUsed reached n. To cover a disconnected graph you'd run Prim's from each unvisited vertex, producing a minimum spanning forest rather than a single tree.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.