Prim's Algorithm

Prim's algorithm (also known as the Jarník–Prim–Dijkstra algorithm) is a greedy graph optimization algorithm within computation and algorithms that computes a minimum spanning tree (MST) for a connected, edge-weighted undirected graph G = (V, E, w). First formulated by Czech mathematician Vojtěch Jarník in 1930, independently rediscovered by Robert C. Prim at Bell Laboratories in 1957 to design minimum-mileage telephone trunk networks, and reformulated with vertex distance tables by Edsger W. Dijkstra in 1959, the algorithm grows a single connected tree T outward from an arbitrary root vertex r ∈ V. At each of |V| − 1 steps, Prim's algorithm selects the minimum-weight edge (u, v) having one endpoint u inside the current tree vertex set S and the other endpoint v outside S, adding v and (u, v) to the tree.

Whereas Kruskal's algorithm sorts all |E| edges globally and merges scattered forest components via a disjoint-set data structure, Prim's algorithm maintains connectivity as an invariant throughout execution and tracks only the single lightest incident edge from S to each external vertex v ∈ V \ S using a priority queue. Paired with an unsorted array, Prim's algorithm executes in O(|V|²) time—which is asymptotically optimal for dense graphs where |E| = Θ(|V|²)—and paired with a Fibonacci heap, it achieves O(|E| + |V| log |V|) time within computational complexity theory.

Single-Tree Frontier Expansion and Vertex Keys

Let G = (V, E, w) be a connected undirected graph with vertex set V, edge set E, and real weight function w : E → ℝ. Starting from an arbitrary root vertex r ∈ V, Prim's algorithm maintains a growing tree vertex set S ⊆ V and a priority queue Q = V \ S containing all vertices not yet annexed into the tree. Rather than storing all candidate edges crossing the cut (S, V \ S), the vertex-centric formulation stores at most |V| elements by maintaining two values for every vertex v ∈ V:

• *key*[v]: the minimum weight w(u, v) of any edge connecting v to a vertex u ∈ S (initialized to *key*[r] = 0 and *key*[v] = +∞ for all v ≠ r).
• π[v]: the parent vertex u ∈ S achieving that minimum crossing weight *key*[v] = w(π[v], v) (initialized to NIL).

In each iteration while Q ≠ ∅, the algorithm extracts the vertex u ∈ Q minimizing *key*[u], transfers u into S (adding edge (π[u], u) to T when u ≠ r), and inspects every neighbor v ∈ *Adj*[u]:

Inductive Proof via the Cut Property

Correctness follows from the loop invariant that prior to each iteration, the selected edge set A = {(π[v], v) : v ∈ S \ {r}} is a subset of some minimum spanning tree T* of G. Suppose the invariant holds when A ⊆ T* spans vertex set S, and the algorithm extracts u ∈ V \ S minimizing *key*[u]. By definition of key, the edge e = (π[u], u) is a minimum-weight edge crossing the cut (S, V \ S), and no edge in A crosses (S, V \ S).

If e ∉ T*, adding e to T* creates a fundamental cycle C in T* ∪ {e} that must cross (S, V \ S) along at least one other edge e′ ∈ T* \ A. Because e is a lightest edge across (S, V \ S), w(e) ≤ w(e′). Exchanging e′ for e yields a spanning tree T*′ = (T* \ {e′}) ∪ {e} of weight w(T*′) = w(T*) − w(e′) + w(e) ≤ w(T*), proving that T*′ is also a minimum spanning tree containing A ∪ {e}.

Structural Comparison with Dijkstra's and A* Relaxation Rules

The control flow of Prim's algorithm is identical to that of Dijkstra's algorithm and the A* search algorithm, differing only in the priority-queue key assignment:

• Prim's Key: *key*[v] = min_u∈S w(u, v), measuring the local single-edge distance from v to the nearest vertex in S. Because *key*[v] does not accumulate root-to-node path sums, Prim's algorithm works without modification on graphs with negative edge weights w(u, v) < 0.
• Dijkstra's Key: d[v] = min_u∈S (d[u] + w(u, v)), measuring cumulative path distance from the fixed root r, which requires w(u, v) ≥ 0.

Dense Matrix vs. Heap Complexity Scaling

Across a complete run on a connected graph G = (V, E), Prim's algorithm executes |V| Extract-Min operations and at most |E| Decrease-Key operations:

Notice why the classic unsorted-array implementation of Prim's algorithm (O(|V|²)) outperforms Kruskal's algorithm (O(|V|² log |V|)) on complete graphs such as pairwise biological distance matrices: unsorted-array Prim evaluates pairwise distances w(u, v) on the fly in O(|V|) space and O(|V|²) time without materializing or sorting Θ(|V|²) edges.

Advanced Hybridization: Fredman–Tarjan and Chazelle's Soft-Heap Bounds

In 1987, Michael Fredman and Robert Tarjan combined Prim's single-tree growth with Borůvka-style graph contraction: growing local Prim trees only until their Fibonacci heap reaches size k, contracting the resulting trees into super-vertices, and repeating with packet size k′ = 2^k achieves O(|E| β(|E|, |V|)) time, where β(|E|, |V|) ≤ log* |V|. Bernard Chazelle (2000) later achieved O(|E| α(|E|, |V|)) deterministic time using soft heaps.

In computational geometry and operations research, Prim's algorithm constructs Euclidean Minimum Spanning Trees (EMSTs) and serves as the first stage of the Christofides–Serdyukov 3/2-approximation algorithm for the metric Traveling Salesperson Problem (TSP). In molecular phylogenetics, distance-based tree reconstruction engines run O(|V|²) array-based Prim's algorithm on dense N × N evolutionary distance matrices to seed initial topologies before maximum-likelihood branch length optimization.

Does the choice of starting root vertex r change the output of Prim's algorithm?

When all edge weights in G are distinct, the minimum spanning tree is unique and Prim's algorithm constructs the same set of |V| − 1 edges regardless of which root vertex r ∈ V initializes *key*[r] = 0; only the orientation of parent pointers π[v] and the annexation order change.

When should Prim's algorithm be preferred over Kruskal's algorithm?

Prim's algorithm is preferred on dense graphs (|E| ≈ |V|²) where evaluating edge weights on demand in O(|V|²) time and O(|V|) space avoids sorting Θ(|V|²) edges. Kruskal's algorithm is preferred on sparse graphs (|E| = O(|V|)) or disconnected graphs requiring a minimum spanning forest.

1. Jarník, V. (1930). "O jistém problému minimálním." Práce Moravské Přírodovědecké Společnosti, 6, 57–63. https://dml.cz/handle/10338.dmlcz/500726
2. Prim, R. C. (1957). "Shortest connection networks and some generalizations." Bell System Technical Journal, 36(6), 1389–1401. https://doi.org/10.1002/j.1538-7305.1957.tb01515.x
3. Fredman, M. L., & Tarjan, R. E. (1987). "Fibonacci heaps and their uses in improved network optimization algorithms." Journal of the ACM, 34(3), 596–615. https://doi.org/10.1145/28869.28874
4. Karger, D. R., Klein, P. N., & Tarjan, R. E. (1995). "A randomized linear-time algorithm to find minimum spanning trees." Journal of the ACM, 42(2), 321–328. https://doi.org/10.1145/201019.201022
5. Chazelle, B. (2000). "A minimum spanning tree algorithm with inverse-Ackermann type complexity." Journal of the ACM, 47(6), 1028–1047. https://doi.org/10.1145/355541.355562