Prim’s Algorithm

A minimum spanning tree (MST) connects all vertices in an undirected, weighted graph using the fewest total edge weight — no cycles, every vertex reachable. Prim’s algorithm builds this tree by growing it one vertex at a time, always absorbing the cheapest available edge that connects the MST to a vertex outside it.

Picture building a railroad network across cities. You start at one city and repeatedly lay track to the nearest unconnected city. Every step adds the cheapest possible connection. When all cities are linked, you’ve built the minimum-cost network. That’s Prim’s algorithm.

The Algorithm

1. Pick any starting vertex. Mark it as part of the MST.
2. Add all edges from MST vertices into a priority queue, ordered by weight.
3. Extract the minimum-weight edge from the PQ.
4. If the destination vertex is already in the MST → skip this edge (lazy deletion).
5. Otherwise, add the destination to the MST and enqueue all its edges.
6. Repeat until the MST contains V - 1 edges (connecting all V vertices).

The greedy choice — always take the cheapest crossing edge — produces a globally optimal result. This works because of the cut property, which we’ll prove shortly.

Lazy Implementation

The “lazy” approach is simpler and the version you’ll implement in interviews. It adds edges to the priority queue and discards stale ones later.

record Edge(int from, int to, int weight) implements Comparable<Edge> {
    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.weight, other.weight);
    }
}

record MSTResult(int totalWeight, List<Edge> edges) {}

MSTResult primMST(List<List<Edge>> graph, int n) {
    boolean[] inMST = new boolean[n];
    PriorityQueue<Edge> pq = new PriorityQueue<>();
    List<Edge> mstEdges = new ArrayList<>();
    int totalWeight = 0;

    // Start from vertex 0
    inMST[0] = true;
    for (Edge e : graph.get(0)) {
        pq.offer(e);
    }

    while (!pq.isEmpty() && mstEdges.size() < n - 1) {
        Edge edge = pq.poll();

        // Lazy deletion: skip if destination already in MST
        if (inMST[edge.to()]) continue;

        // Accept this edge into the MST
        inMST[edge.to()] = true;
        mstEdges.add(edge);
        totalWeight += edge.weight();

        // Add all edges from the newly added vertex
        for (Edge next : graph.get(edge.to())) {
            if (!inMST[next.to()]) {
                pq.offer(next);
            }
        }
    }

    return new MSTResult(totalWeight, mstEdges);
}

The inMST boolean array tracks which vertices belong to the tree. When we extract an edge whose destination is already in the MST, we discard it — it’s a stale entry left over from an earlier, more expensive path. This lazy deletion is why the PQ can contain up to O(E) entries.

Building the Graph

List<List<Edge>> buildGraph(int n, int[][] edges) {
    List<List<Edge>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

    for (int[] e : edges) {
        int u = e[0], v = e[1], w = e[2];
        graph.get(u).add(new Edge(u, v, w));
        graph.get(v).add(new Edge(v, u, w));  // Undirected
    }
    return graph;
}

Eager Implementation

The eager approach maintains at most one entry per non-MST vertex in the priority queue — the cheapest known edge connecting that vertex to the MST. When a cheaper edge is discovered, it replaces the existing entry.

This requires an indexed priority queue (IPQ) that supports decreaseKey operations. The IPQ maps each vertex to its current best edge weight and allows efficient updates.

// Pseudocode for eager Prim's
for each non-MST vertex v:
    bestEdge[v] = cheapest edge connecting v to MST

PQ contains one entry per non-MST vertex, keyed by bestEdge weight.

When adding vertex u to MST:
    for each edge (u, v, w) where v is not in MST:
        if w < bestEdge[v]:
            bestEdge[v] = w
            decreaseKey(v, w) in PQ

The eager approach keeps the PQ size at O(V) instead of O(E). For dense graphs where E ≈ V², this difference is substantial. However, implementing an indexed priority queue from scratch during an interview is impractical. The lazy version is the standard interview answer.

The Cut Property

The cut property is why Prim’s algorithm works. Understanding it gives you the ability to explain correctness to any interviewer.

Definition: A cut in a graph partitions the vertices into two non-empty sets S and V − S. A crossing edge has one endpoint in S and the other in V − S.

Cut Property: For any cut in the graph, the minimum-weight crossing edge belongs to some MST.

Proof sketch: Suppose the minimum crossing edge e = (u, v) does NOT appear in some MST T. Adding e to T creates a cycle. This cycle must contain another crossing edge e’ (because u is in S and v is in V − S, so the path from u to v in T must cross the cut somewhere). Since weight(e) ≤ weight(e’), removing e’ and adding e produces a spanning tree T’ with total weight ≤ T. So T’ is also an MST, and it contains e.

Why Prim’s is correct: At every step, Prim’s algorithm considers the cut between MST vertices and non-MST vertices. It selects the minimum crossing edge. By the cut property, this edge belongs to some MST. After V - 1 such selections, the result is an MST.

Step-by-Step Walkthrough

Consider this graph:

    2       3
A ——— B ——— C
|   / |     |
6  1  5     7
| /   |     |
D ——— E ——— F
    4       8

Edges: A-B(2), B-C(3), A-D(6), B-D(1), B-E(5), D-E(4), C-F(7), E-F(8)

Start at A. MST = {A}. PQ: [A-B(2), A-D(6)]

Step 1. Extract A-B(2). Add B to MST. MST = {A, B}. PQ: [B-D(1), B-C(3), B-E(5), A-D(6)]

Step 2. Extract B-D(1). Add D to MST. MST = {A, B, D}. PQ: [B-C(3), D-E(4), B-E(5), A-D(6)]

Step 3. Extract B-C(3). Add C to MST. MST = {A, B, D, C}. PQ: [D-E(4), B-E(5), A-D(6), C-F(7)]

Step 4. Extract D-E(4). Add E to MST. MST = {A, B, D, C, E}. PQ: [B-E(5), A-D(6), C-F(7), E-F(8)]

Step 5. Extract B-E(5) → E already in MST → skip. Extract A-D(6) → D already in MST → skip. Extract C-F(7). Add F to MST. MST = {A, B, D, C, E, F}.

MST edges: A-B(2), B-D(1), B-C(3), D-E(4), C-F(7). Total weight: 17.

Notice how stale edges (B-E and A-D) get extracted and discarded. This is the “lazy” part — the PQ accumulates edges that become irrelevant once their destination joins the MST.

Complexity Analysis

Lazy Prim’s

• Time: O(E log E). Each edge enters the PQ at most twice (once from each endpoint). Each PQ operation (insert or extract-min) takes O(log E). Since log E = O(log V²) = O(2 log V) = O(log V), this is effectively O(E log V).
• Space: O(V + E). The adjacency list takes O(V + E) and the PQ holds up to O(E) edges.

Eager Prim’s

• Time: O(E log V). The indexed PQ holds at most V entries, so each operation is O(log V). We perform at most E decrease-key operations.
• Space: O(V + E). The IPQ holds O(V) entries.

For dense graphs (E ≈ V²), both approaches run in O(V² log V). For sparse graphs (E ≈ V), lazy Prim’s runs in O(V log V).

Prim’s vs Kruskal’s

Both algorithms produce the same MST (if all edge weights are distinct, the MST is unique). They differ in strategy:

Property	Prim’s	Kruskal’s
Strategy	Grow tree from a vertex	Sort edges, add cheapest non-cyclic edge
Data structure	Priority queue	Sort + Union-Find
Focus	Vertex-centric	Edge-centric
Starts from	Single vertex	Global edge list
Best for	Dense graphs (E ≈ V²)	Sparse graphs (E ≈ V)
Time (lazy/standard)	O(E log V)	O(E log E)
Handles disconnected graphs	Finds MST of component	Finds minimum spanning forest
Parallelizable	Difficult	Easier (edges can be sorted in parallel)

When edge weights are not distinct, multiple MSTs can exist. Both algorithms find an MST, but they can find different ones depending on tie-breaking.

Interviewers appreciate candidates who know both and can articulate when one is preferable. For dense graphs (adjacency matrix representation), Prim’s with an indexed PQ runs in O(V² log V). Kruskal’s on the same graph pays O(V² log V²) = O(V² log V) for sorting, making them comparable. For sparse graphs, Kruskal’s O(E log E) with E ≈ V becomes O(V log V), which matches Prim’s.

Practice Problems

Min Cost to Connect All Points

Problem: Given n points on a 2D plane, find the minimum cost to connect all points. The cost between two points is the Manhattan distance |xᵢ - xⱼ| + |yᵢ - yⱼ|.

This is a Euclidean MST problem with Manhattan distance. The graph is complete (every pair of points has an edge), so E = V(V-1)/2. Prim’s is ideal here because the graph is dense.

int minCostConnectPoints(int[][] points) {
    int n = points.length;
    boolean[] inMST = new boolean[n];
    // PQ: [cost, pointIndex]
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    pq.offer(new int[]{0, 0});
    int totalCost = 0;
    int edgesAdded = 0;

    while (edgesAdded < n) {
        int[] curr = pq.poll();
        int cost = curr[0], u = curr[1];

        if (inMST[u]) continue;
        inMST[u] = true;
        totalCost += cost;
        edgesAdded++;

        for (int v = 0; v < n; v++) {
            if (!inMST[v]) {
                int dist = Math.abs(points[u][0] - points[v][0])
                         + Math.abs(points[u][1] - points[v][1]);
                pq.offer(new int[]{dist, v});
            }
        }
    }
    return totalCost;
}

This runs in O(V² log V) — you add O(V) edges each time you absorb a vertex, and there are V vertices. For the complete graph, this matches the theoretical optimum.

MST Weight Computation

In many interview problems, you need the MST weight rather than the tree itself. Prim’s gives you this naturally — accumulate edge.weight() each time you accept an edge.

Edge Cases

Disconnected graph: Prim’s started from a single vertex only builds the MST of the connected component containing that vertex. If you need a minimum spanning forest (MST for each component), run Prim’s from each unvisited vertex.

int mstForest(List<List<Edge>> graph, int n) {
    boolean[] inMST = new boolean[n];
    int totalWeight = 0;

    for (int start = 0; start < n; start++) {
        if (inMST[start]) continue;
        totalWeight += primFromVertex(graph, inMST, start, n);
    }
    return totalWeight;
}

Single vertex: An MST of one vertex has zero edges and zero weight. The algorithm handles this naturally — the PQ starts empty (no edges from a lone vertex), and the loop exits immediately.

Equal weight edges: Multiple MSTs can exist. Prim’s finds one of them, determined by the starting vertex and tie-breaking in the PQ.

Self-loops: These never appear in an MST (they connect a vertex to itself, contributing weight without connecting new vertices). Filter them out or let the inMST check skip them.

Negative weights: Prim’s handles negative edge weights correctly. Unlike shortest-path algorithms, MST algorithms care about relative ordering, not sign. A negative-weight edge is always attractive — it reduces total MST cost.

Interviewer Tips

“Walk me through Prim’s algorithm.” Start from any vertex, maintain a priority queue of edges connecting the MST to non-MST vertices, and repeatedly extract the minimum-weight edge. Skip edges to vertices already in the MST. Continue until V - 1 edges are accepted.

“Why does the greedy approach work?” Because of the cut property: the minimum-weight edge crossing any cut belongs to some MST. At every step, Prim’s selects the minimum crossing edge for the cut between MST and non-MST vertices.

“Prim’s or Kruskal’s — which do you prefer?” For interviews, Prim’s with a lazy PQ when the graph is given as an adjacency list and is dense. Kruskal’s when the graph is given as an edge list and is sparse. If all the edges are already available and the graph is small, Kruskal’s often leads to cleaner code because sorting is a one-liner. For competitive programming with dense graphs, Prim’s avoids the O(E log E) sorting step.

“What’s the time complexity?” O(E log V) for both lazy and eager Prim’s. The lazy version has worst-case PQ size O(E), but log E = O(log V) for connected graphs, so the asymptotic bound is the same. The eager version keeps PQ size at O(V) with decrease-key operations.