What is Prim's algorithm?
Prim's algorithm also builds a minimum spanning tree, but it grows the tree from a single
starting node outward instead of sorting every edge globally the way Kruskal's does. At each step it
adds the cheapest edge that connects the tree-so-far to any node not yet in it, using a min-heap of
"frontier" edges — the same greedy safety guarantee as Kruskal's, just reached by a different route.
- Frontier edge
- The cheapest known edge connecting the tree-so-far to a node that isn't in the tree yet
- Min-heap
- A priority queue that always hands back the cheapest frontier edge next
- Tree-so-far
- The nodes already connected — it grows by exactly one node per step
Why grow from a single starting node?
Kruskal's algorithm looks at the whole edge list first: sort every edge by cost, then walk down the sorted list adding whichever ones don't create a cycle. Prim's never sorts anything — it starts at one node and only ever asks "what's the cheapest way to reach one more node from here?"
Think of it like running a garden hose network from a single faucet. You don't plan the whole yard's plumbing layout up front — you extend the hose to whichever unconnected sprinkler is currently cheapest to reach from the network you've already laid down.
Faucet reaches Sprinkler 1 for 2, Sprinkler 2 for 4 — Sprinkler 1 is cheapest.
How the frontier grows
Two things happen on every step: the cheapest frontier edge gets absorbed into the tree, and absorbing a node can reveal a cheaper way to reach a node that's already on the frontier.
Absorb the cheapest edge, every time
Start the tree at one node. Look at every edge leaving the tree toward an unvisited node — that's the frontier — and always take the cheapest one. The tree grows by exactly one node per step, never more.
Root at A. Frontier: A→B costs 4, A→C costs 2.
The frontier updates on the fly
Absorbing a node can beat an existing frontier entry. If a newly absorbed node offers a cheaper edge to a node that's already waiting on the frontier, that edge replaces the old, pricier one — the frontier always reflects the cheapest way in right now, not the first way in found.
B's cheapest known edge is straight from A, at cost 4.
Prim's vs Kruskal's
Both build a minimum spanning tree and both are provably correct by the same greedy safety argument — the cheapest edge crossing any cut is always safe to add. They differ in what they track and how they decide what's safe right now.
Kruskal's: edge-centric
Sort every edge in the graph once, then walk the sorted list. For each edge, use
union-find to check whether its two endpoints are already connected — if they are,
adding the edge would only create a cycle, so skip it.
function kruskalMST(nodeCount: number, edges: [number, number, number][]): number {
const sorted = [...edges].sort((a, b) => a[2] - b[2]); // globally cheapest first
const unionFind = new UnionFind(nodeCount);
let total = 0;
for (const [a, b, cost] of sorted) {
if (unionFind.find(a) === unionFind.find(b)) continue; // would form a cycle
unionFind.union(a, b);
total += cost;
}
return total;
}
Prim's: node-centric
Start at one node and maintain a min-heap of frontier edges instead. There's no cycle
check to run — an edge only ever gets pushed toward a node that isn't in the tree yet, so a
cycle simply can't form.
function primMST(nodeCount: number, edges: [number, number, number][]): number {
const adjacency = buildAdjacencyList(nodeCount, edges);
const inTree = new Set([0]);
const frontier = new MinHeap<[cost: number, node: number]>();
for (const [neighbor, cost] of adjacency[0]) frontier.push([cost, neighbor]);
let total = 0;
while (inTree.size < nodeCount && !frontier.isEmpty()) {
const [cost, node] = frontier.pop(); // cheapest way in, right now
if (inTree.has(node)) continue; // stale entry, already absorbed
inTree.add(node);
total += cost;
for (const [neighbor, edgeCost] of adjacency[node]) {
if (!inTree.has(neighbor)) frontier.push([edgeCost, neighbor]);
}
}
return total;
}
Where it wins — and where Kruskal's wins instead
Both algorithms are always correct — neither one "breaks." The difference is purely how much work each does, and that comes down to how many edges the graph has relative to its nodes.
Dense graphs favor Prim's
With many more edges than nodes, sorting the full edge list up front gets expensive. Prim's frontier only ever holds edges leaving the current tree, so it stays lean no matter how many edges the graph has overall.
Every node reaches every other node directly — A's frontier already lists all three neighbors.
Sparse graphs favor Kruskal's
With barely more edges than nodes, there's almost nothing to sort and almost no cycles to check — Kruskal's overhead disappears. Prim's still finds the correct answer, it just doesn't have much of a frontier to search each step.
Only n − 1 edges exist in total — there's barely a frontier to search each step.