Skip to main content

Prim with Priority Queue

What This Concept Is​

Prim's algorithm grows one tree from an arbitrary root. At each step, it adds the minimum-weight edge that leaves the tree and goes into an out-of-tree vertex. A priority queue keyed on "minimum edge weight from the current tree to each out-of-tree vertex" does the bookkeeping:

for each v in V: key[v] := +infinity; parent[v] := null
key[r] := 0            # r is the root
Q := priority queue of all V, keyed by key
while Q is not empty:
    u := Q.extract-min()
    for each edge (u, v, w) in adj[u]:
        if v in Q and w < key[v]:
            key[v] := w
            parent[v] := u
            Q.decrease-key(v, w)

Each extract-min pulls one vertex into the tree. The edges (parent[v], v) for each v != r form the MST.

Total time:

  • Binary heap. O((|V| + |E|) log |V|).
  • Fibonacci heap. O(|E| + |V| log |V|).
  • Array. O(|V|^2), best on dense graphs.

Why It Matters Here​

Prim is structurally the same shape as Dijkstra - grow a tree from a root, maintain a "frontier" priority queue, extract min, relax. The difference is only what key[v] stores:

  • Dijkstra: key[v] = best known distance from s to v.
  • Prim: key[v] = minimum edge weight from the current tree to v.

Recognizing this similarity is not cosmetic - it tells you the same data structures and engineering tradeoffs apply, and it makes memorizing neither necessary.

Prim vs Kruskal:

  • Prim. Grows one tree; priority queue over vertices; best when graph is dense or adjacency lists are already in memory. Natural when you want the MST to grow incrementally from a known root.
  • Kruskal. Grows a forest; union-find over edges; best when graph is sparse or edges are already sorted. Produces MST edges in weight order as a by-product.

Both compute an MST in O(|E| log |V|) for the standard implementations; the choice is about the input format and downstream bookkeeping, not asymptotic cost.

Concrete Example​

Graph:

Start at a. Initial key = [a:0, b:inf, c:inf, d:inf, e:inf].

stepextract (key)updates afterparent updatesin-tree
1a (0)b:1, c:5parent[b]=a, parent[c]=a{a}
2b (1)c:2, d:3 (beats 5/inf)parent[c]=b, parent[d]=b{a,b}
3c (2)d: no (4>3), e:6parent[e]=c{a,b,c}
4d (3)e: no (7>6)unchanged{a,b,c,d}
5e (6)--{a,b,c,d,e}

MST edges: (a,b), (b,c), (b,d), (c,e). Total weight 1 + 2 + 3 + 6 = 12 - same as Kruskal, as expected.

Common Confusion / Misconceptions​

  • "Prim and Dijkstra are the same algorithm." Same shape, different objective. Dijkstra relaxes dist[u] + w; Prim relaxes with raw edge weight w. Swapping them silently gives you a shortest-path tree instead of an MST (or vice versa).
  • "Prim builds an MST rooted at the start vertex." The MST is unique (for distinct weights) and does not depend on the root. Different roots produce the same edge set; only the traversal order differs.
  • "decrease-key is cheap in a binary heap." It requires an index from vertex-id to heap-position, or lazy deletion. The idiomatic lazy-deletion variant pushes duplicates and discards stale pops.
  • "Prim cannot produce a minimum spanning forest." It cannot directly; it grows one tree and terminates when that tree spans one component. For forests, run Prim from each unvisited vertex - or just use Kruskal.
  • "Dense graphs need Fibonacci heaps." On truly dense graphs (|E| = Theta(|V|^2)), the O(|V|^2) array-based Prim beats both binary heap and Fibonacci heap.

How To Use It​

For most production cases, use the binary-heap version. Implement it with lazy deletion (push updated pairs, skip stale pops) to avoid costly decrease-key:

heap := [(0, r)]
in_tree[v] := false; key[v] := +inf; key[r] := 0
while heap not empty:
    (w, u) := heap.extract-min()
    if in_tree[u]: continue
    in_tree[u] := true
    add edge via parent[u] if u != r
    for each (u, v, ww) in adj[u]:
        if not in_tree[v] and ww < key[v]:
            key[v] := ww
            parent[v] := u
            heap.push((ww, v))

Use the array-based variant O(|V|^2) if the graph is so dense that |E| = Theta(|V|^2).

Integration tips:

  • remember to initialize key[r] = 0 exactly once; all others +infinity
  • track in_tree[] explicitly so the lazy pop check is O(1)
  • if you need the MST edges in weight-order at the end, sort the edges of the final tree; do not try to extract in-order during the run

Transfer / Where This Shows Up Later​

  • S3 (systems). Building cluster-wide spanning trees for monitoring or log shipping uses Prim with latency weights.
  • S4 (compilers). Tree-shape extraction from CFGs and call graphs leans on Prim-like scaffolding.
  • S5 (OS). Multicast or broadcast tree construction in kernel-bypass NICs.
  • S6 (databases). Replication topology with cost-aware spanning trees for write fan-out.
  • S7 (DDD). When minimizing cross-context coupling, Prim over a weighted context-map picks the cheapest backbone.
  • S8 (distributed). Gossip-overlay and multicast trees, spanning-tree protocols in Ethernet (STP), and similar.

Back-link to concept 10 (Dijkstra) for the priority-queue scaffold comparison, and to concept 13 for the cut-property correctness proof.

Check Yourself​

  1. Explicitly compare Prim and Dijkstra: what is the same, what is different?
  2. Why does the cut property justify Prim: which cut is being processed at each extract-min?
  3. For a dense graph with |V| = 1000, estimate the runtime of Prim with a binary heap vs an array.
  4. What does parent[] represent at the end of Prim, and how do you reconstruct the MST edges from it?
  5. Give one graph where Prim and Kruskal produce different edge sets with equal total weight, and one where they produce the same set.
  6. Why does choosing a different root not change the total weight of the MST?

Mini Drill or Application​

Run Prim from vertex a on

a - b (7), a - d (5)
b - c (8), b - d (9), b - e (7)
c - e (5)
d - e (15), d - f (6)
e - f (8), e - g (9)
f - g (11)

Record the extraction order and the final MST weight.

Implementation drill.

  1. Implement binary-heap Prim with lazy deletion.
  2. Implement array-based O(|V|^2) Prim.
  3. Run both on a complete graph of 200 vertices with random [1, 100] weights; verify total weight matches your Kruskal implementation on the same graph.
  4. Benchmark all three (heap Prim, array Prim, Kruskal) on sparse, medium, and dense graphs; produce a short table of crossover densities.
  5. Use Prim to compute an MST of your university's campus as a weighted graph (distances between buildings); produce a minimal-cable layout.

Read This Only If Stuck​