Prim's algorithm
Greedy algorithm for minimum spanning trees.
Prim's algorithm is a greedy method used in computer science to find a minimum spanning tree in a weighted, undirected graph. It works by selecting a starting vertex arbitrarily and then repeatedly adding the cheapest edge that connects the growing tree to a new vertex, building the tree one vertex at a time. The algorithm was originally developed in 1930 by Czech mathematician Vojtěch Jarník and later independently rediscovered by Joseph Kruskal (1956), Robert C. Prim (1957), and Edsger W. Dijkstra (1959). As a result, it is also known as Jarník's algorithm, the Prim–Jarník algorithm, the Prim–Dijkstra algorithm, or the DJP algorithm.
Other well-known algorithms for the same problem include Kruskal's and Borůvka's algorithms, which can find a minimum spanning forest in a possibly disconnected graph. In its basic form, Prim's algorithm only works on connected graphs, but it can be applied to each connected component separately to produce a minimum spanning forest. For sparse graphs, these three algorithms have similar asymptotic time complexity, though more sophisticated algorithms can be faster. For sufficiently dense graphs, Prim's algorithm can run in linear time, matching or improving the performance of other methods.
The algorithm can be implemented using a priority queue or simpler data structures. A straightforward implementation using an adjacency matrix or list and a linear search for the minimum-weight edge runs in O(|V|²) time. Using a binary heap to store vertices ordered by the smallest edge weight connecting them to the partial tree improves this to O(|E| log |V|). With a Fibonacci heap, the time complexity becomes O(|E| + |V| log |V|), which is asymptotically faster for dense graphs where |E| is ω(|V|), and linear when |E| is at least |V| log |V|. For even denser graphs (with |V|^c edges for some c > 1), a d-ary heap can achieve linear time more simply.
The algorithm's correctness relies on the fact that at each step, it picks the cheapest edge connecting the current subgraph to a vertex outside it. Since the graph is connected, such an edge always exists until all vertices are included, ensuring a minimum spanning tree is formed.
- field
- Computer science
- known_for
- Prim's algorithm (minimum spanning tree)
- type
- Algorithm
Lore & Background
Prim's algorithm is a greedy method used to find a minimum spanning tree in a weighted undirected graph, meaning it selects a subset of edges that connects all vertices with the smallest possible total edge weight. The algorithm builds this tree incrementally, starting from an arbitrary vertex and repeatedly adding the cheapest edge that connects a vertex already in the tree to a vertex outside it. Its development history spans several decades: the algorithm was first devised in 1930 by Czech mathematician Vojtěch Jarník, and was later independently rediscovered by Joseph Kruskal in 1956, Robert C. Prim in 1957, and Edsger W. Dijkstra in 1959. Consequently, it is also known as Jarník's algorithm, the Prim–Jarník algorithm, the Prim–Dijkstra algorithm, or the DJP algorithm. Unlike Kruskal's and Borůvka's algorithms, which can handle disconnected graphs to find a minimum spanning forest, the basic form of Prim's algorithm only works on connected graphs; however, it can be applied separately to each connected component to achieve the same result. For sparse graphs, all three algorithms have similar asymptotic time complexity, but for sufficiently dense graphs, Prim's algorithm can run in linear time, matching or surpassing the performance of more sophisticated approaches. The algorithm's correctness relies on the fact that at each step, the cheapest edge connecting the growing tree to the rest of the graph must be part of some minimum spanning tree. While the main loop of Prim's algorithm is inherently sequential, the inner loop that selects the minimum-weight edge can be parallelized by distributing vertices and edges across multiple processors, though more efficient distributed algorithms exist for the minimum spanning tree problem.
Reader's Guide
Prim's algorithm, also known as Jarník's algorithm, the Prim–Jarník algorithm, the Prim–Dijkstra algorithm, or the DJP algorithm, was originally developed in 1930 by Czech mathematician Vojtěch Jarník and later independently rediscovered by Joseph Kruskal, Robert C. Prim, and Edsger W. Dijkstra in the 1950s. It operates as a greedy algorithm, building a minimum spanning tree one vertex at a time from an arbitrary starting vertex, at each step adding the cheapest possible connection from the current tree to a vertex outside it. This process ensures that the tree includes every vertex while minimizing the total weight of its edges. The algorithm is designed for connected, weighted undirected graphs; to handle disconnected graphs and find a minimum spanning forest, it can be run separately for each connected component. In terms of asymptotic time complexity, Prim's algorithm, Kruskal's algorithm, and Borůvka's algorithm are equally fast for sparse graphs, though more sophisticated algorithms can outperform them. For sufficiently dense graphs, Prim's algorithm can achieve linear time, particularly when implemented with a d-ary heap rather than a Fibonacci heap. The main loop of Prim's algorithm is inherently sequential and cannot be parallelized, but the inner loop—which selects the next minimum-weight edge—can be parallelized by distributing vertices and edges across processors. This parallel variant has been explored for both distributed and shared memory machines, though more efficient algorithms exist for the distributed minimum spanning tree problem. The algorithm's correctness is proven by showing that each edge added during its construction belongs to some minimum spanning tree, and that the final output is a tree because every added edge connects a vertex inside the growing subgraph to one outside it.
Did You Know?
- Using a Fibonacci heap, Prim's algorithm runs in O(|E| + |V| log |V|) time.
- The main loop of Prim's algorithm is inherently sequential and thus not parallelizable.
Frequently Asked Questions
Who is Prim's algorithm?
Prim's algorithm is a greedy strategy from computer science, best known for carving a minimum spanning tree out of a weighted undirected graph. Think of it as the character who takes a tangled web of edges and distills it down to the cheapest possible skeleton that still connects every vertex.
What are Prim's algorithm's powers and role?
Its core ability is to grow a spanning tree one vertex at a time, always selecting the single cheapest edge that links the current tree to an outside vertex. It never looks ahead or backtracks—pure greedy selection drives every single decision.
How does Prim's algorithm's story begin and end?
The story kicks off from any arbitrary starting vertex you choose, and it wraps up the moment every vertex in the graph has been absorbed into the growing tree. At that point the resulting structure is guaranteed to be a minimum spanning tree, and the algorithm halts.
Why is Prim's algorithm important to fans of complexity theory?
It gives practitioners a straightforward, provably optimal way to solve the minimum-spanning-tree problem without resorting to brute-force enumeration. Its greedy nature makes it a go-to teaching example for how consistently local choices can still yield a globally optimal structure.
What's the deal between Prim's algorithm and Kruskal's algorithm?
Both solve the same minimum-spanning-tree problem, but Prim's grows a single connected tree outward from one seed vertex while Kruskal's sorts all edges globally and merges separate components. Prim's tends to shine on dense graphs where adjacency-list lookups keep each per-step choice cheap.
More in Complexity Theory 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record