Prim’s Algorithm¶
A greedy minimum-spanning-tree algorithm that grows one connected tree from a chosen start vertex by repeatedly adding a cheapest edge crossing from the current tree to an unreached vertex.
Core Idea¶
Prim's algorithm maintains one connected partial tree. At each iteration it selects a cheapest edge with exactly one endpoint in that tree, adds the edge and outside endpoint, and thereby expands without forming a cycle.
Correctness follows from the cut property: a minimum-weight edge crossing the reached–unreached cut can be included in a minimum spanning tree. Efficient implementations store each outside vertex's cheapest known connection and update it as the frontier changes.
Structural Signature¶
Sig role-phrases:
- Weighted undirected graph — Supplies vertices, edges, and comparable costs. It is input structure. Counterfactual: Direction or missing weights changes the problem.
- Start vertex — Seeds the single growing component. It is initial state. Counterfactual: No seed means no defined first tree cut.
- Reached set — Identifies vertices already in the partial tree. It is tree state. Counterfactual: Losing connected growth changes the algorithm.
- Cut-crossing edge — Connects reached and unreached vertices. It is eligibility rule. Counterfactual: An internal edge creates a cycle and adds no vertex.
- Minimum-edge choice — Selects a cheapest eligible edge under ties. It is greedy rule. Counterfactual: A nonminimum crossing choice can destroy optimality.
- Priority data structure — Maintains best current connection efficiently. It is implementation layer. Counterfactual: Its choice affects runtime but not the greedy identity.
What It Is Not¶
- It is not Dijkstra's algorithm despite similar priority-queue code.
- It does not sort and consider every edge globally as Kruskal's algorithm does.
- The basic single run assumes the relevant component is connected.
- Equal-weight ties may change the returned tree without changing minimum total weight.
- Closest near-miss. Dijkstra may use a similar priority queue but keys vertices by source-path distance; Prim keys them by cheapest single edge into the current tree.
Scope of Application¶
- Network design. Finds least-total-cost connections in undirected models.
- Algorithm education. Demonstrates cut-based greedy correctness.
- Dense graph computation. Supports efficient array-based implementations.
- Sparse graph computation. Uses priority queues for improved asymptotic cost.
Clarity¶
State graph direction, weight domain, connectivity assumption, start choice, tie handling, and data structure. Define vertex keys as cheapest incident edge from the current tree, not path length, and attach runtime claims to the implementation used.
Manages Complexity¶
The algorithm reduces a global combinatorial objective to a sequence of locally safe cut choices. Its conceptual state is small, but data-structure operations, density, disconnected inputs, and ties determine performance and output multiplicity.
Abstract Reasoning¶
- Verify the graph is weighted and undirected and decide how to handle disconnected components.
- Choose a start vertex and initialize outside-vertex keys.
- Extract an unreached vertex with minimum connection cost.
- Add its connecting edge and update neighboring keys and predecessors.
- Check spanning, acyclicity, total weight, tie policy, and implementation-specific complexity.
Knowledge Transfer¶
The safe-choice proof transfers to objectives satisfying the minimum-spanning-tree cut property. Similar-looking priority-queue growth does not transfer the result to directed graphs, shortest paths, or constrained networks without a new proof.
Examples¶
Canonical¶
Beginning at vertex A, the algorithm keeps each outside vertex's cheapest edge to the reached set, adds the smallest such edge and endpoint, updates adjacent keys, and repeats until all vertices are in one tree.
Mapped back: input → weighted undirected graph; state → one reached tree; choice → cheapest crossing edge; output → minimum spanning tree.
Applied / In Practice¶
Selecting the unreached vertex with smallest accumulated distance from A computes shortest paths in Dijkstra's algorithm, not Prim's minimum spanning tree.
Mapped back: key → path distance; objective → shortest paths; verdict → different algorithm.
Structural Tensions¶
T1 — Abstract Greedy Rule versus Implementation Cost. The same safe-edge choice has different runtimes under arrays, binary heaps, Fibonacci heaps, and graph density.
Diagnostic: Is a complexity claim tied to the stated data structure?
T2 — Arbitrary Start versus Nonunique Output. Any start yields minimum total weight, while ties can produce different valid trees.
Diagnostic: Is the output claimed unique despite equal-weight choices?
Structural–Framed Character¶
Prim's Algorithm is structural as single-tree greedy cut expansion and framed by minimum-spanning-tree theory. The selected item is an edge crossing the current cut, and safety comes from its minimum weight on that cut.
Structural Core vs. Domain Accent¶
The general pattern is greedy expansion of a connected structure. Graph theory supplies vertices, weighted undirected edges, cuts, acyclicity, and total tree cost; swapping in path distance or directed reachability creates a different algorithmic abstraction.
Instantiates / Related Primes¶
This entry is a kind of Greedy Algorithm.
-
Approved unparented root. No reviewed parent entails the exact minimum-cut-edge growth procedure.
-
Related — Kruskal and Dijkstra. Kruskal shares the spanning-tree objective but not the single-tree process; Dijkstra shares implementation shapes but optimizes a different quantity.
Relationships to Other Abstractions¶
Current abstraction Prim’s Algorithm Domain-specific
Parents (1) — more general patterns this builds on
-
Prim’s Algorithm is a kind of Greedy Algorithm Prime
Prim's Algorithm is a Greedy Algorithm that repeatedly adds the cheapest edge crossing from a growing tree to an unreached vertex.Each irrevocable locally cheapest choice extends the solution, satisfying Greedy Algorithm while adding the MST cut rule. Greedy algorithms solve many problems other than spanning trees.
Hierarchy paths (2) — routes to 2 parentless roots
- Prim’s Algorithm → Greedy Algorithm → Heuristic → Approximation → Representation → Abstraction
- Prim’s Algorithm → Greedy Algorithm → Heuristic → Trade-offs → Constraint
Neighborhood in Abstraction Space¶
Prim’s Algorithm sits in a crowded region of the domain-specific corpus (33rd percentile for distinctiveness): several abstractions share nearly its structure, so a description that fits it tends to fit its neighbors too.
Family — Graph Structures & Algorithms (24 abstractions)
Nearest neighbors
- Loop (Graph Theory) — 0.89
- Geodetic Graph — 0.88
- Graph Power — 0.88
- Graph dynamical system — 0.88
- Utility graph — 0.88
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
- Dijkstra's algorithm. Tell: Minimizes distances from a source rather than total tree weight.
- Kruskal's algorithm. Tell: Adds globally light edges across a growing forest rather than one tree.
- Breadth-first search. Tell: Uses hop layers and ignores general edge weights.
- Minimum arborescence. Tell: Is the directed analogue and requires different algorithms.
References¶
- Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Prim%27s_algorithm (revision 1368985795).
- Preserved source candidate: https://archive.org/details/bstj36-6-1389
- Preserved source candidate: http://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/dijkstra.pdf
- Preserved source candidate: https://books.google.com/books?id=MTpsAQAAQBAJ&pg=PA628
- Preserved source candidate: https://books.google.com/books?id=6EJOCAAAQBAJ&pg=PA798
- Preserved source candidate: http://www.cs.utexas.edu/~vlr/papers/optmsf-jacm.pdf
- Preserved source candidate: https://books.google.com/books?id=JBXDc83jRBwC&pg=PA55
- Preserved source candidate: https://ncit-cluster.grid.pub.ro/trac/PP2009/export/157/proiecte/pgraph/Documentation/parallelspannintree.pdf
- Preserved source candidate: https://meyavuz.wordpress.com/2017/03/10/prims-algorithm-animation-for-randomly-distributed-points
The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.