Prim’s Algorithm

Prim’s algorithm (1957) takes a different angle: instead of sorting all edges globally, it grows the MST one vertex at a time from an arbitrary starting node. At each step it asks: “what’s the cheapest edge connecting the current tree to a vertex not yet in the tree?”

This is also justified by the cut property: at every step, S = the set of vertices already in the tree and V − S = the rest. Prim’s always picks the minimum crossing edge — the cut property guarantees this is the right move.

The algorithm

Worked example

Same graph as before. Starting from vertex A.

MST edges: A-C(2), C-B(1), B-D(5), D-E(2), E-F(3). Total: 13. Same MST as Kruskal’s.

Implementation — lazy Prim’s (heap of edges)

The “lazy” variant pushes all edges of a newly added vertex into the heap without removing stale entries. Stale entries (edges to already-added vertices) are detected and skipped when popped.

int primLazy(int n, vector<vector<pair<int,int>>>& adj) {
    // adj[u] = {(v, weight), ...}
    vector<bool> inTree(n, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, 0});  // {cost, vertex}, start at vertex 0
 
    int total = 0, added = 0;
    while (!pq.empty() && added < n) {
        auto [w, u] = pq.top(); pq.pop();
        if (inTree[u]) continue;
        inTree[u] = true;
        total += w;
        added++;
        for (auto [v, wv] : adj[u])
            if (!inTree[v])
                pq.push({wv, v});
    }
    return added == n ? total : -1;
}

import heapq
 
def prim_lazy(n, adj):
    # adj[u] = [(weight, v), ...]
    in_tree = [False] * n
    heap = [(0, 0)]  # (cost, vertex), start at 0
    total = added = 0
 
    while heap and added < n:
        w, u = heapq.heappop(heap)
        if in_tree[u]:
            continue
        in_tree[u] = True
        total += w
        added += 1
        for wv, v in adj[u]:
            if not in_tree[v]:
                heapq.heappush(heap, (wv, v))
 
    return total if added == n else -1

int primLazy(int n, List<int[]>[] adj) {
    // adj[u] = list of {v, weight}
    boolean[] inTree = new boolean[n];
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, 0});  // {cost, vertex}
 
    int total = 0, added = 0;
    while (!pq.isEmpty() && added < n) {
        int[] top = pq.poll();
        int w = top[0], u = top[1];
        if (inTree[u]) continue;
        inTree[u] = true;
        total += w;
        added++;
        for (int[] edge : adj[u])
            if (!inTree[edge[0]])
                pq.offer(new int[]{edge[1], edge[0]});
    }
    return added == n ? total : -1;
}

Eager Prim’s — fewer heap entries

The lazy version may put O(E) entries in the heap. The “eager” variant maintains, for each unvisited vertex v, only the current best edge connecting it to the tree. When a shorter edge is found, it decreases the key in the heap (a “decrease-key” operation).

With a Fibonacci heap, eager Prim’s runs in O(E + V log V). With a standard binary heap, decrease-key is O(log V) per update, giving O(E log V) — same asymptotic as the lazy version but with a smaller heap.

For competitive programming and interviews, lazy Prim’s is almost always sufficient. Implement eager only if explicitly asked for the Fibonacci-heap version.

Dense-graph Prim’s: O(V²) with an array

For dense graphs (E ≈ V²), using an adjacency matrix and scanning all vertices instead of a heap gives O(V²) — better than O(E log E) = O(V² log V).

def prim_dense(n, dist_matrix):
    # dist_matrix[i][j] = edge weight, float('inf') if no edge
    key = [float('inf')] * n
    in_tree = [False] * n
    key[0] = 0
    total = 0
 
    for _ in range(n):
        # Find the unvisited vertex with the smallest key
        u = min((i for i in range(n) if not in_tree[i]), key=lambda i: key[i])
        in_tree[u] = True
        total += key[u]
        for v in range(n):
            if not in_tree[v] and dist_matrix[u][v] < key[v]:
                key[v] = dist_matrix[u][v]
    return total

This O(V²) version is the right choice for:

• Complete graphs (every pair of vertices connected)
• Min Cost to Connect All Points (LC 1584), where the graph is implicitly complete

Kruskal’s vs Prim’s

Quick check

Next: Advanced Patterns — Borůvka’s algorithm, minimum bottleneck spanning trees, second-best MST, and real-world MST applications.