Prim's algorithm
Greedy algorithm for minimum spanning trees.
Prim's algorithm is a greedy algorithm in computer science that finds a minimum spanning tree for a weighted undirected graph. It builds a tree one vertex at a time from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.
- field
- Computer science
- known_for
- Prim's algorithm (minimum spanning tree)
- type
- Algorithm
Lore & Background
It is also sometimes called Jarník's algorithm, the Prim–Jarník algorithm, the Prim–Dijkstra algorithm, or the DJP algorithm. Other well-known algorithms for this problem include Kruskal's algorithm and Borůvka's algorithm.
Reader's Guide
Prim's algorithm finds a minimum spanning tree for a connected, weighted undirected graph by iteratively adding the cheapest edge connecting the current tree to a vertex outside it. Its time complexity depends on data structures: O(|V|^2) with simple arrays, O(|E| log |V|) with a binary heap, and O(|E| + |V| log |V|) with a Fibonacci heap. For sufficiently dense graphs, it can run in linear time. The algorithm is inherently sequential in its main loop, but the inner loop can be parallelized. Its correctness is proven by showing that any edge added is part of some minimum spanning tree.
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