Prim's Algorithm — MST via Min-Heap Greedy Expansion [Google, Amazon, Microsoft]

Problem Statement#

Given a connected, undirected, weighted graph with n vertices and a set of weighted edges, find the Minimum Spanning Tree (MST) — a subgraph that connects every vertex with no cycles and minimum possible total edge weight. Implement Prim's algorithm: grow the tree from a single starting vertex, repeatedly attaching the cheapest edge that connects a tree vertex to a non-tree vertex.

Constraints:

• 1 <= n <= 1000
• n - 1 <= edges.length <= n * (n-1) / 2
• Edge weights can be any integer (positive, negative, or zero)
• The graph is connected (an MST exists)

Example:

Input:  n = 5, edges = [[0,1,2],[0,3,6],[1,2,3],[1,3,8],[1,4,5],[2,4,7],[3,4,9]]
Output: MST cost = 16
Explanation: Pick edges (0,1,2), (1,2,3), (1,4,5), (0,3,6) → 2+3+5+6 = 16

Why This Problem Matters#

Prim's algorithm is the second pillar of the MST world. While Kruskal's algorithm processes edges globally, Prim's grows a single connected tree outward like a spreading ink stain — making it conceptually closer to Dijkstra and a natural fit when the graph is given as an adjacency list or matrix rather than an edge list. FAANG interviews like to test whether candidates can pick the right MST flavor for the input format: dense graphs with adjacency matrices favor Prim, sparse edge lists favor Kruskal.

You will see Prim disguised inside problems like LeetCode 1584 (Min Cost to Connect All Points), LeetCode 1135 (Connecting Cities with Minimum Cost), and LeetCode 1168 (Optimize Water Distribution in a Village). Recognizing the MST signature — "minimum total weight to connect everything, no specific path required" — is half the interview win. The other half is implementing the heap-based version cleanly without bugs.

Prim's is also the gateway to understanding the cut property intuitively. Each pop of the min-heap corresponds to choosing the lightest edge across the cut separating the tree from the rest of the graph. If a candidate can articulate this insight, interviewers know the candidate truly understands greedy graph algorithms rather than memorising templates.

The Core Insight#

Prim's algorithm builds the MST one vertex at a time. Begin with any starting vertex (typically vertex 0). Maintain two sets: vertices already in the tree (visited) and vertices yet to be added. At every step, examine all edges crossing the cut and pick the lightest one. The endpoint of that edge becomes the next vertex added to the tree.

Naive implementation scans all edges each iteration, costing O(VE). The efficient version uses a min-heap keyed on edge weight. Push every edge from the starting vertex into the heap. Pop the minimum-weight edge. If its other endpoint is unvisited, mark it visited, add the weight to the running cost, and push all of that vertex's edges into the heap. Repeat until V vertices are in the tree.

The heap-based version is O((V + E) log V). The crucial invariant: at every iteration the partial tree is a subset of some MST. Proof comes from the cut property — the lightest edge crossing any cut belongs to an MST. Since every popped edge is the lightest crossing the current cut between visited and unvisited vertices, it is always safe to add.

Visual Dry Run#

Input graph (adjacency list):

0: [(1,2),(3,6)]
1: [(0,2),(2,3),(3,8),(4,5)]
2: [(1,3),(4,7)]
3: [(0,6),(1,8),(4,9)]
4: [(1,5),(2,7),(3,9)]

When (7,4) and (8,3) and (9,3) are eventually popped, their endpoints are already visited so they are simply discarded. Total MST cost = 16.

Solution (Optimal)#

Python#

import heapq
 
def prim_mst(n, adj):
    """
    n   : number of vertices labelled 0..n-1
    adj : adjacency list where adj[u] = [(v, weight), ...]
    Returns total weight of MST, or -1 if graph disconnected.
    """
    visited = [False] * n
    visited[0] = True
    # min-heap of (edge_weight, to_vertex)
    heap = [(w, v) for v, w in adj[0]]
    heapq.heapify(heap)
 
    mst_cost = 0
    edges_used = 0
 
    while heap and edges_used < n - 1:
        w, u = heapq.heappop(heap)
        if visited[u]:
            continue  # stale edge — endpoint already in tree
        visited[u] = True
        mst_cost += w
        edges_used += 1
        # push all edges leaving u that head to unvisited vertices
        for v, wt in adj[u]:
            if not visited[v]:
                heapq.heappush(heap, (wt, v))
 
    return mst_cost if edges_used == n - 1 else -1

JavaScript#

// Requires a MinHeap helper. Below uses a simple binary heap.
class MinHeap {
    constructor() { this.h = []; }
    push(v) { this.h.push(v); this._up(this.h.length - 1); }
    pop() {
        const top = this.h[0], last = this.h.pop();
        if (this.h.length) { this.h[0] = last; this._down(0); }
        return top;
    }
    size() { return this.h.length; }
    _up(i) {
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p][0] <= this.h[i][0]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]]; i = p;
        }
    }
    _down(i) {
        const n = this.h.length;
        while (true) {
            const l = 2*i+1, r = 2*i+2; let s = i;
            if (l < n && this.h[l][0] < this.h[s][0]) s = l;
            if (r < n && this.h[r][0] < this.h[s][0]) s = r;
            if (s === i) break;
            [this.h[s], this.h[i]] = [this.h[i], this.h[s]]; i = s;
        }
    }
}
 
function primMST(n, adj) {
    const visited = new Array(n).fill(false);
    const heap = new MinHeap();
    visited[0] = true;
    for (const [v, w] of adj[0]) heap.push([w, v]);
 
    let cost = 0, used = 0;
    while (heap.size() && used < n - 1) {
        const [w, u] = heap.pop();
        if (visited[u]) continue;
        visited[u] = true;
        cost += w; used++;
        for (const [v, wt] of adj[u]) {
            if (!visited[v]) heap.push([wt, v]);
        }
    }
    return used === n - 1 ? cost : -1;
}

Complexity: Time O((V + E) log V) because every edge can be pushed and popped once and heap operations are logarithmic. Space O(V + E) for the heap and visited array. For dense graphs, the array-based variant runs in O(V^2) and is often faster in practice.

Common Mistakes#

1. Forgetting the staleness check. When an edge is popped, its destination might already be visited because a cheaper edge to it was processed earlier. Always continue past visited endpoints.
2. Pushing edges to already-visited vertices. This is fine for correctness but wastes memory. Filtering at push time keeps the heap smaller.
3. Using a max-heap accidentally. In languages where the default heap is max (Java's PriorityQueue is min, but JavaScript has none), you must invert weights or implement a min-heap.
4. Restarting from the wrong vertex on a disconnected graph. Prim works on a single connected component. If the graph might be disconnected, run Prim from every unvisited vertex (giving a minimum spanning forest).
5. Confusing Prim with Dijkstra. Both use a min-heap, but Dijkstra stores cumulative path distances while Prim stores single edge weights. Mixing the two yields wrong answers.
6. Integer overflow on the running total. Large edge weights summed over thousands of edges can overflow 32-bit integers. Use 64-bit accumulator.

Interview Tips#

• State the choice between Prim and Kruskal up front. If the input is an adjacency list or matrix, Prim is natural. If the input is an edge list and the graph is sparse, Kruskal often wins.
• Walk the interviewer through the cut property in plain words — "the cheapest edge crossing any cut between tree and non-tree vertices belongs to some MST." This earns rigor points.
• For dense graphs (E close to V squared), mention the O(V^2) array-based Prim and offer it as an optimization.
• If asked about negative edge weights, reassure the interviewer: MSTs are defined by relative weights, so negatives cause no issues.
• When the problem asks for the actual edges (not just the cost), maintain a parent array: when popping (w, u) from a parent p, record parent[u] = p.

Follow-up Questions#

1. What if you need the maximum spanning tree? Negate every edge weight and run Prim, or replace the min-heap with a max-heap.
2. What is the minimum bottleneck spanning tree? It minimizes the maximum edge — and any MST is also a minimum bottleneck spanning tree.
3. Can Prim handle a graph where edge weights change over time? Yes, but you must rerun it. Dynamic MST is a separate research area using link-cut trees.
4. How do you parallelise Prim? Borůvka's algorithm is more amenable to parallelisation than Prim or Kruskal.
5. LeetCode 1584 (Min Cost to Connect All Points) — solve with both Prim and Kruskal. Compare runtimes.

Key Takeaways#

• Prim's algorithm grows a single MST outward from any starting vertex by repeatedly attaching the cheapest crossing edge.
• The min-heap implementation runs in O((V + E) log V), which is optimal for sparse graphs where E is close to V.
• For dense graphs (E close to V squared), the O(V^2) array-based Prim avoids heap overhead and is faster in practice.
• The cut property guarantees correctness: the lightest edge across any cut belongs to some MST.
• Prim is the natural choice when the graph is supplied as adjacency list or matrix; Kruskal wins when the input is a sorted-friendly edge list.
• FAANG interview cue: any problem asking for "minimum cost to connect all nodes" is an MST problem; Prim and Kruskal both solve it.