1. Min-heap by weight
The heap always surfaces the cheapest edge crossing out of the tree.
const heap = new MinHeap((x, y) => x[0] - y[0])Typorithm · medium
Prim's MST
▷ Interactive algorithm labprim-mstgraph-algorithmsmin-heapgreedyfrontier
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Prim's MST
Graph Algorithms
Grow one tree from a start node using a min-heap of (weight, node) edges, always adding the cheapest edge to an unvisited node.
Prim's builds a minimum spanning tree by expanding a single growing tree outward.
A min-heap holds candidate edges; the cheapest edge to a node outside the tree is taken next.
Adding a node pushes its neighbors' edges, refreshing the frontier of crossing edges.
Preparing algorithm lab…
01
Min-heap orders edges by weight.
02
Pop the cheapest edge to a new node.
03
Push neighbors after adding a node.
function primMst(n, graph, start) {
const inTree = new Array(n).fill(false);
const heap = new MinHeap((x, y) => x[0] - y[0]);
heap.push([0, start]);
let total = 0;
let used = 0;
while (heap.size() > 0 && used < n) {
const [weight, node] = heap.pop();
if (inTree[node]) continue;
inTree[node] = true;
total += weight;
used += 1;
for (const [next, w] of graph[node]) {
if (!inTree[next]) heap.push([w, next]);
}
}
return used === n ? total : null;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Seed the start
Begin the tree at the start node with zero cost.
heap.push([0, start])3. Pop cheapest
Repeatedly take the cheapest edge to a node not yet in the tree.
const [weight, node] = heap.pop()4. Skip in-tree
A node may sit in the heap more than once; ignore it once it is already in the tree.
if (inTree[node]) continue5. Push neighbors
Adding a node exposes new crossing edges for the heap to consider.
if (!inTree[next]) heap.push([w, next])A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.