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.
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. Inclusion test: Require a weighted undirected input and a connected partial tree that expands by a minimum-weight edge crossing to an unreached vertex until the component is spanned. Exclusion test: Exclude Dijkstra's shortest-path algorithm, Kruskal's globally sorted forest growth, breadth-first traversal, directed arborescence algorithms, and any heuristic choosing a nonminimum crossing edge. Nearest boundary: 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. Exit condition: The method exits when it grows several independent components simultaneously or optimizes path distances rather than total spanning-tree weight. Common misclassifications: 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. Nearest named distinctions: Dijkstra's algorithm: Minimizes distances from a source rather than total tree weight. Kruskal's algorithm: Adds globally light edges across a growing forest rather than one tree. Breadth-first search: Uses hop layers and ignores general edge weights. Minimum arborescence: Is the directed analogue and requires different algorithms.
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.
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.
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