Prim's Adjacency-List Implementation

From Prim’s Rule to an Implementation

Prim’s algorithm grows a tree from a chosen starting vertex. At each step it adds an outside vertex using a cheapest edge from that vertex to the current tree. An adjacency list lets the algorithm examine only the edges incident to a vertex just added. A priority queue lets it choose the outside vertex with the smallest current connection cost.

Here we consider finite, connected, simple, undirected graphs with a real weight \(w(e)\) on each edge. A spanning tree is a connected, cycle-free subgraph containing every vertex. This tutorial focuses on implementing Prim’s choices; the proof that those choices produce a minimum spanning tree is a separate correctness question. The implementation also detects when a graph is disconnected, in which case a spanning tree does not exist.

The priority queue stores pairs \((\operatorname{key}[v],v)\), ordered by key; ties may be settled by vertex label. When a key decreases, a standard priority queue could update the old entry using a decrease-key operation. Instead, we use lazy insertion: insert a new pair and leave the old one in the queue. An entry is stale if its recorded key no longer equals the vertex’s current key, or if that vertex has already joined the tree.

Initialization and the Key Invariant

Let \(r\) be the chosen root. Start with \(T=\{r\}\), set every other key to \(+\infty\), and scan the adjacency list of \(r\). For each neighbor \(v\), set \(\operatorname{key}[v]=w(rv)\), set \(\operatorname{parent}[v]=r\), and insert \((w(rv),v)\) into the queue. Only after this initial scan do we claim the key invariant: for every \(v\notin T\), its key equals the minimum weight of an edge from \(v\) to \(T\), or \(+\infty\) if there is no such edge. A finite key has a parent in \(T\) that realizes it.

This timing matters. Before the root’s adjacency list is scanned, an outside neighbor still has key \(+\infty\), even though an edge to the root exists. Initialization is therefore a separate step, not an instance of the invariant.

The update condition is strict. If an edge has the same weight as the current key, it is also a cheapest connection, but the algorithm can keep the existing parent. This avoids unnecessary queue entries and makes the chosen output depend consistently on the tie-breaking rule.

Proof. After initialization, \(T=\{r\}\). Scanning all edges incident to \(r\) assigns each outside neighbor the weight of its edge to \(r\); every other outside vertex has no edge to \(T\) and keeps key \(+\infty\). Thus the invariant holds. Now suppose it holds at the start of an iteration, and a valid queue entry selects \(v\notin T\). Before adding \(v\), every outside vertex \(x\) has the minimum weight of an edge from \(x\) to the old \(T\). After \(v\) is added, the only new possible edge from an outside \(x\) to the enlarged tree is \(xv\). If \(xv\) is an edge, scanning \(v\)’s adjacency list compares \(w(xv)\) with the old key. A strict decrease replaces the key and records \(v\) as parent; otherwise the old key remains a minimum. If \(xv\) is not an edge, the old minimum is unchanged. These cases cover every outside \(x\), so the invariant holds after the scan. \(\square\)

Why Lazy Queue Entries Are Safe

A vertex may have several entries in the queue because its key may have decreased more than once. The queue does not need to delete an older entry when this happens. On removal, the algorithm compares the recorded value with the vertex’s current key and checks whether the vertex is already in \(T\).

Proof. If the vertex is already in \(T\), it is not eligible to be selected again. If the recorded key differs from the current key, that entry does not represent the vertex’s current connection cost. Every outside vertex with a finite current key has an entry for that key: initialization inserts entries for root neighbors, and every later strict key decrease inserts a new entry. Therefore, after stale entries are discarded, the first valid entry removed has minimum current key among the outside vertices with finite keys. Discarding the stale entry cannot remove that current minimum. \(\square\)

Keys only decrease, and each change inserts an entry with the new value. Thus an older entry for the same vertex has a larger recorded key and fails the equality test. Once a vertex has been added, all its entries fail the membership test. The algorithm can stop immediately when all vertices have been added rather than emptying the queue.

Worked Traces

Implementation Details and Common Pitfalls

For an undirected graph, an adjacency list stores each edge \(uv\) in the lists of both \(u\) and \(v\), with its weight. When a vertex joins \(T\), scan its list and ignore neighbors already in \(T\). For an outside neighbor, compare the edge weight with that neighbor’s current key and update only on a strict decrease. The parent edge recorded at that moment is the edge used when the neighbor is eventually selected.

The most important initialization pitfall is claiming that all keys already represent minimum edges to \(T\) before scanning the root. For example, with \(V=\{r,a\}\), \(E=\{ra\}\), and \(w(ra)=6\), setting \(\operatorname{key}[a]=+\infty\) and immediately asserting that it is the minimum edge weight to \(T=\{r\}\) is false: that minimum is \(6\). The correction is to scan \(r\)’s adjacency list first, set \(\operatorname{key}[a]=6\), and only then use the invariant.

Other errors to avoid include treating an old queue entry as current after a decrease, changing a parent when an equal-weight edge is found despite using strict updates, and continuing to claim a spanning tree exists when the queue empties with vertices still outside \(T\). A one-vertex graph is a valid special case: with \(V=\{r\}\) and \(E=\varnothing\), initialization leaves no outside vertices, and the spanning tree has no edges.

The adjacency-list implementation makes the connection-cost rule explicit: each vertex stores its best known way into the current tree, and each newly added vertex can improve those costs only through its incident edges. Lazy insertion keeps the queue logic simple, while the stale-entry test ensures that only current keys determine the next choice.