Day 14 · Week 3

Prim's Minimum Spanning Tree

Level 5 · MST · 2 hrs: ~45 min theory · ~60 min code · ~15 min notes

🧠 Mental Model

Prim's is the "local greedy" MST: grow one tree from a start vertex, always adding the cheapest edge that connects the tree to a new vertex. Where Kruskal thinks globally (cheapest edge anywhere), Prim thinks locally (cheapest edge on the frontier). It looks almost exactly like Dijkstra — a min-heap on the frontier.

Same cut property underpins both, applied to a different cut: the tree-so-far vs everything else.

⚙️ Mechanics

Start from any vertex; put its edges in a min-heap keyed by weight.
Pop the lightest edge to a vertex v not yet in the tree; add v and its weight.
Push v's edges to unvisited neighbors.
Repeat until all V vertices are in the tree.

Invariant: the selected edges always form a single connected tree, and every step adds the minimum-weight edge crossing the cut (tree vs non-tree) — safe by the cut property.

📐 Correctness

Theorem Prim's produces an MST: at each step the added edge is a minimum-weight edge crossing the cut (tree, V − tree), hence safe.

Proof Let A be the edges chosen so far, forming a tree over vertex set S. Consider the cut (S, V∖S). Prim's heap always yields the lightest edge crossing this cut (all lighter edges lead to vertices already in S and are discarded). By the cut property (proven Day 13), that edge belongs to some MST extending A. By induction, starting from the trivial tree A = ∅, every added edge is safe, so the final tree is an MST. ∎

⚖️ Kruskal vs Prim — which to reach for

	Kruskal	Prim (heap)	Prim (matrix)
Strategy	Global: cheapest edge anywhere	Local: grow one tree	Local: grow one tree
Data structure	Sort + Union-Find	Min-heap	Arrays
Time	O(E log E)	O(E log V)	O(V²)
Best for	Sparse graphs, edge list given	Sparse/medium graphs	Dense graphs (E ≈ V²)
Handles disconnection	Naturally (forest)	Detects (can't reach all)	Detects

Interview rule of thumb: edge list + sparse → Kruskal. Dense/complete graph (e.g. "connect all points") → Prim with O(V²) arrays avoids building O(V²) explicit edges to sort.

💻 Reference Implementation (Java)

import java.util.*;

/** Prim's MST with a min-heap. adj[u] = list of {v, w}. */
public int prim(List<int[]>[] adj, int n) {
    boolean[] inTree = new boolean[n];
    PriorityQueue<int[]> pq =
        new PriorityQueue<>((a, b) -> a[1] - b[1]); // {vertex, edgeWeight}
    pq.offer(new int[]{0, 0});   // start at vertex 0, cost 0
    int total = 0, count = 0;

    while (!pq.isEmpty() && count < n) {
        int[] top = pq.poll();
        int u = top[0], w = top[1];
        if (inTree[u]) continue;      // stale frontier entry
        inTree[u] = true;
        total += w;
        count++;
        for (int[] e : adj[u])
            if (!inTree[e[0]]) pq.offer(new int[]{e[0], e[1]});
    }
    return count == n ? total : -1;  // -1 ⇒ disconnected
}

Note the resemblance to Dijkstra — the difference: Prim's key is the edge weight (cost to attach), Dijkstra's key is cumulative distance from the source.

🎭 Problem Variances — Prim-flavored twists

Disguise / phrasing	What's really asked	Twist to handle
"Connect all points" (dense/complete)	MST on a geometric graph	Use Prim O(V²) with a `minDist[]` array — no explicit edge list
"Optimize water distribution" (wells + pipes)	MST with a virtual source	Well cost = edge from node 0; run Prim from 0
"Grow network from a hub"	MST rooted at a required start	Seed the heap with that hub
"Min cost, some nodes pre-connected"	MST over contracted components	Mark pre-connected nodes inTree before starting
"Bottleneck path between two nodes"	Minimize the max edge on a path	Prim/Kruskal MST contains the minimax path

Kruskal vs Prim in practice: both give the same MST weight — pick by graph density. If asked "why this one?", cite the complexity table above.

⚠️ Common Pitfalls

Missing the stale-entry skip: without if (inTree[u]) continue; you double-count vertices and inflate the total.

Keying the heap by distance-from-source (Dijkstra-style): Prim keys by the single connecting edge's weight, not cumulative distance.

Using heap-Prim on a dense graph: O(E log V) with E ≈ V² is worse than the O(V²) array version.

🎯 Problems

LC 1584 Min Cost to Connect All Points Redo with Prim's O(V²) — compare against yesterday's Kruskal. Dense → Prim wins. Med

LC 1168 Optimize Water Distribution in a Village Virtual node 0 with well-cost edges; MST from there. Hard

📚 References

CLRS, 3rd ed., §23.2 — Prim's algorithm and its cut-property correctness.
Prim, R. C. (1957) — "Shortest connection networks and some generalizations," Bell System Tech. J. 36(6).
Jarník, V. (1930) — the original (pre-Prim) formulation; sometimes "Jarník's algorithm."
Fredman & Tarjan (1987) — Fibonacci-heap Prim's at O(E + V log V).

← Day 13: Kruskal's Day 15: Consolidation →