Prim Algorithm
A greedy algorithm that builds a minimum spanning tree by growing a single tree one cheapest edge at a time
Prim's algorithm is a greedy algorithm for finding a minimum spanning tree of a connected, weighted graph by starting from an arbitrary vertex and repeatedly adding the cheapest edge that connects a vertex already in the tree to one that…
Definition
Prim's algorithm is a greedy algorithm for finding a minimum spanning tree of a connected, weighted graph by starting from an arbitrary vertex and repeatedly adding the cheapest edge that connects a vertex already in the tree to one that isn't.
Overview
Prim's algorithm, developed independently by Vojtěch Jarník in 1930 and later by Robert Prim in 1957 (and also independently by Edsger Dijkstra), takes a vertex-centric approach to building a minimum spanning tree, in contrast to Kruskal's edge-centric approach. It starts with a single arbitrary vertex as a one-node tree, and at each step, looks at every edge that connects a vertex already inside the tree to a vertex still outside it, and adds the cheapest such edge, pulling that new vertex into the tree. This process repeats until every vertex has been absorbed, at which point the tree is a minimum spanning tree. Unlike Kruskal's algorithm, Prim's never needs explicit cycle detection, since every edge it considers connects the tree to a vertex outside it by construction, meaning it can never close a cycle. The practical implementation challenge instead becomes efficiently finding the cheapest "crossing" edge at each step, which is typically solved with a min-priority queue that tracks, for each vertex outside the tree, the cheapest known edge connecting it to the tree so far, updating that value (a "decrease-key" operation) whenever a cheaper connecting edge is discovered. With a binary heap-based priority queue, this gives an overall time complexity of O(E log V); using a more sophisticated Fibonacci heap can improve this to O(E + V log V), which matters for very dense graphs. Prim's algorithm's correctness also follows from the cut property of minimum spanning trees, guaranteeing the greedy choice at each step never needs to be reconsidered. It's generally preferred over Kruskal's algorithm for dense graphs, since its running time depends more on the number of vertices relative to edges, and it has a natural conceptual similarity to Dijkstra's shortest-path algorithm — both grow outward from a starting vertex using a priority queue — though Prim's tracks the cheapest edge into the tree while Dijkstra's tracks the cheapest cumulative path distance from the source.
Key Concepts
- Greedy algorithm that grows a single tree outward from an arbitrary starting vertex
- At each step, adds the cheapest edge connecting the tree to an outside vertex
- Never requires explicit cycle detection, unlike Kruskal's algorithm
- Typically implemented with a min-priority queue tracking cheapest connecting edges
- O(E log V) time with a binary heap; O(E + V log V) with a Fibonacci heap
- Correctness guaranteed by the cut property of minimum spanning trees
- Well suited to dense graphs with many edges relative to vertices
- Conceptually similar in structure to Dijkstra's shortest-path algorithm
Use Cases
Frequently Asked Questions
From the Blog
Feature Engineering: Turning Data Into Signal
Feature engineering turns raw columns into inputs a model can actually learn from. Learn the core techniques that often matter more than the algorithm itself.
Read More ProgrammingWhat Is Big O Notation? A Beginner Guide
Big O notation describes how an algorithm's time or memory grows as input size increases. Learn the common complexities and how to analyze your own code.
Read More Data ScienceWhat Is Feature Engineering in Machine Learning?
Feature engineering is transforming raw data into inputs that help models learn. Good features often matter more than the algorithm. Learn the core techniques here.
Read More AI & TechnologyWhat Is Gradient Descent Explained for Beginners
Gradient descent is the algorithm that trains most machine learning models by repeatedly nudging parameters in the direction that reduces error, step by step.
Read More