Why the Representation Changes the Running Time
Prim’s algorithm grows a tree from a starting vertex, repeatedly adding a least-weight edge from the vertices already reached to a vertex not yet reached. Its correctness depends on the cut property, established in the earlier material on minimum spanning trees. Here the question is computational: how much work does the algorithm perform when the graph is stored in different ways?
Throughout, let \(G=(V,E)\) be a finite, connected, simple, undirected graph with real edge weights, \(n=|V|\ge 1\), and \(m=|E|\). Ties between edge weights may be resolved arbitrarily. A minimum spanning tree is a spanning tree of minimum total edge weight. The connectedness assumption ensures that Prim can reach every vertex and produce a spanning tree. If the graph is disconnected, the same implementation can instead be restarted in each component to produce a spanning forest.
The key for the starting vertex is initialized to \(0\), and all other keys to \(+\infty\). This makes the start the first vertex selected; its key is not the weight of an edge in the output tree. Each later selected vertex contributes its parent edge. We compare two implementations of these same steps, not two different algorithms.
Adjacency Matrix: Quadratic Time
An adjacency matrix stores whether each pair of vertices is adjacent and, if so, the edge weight. To find the next vertex, the matrix implementation scans the keys of all unchosen vertices and selects a minimum. After adding a vertex, it scans that vertex’s entire matrix row to find its neighbors and possibly lower their keys.
Proof. Suppose \(i\) vertices have already been added. There are \(n-i\) unchosen vertices. Selecting a minimum from \(n-i\) keys takes at most \(n-i-1\) comparisons: after the first key is the current candidate, each of the other \(n-i-1\) keys is compared with it. Thus the total number of key comparisons for selection is at most \((n-1)+(n-2)+\cdots+1+0=n(n-1)/2\), which is \(O(n^2)\).
Each of the \(n\) vertices is added once, and the algorithm scans \(n\) entries in its matrix row when it is added. These row scans use \(n\cdot n=n^2\) matrix-entry inspections. Initialization and parent-record maintenance take \(O(n)\) additional time. The selection work and row scans therefore take \(O(n^2)\) altogether. Moreover, scanning all \(n\) rows takes \(n^2\) entry inspections, so the implementation takes \(\Omega(n^2)\) time as well. Hence its running time is \(\Theta(n^2)\). \(\square\)
The statement counts the usual full row scans, even when some entries correspond to absent edges or to vertices already in the tree. For \(n=1\), the algorithm returns the one-vertex tree with no edge; the asymptotic bound is understood for growing \(n\).
Worked Example: Prim with an Adjacency Matrix
Let \(G\) have vertex set \(V=\{1,2,3,4,5\}\) and edge set \(E=\{12,13,23,24,34,35,45\}\), with weights \(w(12)=2\), \(w(13)=6\), \(w(23)=3\), \(w(24)=5\), \(w(34)=1\), \(w(35)=4\), and \(w(45)=2\). Start at vertex \(1\). A key list below is ordered \(1,2,3,4,5\); “done” means the vertex has already been added.
| Step | Selected vertex | Key changes from its row | Keys after the step |
|---|---|---|---|
| Start | None | Set key of 1 to 0 | \((0,\infty,\infty,\infty,\infty)\) |
| 1 | 1, key 0 | Edge 12 sets key 2 to 2; edge 13 sets key 3 to 6 | \((\text{done},2,6,\infty,\infty)\) |
| 2 | 2, key 2 | Edge 23 lowers key 3 from 6 to 3; edge 24 sets key 4 to 5 | \((\text{done},\text{done},3,5,\infty)\) |
| 3 | 3, key 3 | Edge 34 lowers key 4 from 5 to 1; edge 35 sets key 5 to 4 | \((\text{done},\text{done},\text{done},1,4)\) |
| 4 | 4, key 1 | Edge 45 lowers key 5 from 4 to 2 | \((\text{done},\text{done},\text{done},\text{done},2)\) |
| 5 | 5, key 2 | No unreached neighbor remains | All vertices done |
The parent edges are \(12,23,34,45\), with weights \(2,3,1,2\). Their total is \(2+3+1+2=8\). They form a spanning tree: the four edges join the five vertices in the path \(1,2,3,4,5\), so the result is connected and has no cycle. As an operation count, the selection scans use at most \((5-1)+(5-2)+(5-3)+(5-4)+(5-5)=4+3+2+1+0=10\) key comparisons. The five full matrix-row scans inspect \(5\cdot5=25\) entries.
Check: The graph has \(m=7\) edges, so its undirected adjacency lists would contain \(2m=2\cdot7=14\) edge entries. The matrix method’s \(25\) row-entry inspections are consistent with scanning all five columns of each of five rows, including entries for absent edges.
Adjacency Lists and an Indexed Binary Heap
An adjacency list stores the neighbors of each vertex and the weight of each incident edge. In an indexed binary min-heap, each unreached vertex appears once, with its current key as its priority; an index table locates a vertex in the heap so its key can be decreased in place. This detail matters: it avoids inserting repeated copies of a vertex when its key improves.
A binary heap stores its entries in a complete binary tree, with each parent having priority no greater than its children. Its height is at most \(\lfloor\log_2 n\rfloor\) when it contains at most \(n\) entries. Inserting, extracting a minimum, or decreasing a key takes \(O(\log n)\) time: the entry may move along a heap path, whose length is at most the heap’s height.
Proof. Insert the \(n\) vertices into the heap with their initial keys. These insertions take \(O(n\log n)\) time. The algorithm extracts each vertex exactly once, for \(n\) extractions taking \(O(n\log n)\) time in total.
Across all adjacency lists, each undirected edge appears twice, once at each endpoint, so the algorithm inspects \(2m\) edge entries and spends \(O(m)\) time on these inspections apart from heap operations. A key can decrease only when an edge is inspected and its opposite endpoint is still unreached. Since each undirected edge is useful for such a test only when its first endpoint is added, there are at most \(m\) successful decreases. Each decrease-key operation costs \(O(\log n)\), so all successful decreases take \(O(m\log n)\) time. Combining the costs gives \(O(n\log n+m+m\log n)=O((n+m)\log n)\).
Because the graph is connected and \(n\ge2\), it has at least \(n-1\) edges, so \(n\le m+1\). Consequently \(n+m\le 2m+1\le3m\) for \(m\ge1\), giving \(O((n+m)\log n)=O(m\log n)\). The algorithm returns a minimum spanning tree by the cut-property correctness result for Prim’s algorithm: at each step it chooses a lightest edge crossing from the reached vertices to the unreached vertices. \(\square\)
The \(O(m\log n)\) statement is for connected graphs with \(n\ge2\). A one-vertex graph has \(m=0\) and is handled directly; writing a bound such as \(O(m\log n)\) for that case would obscure the fact that initialization still takes time. If the input is disconnected and the algorithm is restarted in each component, the operation count can instead be expressed as \(O((n+m)\log n)\) for the resulting spanning forest.
Worked Example: Heap Operations on the Same Graph
Use \(V=\{1,2,3,4,5\}\), \(E=\{12,13,23,24,34,35,45\}\), and weights \(2,6,3,5,1,4,2\), respectively, as in the preceding example. Start at \(1\). The heap begins with key \(0\) for vertex \(1\) and \(+\infty\) for the other four vertices. The table records all successful decreases; a change such as \(6\to3\) is one decrease-key operation.
| Extracted vertex | Incident-edge inspections that improve a key | Keys of unreached vertices afterward |
|---|---|---|
| 1, key 0 | 12 gives key 2 of 2; 13 gives key 3 of 6 | \(2:2,\ 3:6,\ 4:\infty,\ 5:\infty\) |
| 2, key 2 | 23 changes key 3 from 6 to 3; 24 gives key 4 of 5 | \(3:3,\ 4:5,\ 5:\infty\) |
| 3, key 3 | 34 changes key 4 from 5 to 1; 35 gives key 5 of 4 | \(4:1,\ 5:4\) |
| 4, key 1 | 45 changes key 5 from 4 to 2 | \(5:2\) |
| 5, key 2 | No key improves | None |
The extraction order is \(1,2,3,4,5\), and the parent edges are again \(12,23,34,45\). The output weight is \(2+3+1+2=8\), and the path through these edges includes all five vertices without a cycle. There are \(m=7\) edges, and the adjacency lists contain \(2\cdot7=14\) entries. The table records \(2+2+2+1+0=7\) successful decreases, which is no more than \(m=7\). Including five insertions and five extractions gives \(5+5+7=17\) heap operations. With at most five heap entries, the height is at most \(\lfloor\log_2 5\rfloor=2\), so each of those operations moves an entry through at most two heap levels.
Check: The key changes select the same four parent edges as the matrix implementation. Their weights sum to \(2+3+1+2=8\); the change in data structure affects the running time, not the tree produced by the algorithm.
How Density Affects the Comparison
A connected graph is sparse when its edge count is relatively small, for example \(m=\Theta(n)\), and dense when \(m=\Theta(n^2)\). A connected simple graph has at most \(n(n-1)/2\) edges. For sparse graphs, the heap bound \(O(m\log n)\) is \(O(n\log n)\), while the matrix implementation still takes \(\Theta(n^2)\). For dense graphs, substituting \(m=\Theta(n^2)\) into the heap bound gives \(O(n^2\log n)\); it does not give a quadratic bound. The matrix implementation remains \(\Theta(n^2)\).
Worked Example: Comparing Counts on a Dense Graph
Let \(G\) be the complete graph on \(V=\{1,2,3,4\}\), with edge set \(E=\{12,13,14,23,24,34\}\) and weights \(w(12)=1\), \(w(13)=4\), \(w(14)=6\), \(w(23)=2\), \(w(24)=5\), and \(w(34)=3\). Starting at \(1\), Prim first sets keys \(1,4,6\) for vertices \(2,3,4\). It selects \(2\), then changes the key of \(4\) from \(6\) to \(5\). It next selects \(3\), then changes the key of \(4\) from \(5\) to \(3\). Finally it selects \(4\). The chosen edges are \(12,23,34\), with total weight \(1+2+3=6\).
For this example \(n=4\) and \(m=6\), since the six listed edges are all the pairs of distinct vertices. The matrix selection scans use at most \((4-1)+(4-2)+(4-3)+(4-4)=3+2+1+0=6\) key comparisons, and its row scans inspect \(4\cdot4=16\) entries. The adjacency lists contain \(2\cdot6=12\) entries. The heap has four insertions, four extractions, and six successful key decreases: three when vertex \(1\) is processed, two when vertex \(2\) is processed, and one when vertex \(3\) is processed. Thus the table of operations gives \(4+4+6=14\) heap operations.
Check: The selected edge \(12\) is the lightest edge across the cut \(\{1\}\), with weight \(1\). Across \(\{1,2\}\), the crossing edges have weights \(4,6,2,5\), whose minimum is \(2\) on \(23\). Across \(\{1,2,3\}\), the crossing edges have weights \(6,5,3\), whose minimum is \(3\) on \(34\). Thus each selected edge is a lightest edge across its current cut, in agreement with the cut property.
Common Pitfalls
Off-by-one in the selection sum. A mistaken count says that selecting from \(n-i\) remaining keys takes \(n-i\) comparisons, then sums those quantities but reports \(n(n-1)/2\). These claims do not match: summing \(n-i\) for \(i=0,\ldots,n-1\) gives \(n+(n-1)+\cdots+1=n(n+1)/2\). The correction is that a minimum among \(n-i\) keys requires at most \(n-i-1\) comparisons, because the first key is the initial candidate. Summing the corrected counts gives \((n-1)+(n-2)+\cdots+1+0=n(n-1)/2\).
Calling the heap implementation quadratic on dense graphs. If \(m=\Theta(n^2)\), the binary-heap bound \(O(m\log n)\) becomes \(O(n^2\log n)\), not \(O(n^2)\). The matrix implementation has a \(\Theta(n^2)\) bound; a binary heap may add a logarithmic factor through its extract-min and decrease-key operations. These are upper bounds, not a claim that every dense input forces every heap operation to take its worst-case number of levels.
Confusing edge scans with heap operations. An adjacency-list implementation inspects \(2m\) list entries in an undirected graph, but not every inspection causes a heap update. The number of successful decreases is at most \(m\), and each such operation has a logarithmic cost. Counting only the edge inspections would omit the heap work; counting every inspection as a decrease-key would also be unjustified.
Check Your Understanding
Use the stated assumptions and count comparisons, edge entries, and heap operations separately where appropriate.
- For \(n=6\), how many key comparisons are made in the full selection scans of the adjacency-matrix implementation, using the bound proved above?
- Explain why the adjacency lists of an undirected graph with \(m\) edges contain \(2m\) edge entries.
- For a connected graph with \(n\ge2\) and \(m=\Theta(n)\), give the matrix and indexed-binary-heap running-time bounds.
- If a connected graph has \(m=\Theta(n^2)\), what bound follows for Prim’s indexed-binary-heap implementation? Why is it not the matrix bound?
- Why does an indexed heap permit the analysis to count at most one successful decrease-key operation per edge?