Skip to main content

Prim with Priority Queue

What This Concept Is​

Prim grows one tree by repeatedly choosing a minimum-weight edge crossing from its current vertices to the outside. A vertex key records the cheapest attachment edge, not a source-to-vertex route cost. An indexed heap can update these keys; a lazy edge heap can retain stale candidates and discard those whose endpoints are already in the tree.

Why It Matters Here​

Prim and Dijkstra look similar but prove different objectives. Using distance plus edge weight as a Prim key turns the computation toward shortest paths; using only edge weight as a Dijkstra key loses route-cost information.

Concrete Examples​

In triangle 0–1:2,0–2:3,1–2:2, start at 0. Choose 0–1 of weight 2, then attach 2 via 1–2 of weight 2. MST total is 4, but the tree path 0→1→2 costs 4, longer than direct 0→2 of cost 3. Dijkstra would preserve the direct route.

The proof names the cut: tree vertices versus remaining vertices. The chosen edge is light across that cut, which respects all previously chosen tree edges. The cut exchange argument preserves extension to an optimum at every step.

Common Confusion / Misconceptions​

A negative edge does not invalidate Prim: the objective is a finite forest sum, not repeated-walk shortest cost. A single start vertex reaches only its component. To produce a minimum spanning forest, restart from each unvisited vertex. A lazy heap may store O(E) candidate entries; do not assign an indexed heap's O(V) queue storage to it.

How To Use It​

Choose a representation and state the variant. Dense matrix Prim can use O(V²) time; indexed adjacency-list Prim uses O((V+E) log(V+1)) under its queue model. Lazy edge-heap costs can be expressed with log(E+2) and O(E) queue state. Tie order changes the witness but need not change optimal weight.

Check Yourself​

  1. What quantity belongs in Prim's key?
  2. Why is a negative edge harmless for this proof?
  3. What must change for disconnected input?
  4. When is an O(V²) matrix implementation a reasonable candidate?

Mini Drill or Application​

Implement Prim as an extension and compare forest cost and connectivity to Kruskal on small random graphs. Avoid requiring identical edge sets on ties. Deliberately use accumulated route distance as the key and find an objective counterexample. See P15.

Read This Only If Stuck​

Find Prim variants, cut invariants, and comparison with Dijkstra in Skiena, CLRS, or Sedgewick and Wayne. These are book indexes, not exact section links. The reading guide names bounded assignments and local source files. Attempt the worked examples before adding more reading.