Prim's algorithm
Start from any node. Keep a queue of edges leading out of the tree so far, and always take the cheapest one that reaches a node not yet in the tree. The tree grows by one node each time, like a spreading stain.
priority queue: lightest edge first
Grow a minimum spanning tree outward from A.
1function prim(adj, start) {2 const inTree = new Array(adj.length).fill(false);3 const pq = new MinHeap([[0, start]]);4 let total = 0;5 while (pq.size > 0) {6 const [w, u] = pq.pop();7 if (inTree[u]) continue;8 inTree[u] = true;9 total += w;10 for (const [v, wv] of adj[u]) {11 if (!inTree[v]) pq.push([wv, v]);12 }13 }14 return total;15}16// MinHeap is any binary heap of [weight, node] pairs, as on the Binary heap page.Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | E log V | with a binary heap of candidate edges |
| average | E log V | each edge enters the queue at most twice |
| worst | E log V | the same: every edge is considered |
| space | E | stale entries stay in the queue until popped |
Where it breaks
- Same answer as Kruskal, different order. Pick From A and then try Kruskal's page on the same towns: both total 39. Kruskal joins scattered pieces; Prim always grows one connected tree.
- The start does not matter for the total. Pick From G: the edges are added in another order, but the total weight is the same, 39.
- A disconnected graph. Prim only ever reaches the start node's part of the graph. To cover every part, restart it from a node still outside the tree, or use Kruskal, which handles a forest naturally.