Algorithm Deep Dive: 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.

Visual Intuition

Prim grows one connected territory outward

The key idea is the frontier: edges with one endpoint already inside the growing tree and the other endpoint still outside. Prim ignores edges that lie completely inside the tree and ignores edges between two outside vertices. Among the frontier edges, it chooses the cheapest one.

Memory trick: Prim always asks, “What is the cheapest way to attach one new vertex to the tree I already have?”

Analogy: An Expanding Territory, Always Annexing the Cheapest Neighbor

Picture a small kingdom (the growing tree) deciding which neighboring village to annex next. At every step, it looks only at villages directly bordering its current territory and annexes whichever one is cheapest to connect — never looking at villages far away that aren't yet reachable from the current border. This is exactly why Prim's algorithm needs a priority queue keyed on vertices (specifically, the cheapest known edge connecting each outside vertex to the tree) rather than a global sort of every edge in the graph.

What the Priority Queue Is Really Doing

For every vertex still outside the tree, Prim cares about its best known attachment cost: the cheapest edge currently connecting that vertex to any vertex already inside the tree.

\operatorname{key}[v] = \min_{u \in T} w(u,v)

The priority queue simply returns the outside vertex with the smallest key. Once that vertex joins the tree, its newly exposed edges may improve the keys of other outside vertices.

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$.

Step	Tree so far	Frontier edges considered	Cheapest added
0	{A}	A-C (1), A-B (4)	A-C (1)
1	{A,C}	A-B (4), C-B (1), C-D (5)	C-B (1)
2	{A,C,B}	A-B (skip, both endpoints in tree), B-D (1), C-D (5)	B-D (1)
3	{A,C,B,D}	— all vertices included, stop	—

Step-by-Step

Watch the tree grow from the seed vertex A

Unlike Kruskal, which may build several disconnected trees before merging them, Prim stays connected after every single step. Each accepted edge crosses from the existing tree to exactly one new vertex.

Always connected Adds one vertex per step Cheapest frontier edge

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.

Why the Greedy Choice Is Safe

The current tree creates the cut automatically

Imagine drawing a boundary around every vertex Prim has already chosen. Any edge that leaves that boundary crosses the cut. The cut property says that the minimum-weight crossing edge is always safe to include in some MST — exactly the edge Prim selects.

Why Prim Does Not Need a Separate Cycle Check

Every accepted edge has exactly one endpoint inside the current tree and one endpoint outside it. So that edge attaches a brand-new vertex. A cycle would require both endpoints to already be connected inside the tree, but Prim never accepts an inside-to-inside edge. The growth rule itself prevents cycles.

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

Aspect	Prim's	Kruskal's
Strategy	grows one tree from a seed vertex	sorts all edges, adds globally cheapest safe edge
Best for	dense graphs; adjacency-matrix input	sparse graphs; edge-list input
Needs upfront	a starting vertex only	the entire edge list, sorted
Streaming-friendly?	yes — grows incrementally	no — needs global edge knowledge first

Compare the Mental Models

Both algorithms are greedy and both are justified by the cut property. The difference is which cut they focus on: Prim uses the boundary of one growing tree; Kruskal considers whichever components the next globally cheapest safe edge happens to join.

Real-World Applications

Case Study

Incremental Network Rollout

When a telecom or utility company expands a network incrementally — starting from an existing hub and deciding, year by year, which new site to connect next at minimum cost — Prim's "grow outward" structure matches the real-world constraint far better than Kruskal's "know every candidate edge up front" approach. The same incremental-growth pattern appears in real-time cluster/mesh network formation, where devices discover each other and join a minimum-cost spanning topology as they come online.

Network RolloutMesh Networks

Exercises

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.
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?
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.
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

Adjacency Matrix Overhead on Sparse Graphs

Prim's algorithm needs fast "what are this vertex's neighbors" access, which favors an adjacency list or matrix — on a very sparse graph represented awkwardly (e.g., only as a raw edge list), Kruskal's algorithm can be simpler to apply directly. And like Kruskal's, Prim's algorithm computes an MST that is unaffected by negative weights (unlike shortest-path algorithms) — but it says nothing about shortest paths between vertices; an MST edge is not necessarily on the shortest path between its endpoints once other routes exist.

Cookie Consent

Prim's Algorithm

Contents

A Bit of History

Working Principle

Prim grows one connected territory outward

Analogy: An Expanding Territory, Always Annexing the Cheapest Neighbor

What the Priority Queue Is Really Doing

Worked Example

Watch the tree grow from the seed vertex A

Correctness via the Cut Property

The current tree creates the cut automatically

Why Prim Does Not Need a Separate Cycle Check

Complexity Analysis

Implementation

Prim vs. Kruskal

Real-World Applications

Incremental Network Rollout

Exercises

Limitations

Adjacency Matrix Overhead on Sparse Graphs

Cookie Consent

Prim's Algorithm

Contents

A Bit of History

Working Principle

Prim grows one connected territory outward

Analogy: An Expanding Territory, Always Annexing the Cheapest Neighbor

What the Priority Queue Is Really Doing

Worked Example

Watch the tree grow from the seed vertex A

Correctness via the Cut Property

The current tree creates the cut automatically

Why Prim Does Not Need a Separate Cycle Check

Complexity Analysis

Implementation

Prim vs. Kruskal

Real-World Applications

Incremental Network Rollout

Exercises

Limitations

Adjacency Matrix Overhead on Sparse Graphs

Related Deep Dives

Graph Theory Series

Kruskal's Algorithm

Dijkstra's Algorithm