Prim's · Minimum Spanning Tree

Same MST, different strategy from Kruskal. Prim grows a single tree from a start node, repeatedly absorbing the cheapest edge that reaches a node not yet in the tree.

Concept

Grow one tree

Start with any node. Look at all edges crossing from the tree to the outside (the cut). Pick the lightest one, add its far node to the tree, repeat until everyone's in.

The min-heap

Push edges from the newly added node
Pop the globally cheapest frontier edge
If its target is already in-tree, discard
Otherwise add it, then push its edges

Interactive

Absorb the cheapest frontier edge

Outside tree In tree Chosen edge Discarded

Frontier heap: empty

slowfast

Step 0

In tree

Total cost

MST edges

Heap size

Implementation

C++

int prim(int n, vector<vector<pair<int,int>>>& adj) {
    vector<bool> inMST(n, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>,
                   greater<>> pq;              // {weight, node}
    pq.push({0, 0});                        // start from node 0, cost 0

    int cost = 0, used = 0;
    while (!pq.empty() && used < n) {
        auto [w, u] = pq.top(); pq.pop();
        if (inMST[u]) continue;             // already absorbed, discard
        inMST[u] = true;
        cost += w; used++;
        for (auto& [v, wt] : adj[u])
            if (!inMST[v]) pq.push({wt, v});  // push frontier edges
    }
    return used == n ? cost : -1;    // -1 if disconnected
}

Complexity

Time

O(E log V)

Binary-heap version. Each edge can trigger one heap push.

Space

O(V + E)

Adjacency list, in-MST flags, and the heap.

Dense graphs

O(V²)

An array-based Prim beats the heap when E ≈ V².

Notes

Prim vs Kruskal: identical MST cost, different mechanics. Prim grows one connected tree; Kruskal merges a forest. Prim shines on dense graphs, Kruskal on sparse.
The if (inMST[u]) continue guard is lazy deletion, same trick as Dijkstra's stale-entry skip.
Prim needs a connected graph for a full MST; otherwise it only spans the start's component.
No Union-Find needed, the inMST flag alone prevents cycles.
Structurally almost identical to Dijkstra; the only change is pushing edge weight w instead of cumulative distance.