Prim's Algorithm

A Bit of History

Prim's algorithm is a striking example of an idea being discovered, forgotten, and rediscovered. Czech mathematician Vojtěch Jarník published this exact "grow one tree outward" strategy in 1930 — a full 27 years before Robert Prim, an American mathematician at Bell Labs, independently rediscovered and popularized it in a 1957 paper. Because Jarník's paper was written in Czech and published in a regional journal, it went largely unnoticed outside Central Europe for decades — a genuine case of an important algorithm being "invented" three times: Jarník in 1930, Prim in 1957, and Edsger Dijkstra independently again in 1959 (in the very same short paper that introduced his shortest-path algorithm). Some textbooks now credit it as the "Jarník-Prim algorithm" in recognition of the earlier discovery.

Working Principle

Where Kruskal's algorithm works globally (sort every edge in the whole graph up front), Prim's algorithm works locally: start with a single arbitrary vertex as a one-vertex "tree," and repeatedly add the cheapest edge connecting the current tree to any vertex outside it, growing the tree by exactly one vertex each step. After \(n-1\) additions, every vertex is included and the MST is complete.

Worked Example

The same graph as the Kruskal's deep dive: \(A\text{-}C\) (1), \(B\text{-}C\) (1), \(B\text{-}D\) (1), \(A\text{-}B\) (4), \(C\text{-}D\) (5). Start from \(A\).

Same total weight (3) and, in this case, exactly the same edge set as Kruskal's algorithm found — the MST of a graph with distinct edge weights is always unique (an exercise from the Kruskal deep dive), so any correct algorithm must find it.

Correctness via the Cut Property

Prim's algorithm is, if anything, an even more direct application of the cut property (introduced in the Kruskal deep dive) than Kruskal's algorithm itself: at every step, the partition is literally "tree so far" versus "everything else," and the algorithm always adds the minimum-weight edge crossing exactly that cut — which the cut property guarantees is safe to add to some MST.

Complexity Analysis

With a binary-heap priority queue keyed by "cheapest known connecting edge weight" per outside vertex: \(V\) extractions at \(O(\log V)\) each, and up to \(E\) decrease-key operations at \(O(\log V)\) each:

$$\text{Time: } O((V+E)\log V) \qquad \text{Space: } O(V)$$

On a dense graph, a simpler \(O(V^2)\) array-based implementation (linear scan for the minimum each step, no heap at all) is often faster in practice — the same lesson from Dijkstra's algorithm applies here, since the underlying strategy is nearly identical.

Implementation

import heapq
from collections import defaultdict

def prim(adj, start):
    """
    adj: dict[vertex] -> list[(neighbor, weight)].
    Returns (mst_edges, total_weight).
    """
    visited = {start}
    heap = [(w, start, v) for v, w in adj[start]]
    heapq.heapify(heap)
    mst = []
    total = 0

    while heap and len(visited) < len(adj):
        w, u, v = heapq.heappop(heap)
        if v in visited:
            continue                      # stale entry -- v already annexed
        visited.add(v)
        mst.append((u, v, w))
        total += w
        for neighbor, weight in adj[v]:
            if neighbor not in visited:
                heapq.heappush(heap, (weight, v, neighbor))

    return mst, total

adj = defaultdict(list, {
    "A": [("C", 1), ("B", 4)],
    "B": [("A", 4), ("C", 1), ("D", 1)],
    "C": [("A", 1), ("B", 1), ("D", 5)],
    "D": [("B", 1), ("C", 5)],
})

mst, total_weight = prim(adj, "A")
print("MST edges:", mst)          # [('A','C',1), ('C','B',1), ('B','D',1)]
print("Total weight:", total_weight)  # 3

#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <iostream>
using namespace std;

int main() {
    unordered_map<string, vector<pair<string,int>>> adj = {
        {"A", {{"C", 1}, {"B", 4}}},
        {"B", {{"A", 4}, {"C", 1}, {"D", 1}}},
        {"C", {{"A", 1}, {"B", 1}, {"D", 5}}},
        {"D", {{"B", 1}, {"C", 5}}}
    };

    unordered_set<string> visited{"A"};
    // (weight, from, to)
    priority_queue<tuple<int,string,string>,
                   vector<tuple<int,string,string>>,
                   greater<>> heap;
    for (auto& [v, w] : adj["A"]) heap.push({w, "A", v});

    int totalWeight = 0;
    while (!heap.empty() && visited.size() < adj.size()) {
        auto [w, u, v] = heap.top(); heap.pop();
        if (visited.count(v)) continue;   // stale entry
        visited.insert(v);
        totalWeight += w;
        for (auto& [neighbor, weight] : adj[v]) {
            if (!visited.count(neighbor)) heap.push({weight, v, neighbor});
        }
    }
    cout << "MST total weight: " << totalWeight << endl;  // 3
    return 0;
}

import java.util.*;

class Prim {
    record Edge(int weight, String from, String to) {}

    public static void main(String[] args) {
        Map<String, List<Edge>> adj = new HashMap<>();
        adj.put("A", List.of(new Edge(1, "A", "C"), new Edge(4, "A", "B")));
        adj.put("B", List.of(new Edge(4, "B", "A"), new Edge(1, "B", "C"), new Edge(1, "B", "D")));
        adj.put("C", List.of(new Edge(1, "C", "A"), new Edge(1, "C", "B"), new Edge(5, "C", "D")));
        adj.put("D", List.of(new Edge(1, "D", "B"), new Edge(5, "D", "C")));

        Set<String> visited = new HashSet<>(List.of("A"));
        PriorityQueue<Edge> heap = new PriorityQueue<>(Comparator.comparingInt(Edge::weight));
        heap.addAll(adj.get("A"));

        int totalWeight = 0;
        while (!heap.isEmpty() && visited.size() < adj.size()) {
            Edge e = heap.poll();
            if (visited.contains(e.to())) continue;   // stale entry
            visited.add(e.to());
            totalWeight += e.weight();
            for (Edge next : adj.get(e.to())) {
                if (!visited.contains(next.to())) heap.add(next);
            }
        }
        System.out.println("MST total weight: " + totalWeight);  // 3
    }
}

Prim vs. Kruskal

Real-World Applications

Exercises

1. Run Prim's algorithm by hand starting from vertex \(D\) instead of \(A\) on the worked example's graph, and confirm the total MST weight is still 3.
2. Explain why Prim's algorithm never needs to check for cycles explicitly (unlike Kruskal's Union-Find check) — what property of "grow one connected tree" makes a cycle structurally impossible to introduce?
3. Implement the \(O(V^2)\) array-based version of Prim's algorithm (no heap) and compare its running time against the heap-based version on a very dense randomly generated graph.
4. Challenge: Prove that Prim's algorithm and Kruskal's algorithm always produce the same total MST weight (though possibly different edge sets, if weights are not all distinct) by showing both correctly implement the same cut-property-driven greedy strategy.

Limitations