Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Find the total weight of a Minimum Spanning Tree, growing it outward from a given start node. Prim's greedy: keep one connected tree, and at each step pull in the cheapest edge that links a tree node to a not-yet-included node. A min-heap of candidate (weight, node) edges delivers that cheapest crossing edge in O(log V); skip a popped node already in the tree (stale). Sum the weight used to first add each node. O((V + E) log V).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can build an MST by growing from a node, justify the greedy with the cut property, and adapt the Dijkstra-style heap loop to relax on edge weight (not path cost).
Where candidates slip
Relaxing with dist[u] + w (Dijkstra's path cost) instead of just w (the crossing-edge cost), forgetting to skip nodes already in the tree, or not adding undirected edges both ways.
How to stand out
Name the cut property, contrast Prim (vertex-centric, heap, dense graphs) with Kruskal (edge-centric, sort, sparse graphs), and explain why relaxing on the edge weight — not the path sum — is the crucial difference from Dijkstra.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewMin-heap relaxation from a start nodeRelax with...?single edge weight wpath cost dist[u] + wExplore the full treeCollapse the tree
How to read it:Green edges (3, 2, 4, 6) are added as Prim annexes nodes 2, 5, 3, 4; total 15.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Array-Scan Prim (Baseline)
1Hint 1Explore hintHide hint
Prim needs the cheapest crossing edge each round. The most direct way: store, for every node, the cheapest known edge weight to the current tree, and scan for the minimum.
2Hint 2Explore hintHide hint
Keep key[v] = cheapest edge from the tree to v (start has key 0, rest infinity) and inTree[v]. Each round: scan all nodes for the min-key node not in the tree, add it, then relax its neighbors' keys.
3Hint 3Explore hintHide hint
The scan is O(V), done V times → O(V²), plus O(E) total relaxation. No heap needed and great when E ≈ V².
A · Core idea
Prim's greedy needs only the cheapest crossing edge each round; a linear scan finds it.
The state. key[v] is the weight of the cheapest known edge connecting v to the current tree, initialized to 0 for start and infinity elsewhere. inTree[v] marks finalized nodes.
The loop. Repeat V times: scan all nodes for the not-in-tree node u with the smallest key, mark it in-tree, and add key[u] to total. Then relax: for each neighbor (v, w) of u not yet in the tree, if w < key[v], set key[v] = w (a cheaper way to attach v to the growing tree was found).
Why it's correct. When you pick the minimum-key out-of-tree node, key[u] is the lightest edge crossing the cut between the tree and the rest. By the cut property, that edge belongs to some MST, so adding it is always safe. After V rounds every node is attached and total is the MST weight.
Why mention it. On a dense graph (E ≈ V²), the O(V²) scan is as good as the heap and simpler — no stale-entry bookkeeping. State it to show you know the heap is a sparse-graph optimization, not a requirement.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 5, edges = [[1,2,3],[1,3,4],[4,2,6],[5,2,2],[2,3,5],[3,5,7]], start = 1Array state
init
key[1]=0, rest ∞
15C · Code with teaching comments
Reference implementation previewpublic int prims(int n, int[][] edges, int start) { List<List<int[]>> adj = new ArrayList<>(); for (int i = 0; i <= n; i++) adj.add(new ArrayList<>()); for (int[] e : edges) { adj.get(e[0]).add(new int[]{e[1], e[2]});Explore the full codeHide the full code
D · Why it works and complexityO(V²) timeO(V + E) spaceOpen the invariant and proofExplore the proofHide the proof
Prim's correctness comes from the cut property and the greedy 'nearest outside node', not from any data structure. The heap only speeds up finding that nearest node; on dense graphs the plain O(V²) scan ties it.
ComplexityO(V²) time, O(V + E) space — V rounds, each scanning all V nodes for the minimum key → O(V²). Each edge is examined once during relaxation → O(E). Total O(V² + E) = O(V²). With n ≤ 3000 that's ~9 × 10⁶ — fine, and on a dense graph it matches the heap version while avoiding heap overhead.
E · Edge cases and pitfalls3Relaxing with key[u] + w (Dijkstra) instead of w — builds shortest paths, not an MST.Explore edge casesHide edge cases
Pitfalls
- Relaxing with key[u] + w (Dijkstra) instead of w — builds shortest paths, not an MST.
- Scanning in-tree nodes when picking the minimum — each node should finalize once.
- Adding undirected edges only one way.
Approach 2 of 2 · Optimal
Min-Heap Prim (Optimal)
1Hint 1Explore hintHide hint
The array scan re-examines all V nodes each round. What structure hands you the minimum crossing edge in O(log V) instead?
2Hint 2Explore hintHide hint
A min-heap of (weight, node). Pop the cheapest; if that node is already in the tree, it's stale — skip it. Otherwise add it, then push each better crossing edge to its out-of-tree neighbors.
3Hint 3Explore hintHide hint
Each edge causes at most one push (O(E) pushes × O(log V)); each node is finalized once. Total O((V + E) log V).
A · Core idea
On a sparse graph, scanning all V nodes per round wastes time; a min-heap surfaces the cheapest crossing edge directly.
The loop. Seed dist[start] = 0 and push (0, start). Repeatedly pop the smallest (w, u). If u is already in the tree, this is a leftover duplicate — skip it. Otherwise mark u in-tree, add w to total, and for each neighbor (v, wt) not yet in the tree with wt < dist[v], set dist[v] = wt and push (wt, v).
Why relax on the edge weight. dist[v] here means the cheapest single edge connecting `v` to the current tree, not the cost of a path. That is the only change from Dijkstra, and it's what makes the result a minimum-weight tree instead of a shortest-path tree: an MST cares about each connecting edge's cost, never about cumulative distance from the start.
Why skip stale entries. With no efficient decrease-key, we push a fresh (wt, v) whenever dist[v] improves, so the heap holds several entries per node. The first popped is the cheapest and correct; the rest reference nodes already in the tree and are discarded in O(1) via the if u in tree: continue check.
Why it's correct. Each pop selects the minimum-weight edge crossing the cut between the tree and the rest. By the cut property that edge is in some MST, so every addition is safe. After all V nodes are added, total is the MST weight.
Output. Sum the weight used to first add each node; the start node contributes 0. Parallel edges need no special handling — relaxation keeps the cheapest; self-loops never improve dist.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 5, edges = [[1,2,3],[1,3,4],[4,2,6],[5,2,2],[2,3,5],[3,5,7]], start = 1Array state
add 1
push (3,2),(4,3)
15C · Code with teaching comments
D · Why it works and complexityO((V + E) log V) timeO(V + E) spaceOpen the invariant and proofExplore the proofHide the proof
Prim and Dijkstra share one skeleton — a greedy min-heap that finalizes the closest frontier node — and differ in a single line: Prim relaxes with the edge weight (build a cheap tree), Dijkstra with the accumulated path cost (find cheap paths). Recognizing that they're the same template with one swapped comparison is the senior-level observation.
ComplexityO((V + E) log V) time, O(V + E) space — Each edge can push at most one candidate → O(E) pushes, each O(log V). Each of V nodes is popped and finalized once. Total O((V + E) log V). Space is the adjacency list O(V + E) plus the heap O(V).
E · Edge cases and pitfalls7parallel edges [1,2,5] and [1,2,2] — Both push candidates for node 2; the weight-2 pop adds it, the weight-5 entry is later skipped as stale.Explore edge casesHide edge cases
Edge cases handled
parallel edges [1,2,5] and [1,2,2]Both push candidates for node 2; the weight-2 pop adds it, the weight-5 entry is later skipped as stale.self-loop [u, u, w]Once u is in the tree, the loop's not-in-tree check rejects it; it never affects total.n = 2, one edge [1,2,7], start = 2Add 2 (0), then add 1 via the weight-7 edge → total 7.
Pitfalls
- Relaxing with dist[u] + wt (Dijkstra) instead of wt — silently solves the wrong problem.
- Omitting the in-tree skip — re-adds nodes and overcounts the total.
- Adding undirected edges only one direction.
- Using int for the running total when many large weights could overflow — accumulate in long.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int prims(int n, int[][] edges, int start) { List<List<int[]>> adj = new ArrayList<>(); for (int i = 0; i <= n; i++) adj.add(new ArrayList<>()); for (int[] e : edges) { adj.get(e[0]).add(new int[]{e[1], e[2]});Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Dijkstra-style relaxation
Prim wants the cheapest edge connecting a node to the tree, so it relaxes on w alone. Using dist[u] + w accumulates path cost and builds a shortest-path tree whose total weight is not the MST.
Explore the code comparisonHide the code comparison
Dijkstra-style relaxation
Prim wants the cheapest edge connecting a node to the tree, so it relaxes on w alone. Using dist[u] + w accumulates path cost and builds a shortest-path tree whose total weight is not the MST.
Don't write this
if not in_tree[v] and dist[u] + wt < dist[v]:
dist[v] = dist[u] + wt # path cost — wrong for MSTWrite this instead
if not in_tree[v] and wt < dist[v]:
dist[v] = wt # single edge weight — correct for MST2Missing the in-tree skip
Because we push duplicates instead of decrease-key, the heap holds outdated entries. Processing a node already in the tree re-adds its weight and corrupts the total.
Explore the code comparisonHide the code comparison
Missing the in-tree skip
Because we push duplicates instead of decrease-key, the heap holds outdated entries. Processing a node already in the tree re-adds its weight and corrupts the total.
Don't write this
long[] top = heap.poll();
int u = (int) top[1];
inTree[u] = true;
total += top[0]; // may re-add an already-finalized nodeWrite this instead
long[] top = heap.poll();
int u = (int) top[1];
if (inTree[u]) continue; // skip stale duplicate
inTree[u] = true;
total += top[0];3One-directional undirected edge
An undirected edge connects both ways. Adding it to only one adjacency list hides crossing edges, so some nodes look unreachable and the tree can't span them.
Explore the code comparisonHide the code comparison
One-directional undirected edge
An undirected edge connects both ways. Adding it to only one adjacency list hides crossing edges, so some nodes look unreachable and the tree can't span them.
Don't write this
for u, v, w in edges:
adj[u].append((v, w)) # only one directionWrite this instead
for u, v, w in edges:
adj[u].append((v, w))
adj[v].append((u, w)) # undirected → both waysRevise
Carry the pattern into the interview
Pattern to remember
Grow one tree, always add the cheapest crossing edge (min-heap)
Code pattern to memorize
dist[start] = 0, push (0, start)
total = 0
while heap and tree not full:
(w, u) = pop-min
if u in tree: continue # stale
add u to tree; total += w
for (v, wt) in adj[u]:
if v not in tree and wt < dist[v]:
dist[v] = wt
push (wt, v)
return totalRules to remember
- 1Prim grows one connected tree from a start node — contrast Kruskal, which merges a forest of many trees.
- 2Always add the cheapest edge crossing the cut between in-tree and out-of-tree nodes; that edge is provably safe (cut property).
- 3
dist[v]holds the cheapest single edge from the current tree tov— not an accumulated path cost (that's Dijkstra). - 4Skip a heap pop whose node is already in the tree (
if u in tree: continue) — it's a stale duplicate. - 5Accumulate the edge weight used to first attach each node; the start node contributes 0.
Use this pattern when
- Minimum spanning tree of a connected undirected weighted graph
- A **start node** is given or the graph is **dense** (adjacency-friendly)
- You'd rather grow one tree incrementally than sort all edges
- Edge weights can be relaxed down as cheaper crossing edges appear
Choose another pattern when
- Graph is a sparse **edge list** and easy to sort → Kruskal is often simpler
- You need shortest *paths* from the start → Dijkstra (accumulate path cost, not single-edge cost)
- Directed graph → MST undefined; want a minimum arborescence
- Disconnected graph but a single tree required → no MST exists
Interview takeaway
Prim is the vertex-centric MST: maintain a growing blob and repeatedly annex the nearest outside node by its cheapest connecting edge. It looks like Dijkstra but relaxes on the single edge weight, not the cumulative path — that one difference is what builds a tree of minimum total weight instead of shortest paths.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical Greedy MST via Prim + Min-Heap. Recognize it when growing a single tree from a start node, especially on dense or adjacency-given graphs. It shares Dijkstra's heap-relaxation skeleton — the only change is relaxing on the edge weight instead of the accumulated path cost. Drop to the O(V²) array scan when the graph is dense.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Kruskal (MST): Really Special SubtreeSame MST, edge-centric: sort all edges and merge components with union-find — better on sparse edge lists.
- Min Cost to Connect All PointsComing soonDense complete graph of Manhattan distances — Prim's O(V²) array scan is ideal here.
- Connecting Cities With Minimum CostComing soonMST with a connectivity check — return -1 if fewer than n − 1 edges can be added.
- Dijkstra: Shortest Reach 2The same heap skeleton, but relax on accumulated path cost to get shortest paths instead of an MST.