Minimum Spanning Tree: Prim's Algorithm

Grow the minimum spanning tree one vertex at a time from a chosen start vertex, always picking the cheapest edge that connects a tree vertex to a non-tree vertex — implemented with a binary heap for O((V + E) log V) total time.

Same goal, different greedy

Like Kruskal, Prim's algorithm builds a minimum spanning tree of a connected, undirected, weighted graph. The difference is how it grows the tree:

Kruskal is edge-centric — scan all edges in order of weight, add an edge if it connects two different components.
Prim is vertex-centric — pick any starting vertex, then repeatedly add the cheapest edge that connects a tree vertex to a non-tree vertex, until all vertices are in the tree.

Prim grows one connected blob outward; Kruskal merges separate blobs. They produce trees with the same total weight (though possibly different edges if there are ties).

Prim is the algorithm of choice when the graph is dense or already stored as an adjacency list / matrix — there is no separate sort step, just a priority queue of candidate edges.

The algorithm — maintain `key[v]` and a min-priority queue

Maintain a set T of tree vertices and arrays:

key[v] — the weight of the cheapest edge from v to any tree vertex (or ∞ if none yet). For the start vertex s, key[s] = 0.
parent[v] — the tree vertex that would connect v to the tree via the edge of weight key[v].
inTree[v] — boolean, true once v is added to the tree.

Main loop:

Pick the non-tree vertex u with smallest key[u] (use a min-heap).
Mark u in-tree; the edge (parent[u], u, key[u]) joins the MST.
Relax edges out of u: for every neighbor v not yet in the tree, if w(u, v) < key[v], set key[v] = w(u, v) and parent[v] = u.
Repeat until every vertex is in the tree.

Notice the pattern — exactly like Dijkstra's shortest-path algorithm, except key[v] here measures the best single edge from the tree, not a path length.

Step-by-step visualization

Run Prim on the same graph as in Kruskal's chapter, starting at vertex 1. Step forward and backward with the ← / → arrow keys or the buttons below.

Watch the tree grow outward as one connected blob:

Cyan vertices are on the fringe — discovered, sitting in the min-heap with a finite key. Amber is the vertex just popped; green vertices are settled in the tree, connected by the green MST edges.
Each vertex's k= label is the weight of the cheapest known edge linking it to the tree — watch key[6] improve from ∞ → 8 → 7 as a better connection is found.
The min-heap panel shows every (key, vertex) entry, including the stale (8, 6) left behind after the improvement — it gets popped and skipped near the end, exactly how lazy deletion works in real implementations.

All 6 vertices end up in the tree with total weight 33 — the same as Kruskal, via a completely different growth order.

Not reached (key = ∞)Fringe (in the heap)Current (just popped)In the tree

Min-heap

(0, 1)

key[]

∞

parent[]

–

MST0/5 edges · cost = 0

Start Prim from vertex 1: key[1] = 0, every other key is ∞. Push (0, 1) onto the min-heap.

1 / 31

Speed

Tip: step through with the ← / → arrow keys.

Why Prim's is correct

At every step Prim picks the cheapest edge crossing the cut between the tree set T and the non-tree set V \ T. By the cut property:

The cheapest edge crossing any cut belongs to some MST.

So every edge Prim adds belongs to some MST, and the set of chosen edges stays a subset of some MST throughout. Since Prim eventually adds V - 1 edges and produces a spanning tree, that spanning tree is an MST.

The priority queue is just the efficient way to identify "cheapest edge crossing the cut" each step.

Pseudocode

The lazy-deletion heap version — the one you would actually write in a contest. Instead of a true decrease-key, we simply push a fresh (key, vertex) entry and skip any popped vertex that is already in the tree (the if inTree[u]: continue line — the stale entry you can watch being skipped in the visualization). The C++ tab runs on the visualization's graph and prints total weight 33.

1PRIM(V, adj, s):
2    for each v in V:
3        key[v]    = ∞
4        parent[v] = NIL
5        inTree[v] = false
6    key[s] = 0
7
8    PQ = min-priority queue keyed by key[v];  insert (0, s)
9
10    while PQ is not empty:
11        (k, u) = extract-min(PQ)
12        if inTree[u]: continue        // stale heap entry
13        inTree[u] = true              // edge (parent[u], u, k) joins the MST
14
15        for each (v, w) in adj[u]:
16            if not inTree[v] and w < key[v]:
17                key[v]    = w
18                parent[v] = u
19                insert (w, v) into PQ
20
21    return parent / total weight

Complexity analysis

Each vertex is extracted from the priority queue exactly once. Each edge is examined at most twice (once from each endpoint), and each examination may trigger a decrease-key (in practice: push a new entry onto the heap).

With a binary heap (or priority_queue<pair<int,int>>):

V extract-min operations × O(log V) = O(V log V).
E relaxations × O(log V) per push = O(E log V).
Total: O((V + E) log V).

With a Fibonacci heap: O(E + V log V) — better asymptotically but constants are worse, rarely used in practice.

With an adjacency matrix and a flat array as the priority queue (extract-min in O(V), decrease-key in O(1)): O(V²). This actually beats the heap version for very dense graphs where E ≈ V².

Space: O(V + E) for the heap, key/parent arrays, and adjacency list.

Complexity Analysis

Time Complexity

O((V + E) log V) with a binary heap; O(V²) with an array-based priority queue (better when the graph is dense); O(E + V log V) with a Fibonacci heap.

Space Complexity

O(V + E) — adjacency list + key / parent arrays + priority queue.

Prim is vertex-centric — it shines on dense graphs and when input is already an adjacency list. For graphs handed in as an edge list, or when the data is sparse, Kruskal is often simpler and just as fast.

Growth Rate Comparison