Prim's algorithm

Grow one connected tree with the cheapest edge crossing the current cut. · 11 min read

Concept

Prim's algorithm starts from any vertex and grows one connected tree. At every step, it looks at the cut between vertices already in the tree and vertices outside it, then takes the cheapest edge crossing that cut.

Interactive visualization: Prim: grow across the cheapest cut edge — step through it frame by frame on this page.

Priority-queue version

vector<vector<pair<int,int>>> adj(n); // {to, weight}
vector<bool> used(n, false);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;

pq.push({0, 0}); // cost, vertex
long long total = 0;
int taken = 0;

while (!pq.empty()) {
    auto [cost, u] = pq.top(); pq.pop();
    if (used[u]) continue;
    used[u] = true;
    total += cost;
    taken++;

    for (auto [v, w] : adj[u]) {
        if (!used[v]) pq.push({w, v});
    }
}

if (taken != n) cout << "no spanning tree\n";
else cout << total << '\n';

Why Prim is correct

Growing one safe edge at a time

visited vertices define a cut — Inside the current tree vs outside it.
choose the lightest edge crossing the cut — This is exactly what the priority queue is trying to expose.
the cut property says that edge is safe — Some MST contains it.
add the outside endpoint — The selected edges remain connected and acyclic.

Result: Prim repeatedly applies the cut property

Kruskal vs Prim

Kruskal is edge-centric: sort all edges and use DSU to avoid cycles. It is simple when the input is already an edge list. Prim is vertex-centric: grow from a start vertex using adjacency lists and a priority queue. It is often natural for dense connected graphs or when the graph is stored as neighbours.

Complexity

With adjacency lists and a binary heap, Prim is O(E log V) time and O(V + E) space. With an adjacency matrix and no heap, the classic dense-graph version is O(V^2) time.

Practice: Second Best MST (Hard) — Find the cheapest spanning tree whose total weight is strictly larger than the MST.