Prim's Algorithm builds a Minimum Spanning Tree (MST) by starting with a single node and "growing" the tree outward. At every step, it finds the cheapest edge that connects a node inside the growing tree to a node outside of it. This greedy approach continues until all nodes are part of the tree, ensuring the total weight of all edges is as low as possible. It is perfect for problems like designing cost-effective road, fiber-optic, or electrical utility networks.
MST = empty set
mark src as visited
while MST does not span all vertices:
(u, v) = cheapest edge where
u ∈ visited and v ∉ visited
add edge (u, v) to MST
mark v as visited
(5 credits)
See what happens with your input
Get a short, step-by-step explanation of this visualization. Turn on AI Summary, then start a fresh run with your input.
Prim's algorithm maintains two disjoint sets of vertices: those already included in the growing Minimum Spanning Tree, and those not yet added. Starting from a chosen root vertex, the algorithm continually examines all edges spanning the boundary between the tree and the remaining vertices. The minimum-weight edge crossing this cut is guaranteed to belong to the MST.
In practical implementations, a priority queue tracks the minimum known distance from the MST to each outside vertex. Whenever a new vertex is absorbed into the tree, the distances to its adjacent unvisited neighbors are updated via decrease-key operations.
Prim's algorithm is particularly effective for dense graphs where the number of edges E approaches V². While a standard binary heap yields O(E log V) runtime, implementing Prim's with a Fibonacci heap reduces the amortized cost of decrease-key operations to strictly O(1). This brings Prim's overall runtime down to O(E + V log V), which is asymptotically optimal and significantly outperforms Kruskal's algorithm on dense networks.
Metric / Operation | Complexity | Description |
|---|---|---|
| With Binary Heap | O(E log V) | Extract-min and decrease-key operations on a binary heap take O(log V) across all edges and vertices. |
| With Fibonacci Heap | O(E + V log V) | Fibonacci heap achieves O(1) amortized decrease-key operations, making Prim’s asymptotically optimal for dense graphs. |
| Adjacency Matrix | O(V²) | Simple linear array scan for minimum edge; optimal for extremely dense graphs where E ≈ V². |
| Space Complexity | O(V + E) | Stores graph adjacency structure and priority queue entries for all vertices. |
The Cut Property: For any cut (partition of vertices into two sets S and V - S), the minimum weight edge crossing the cut must belong to the Minimum Spanning Tree (MST). Prim's iteratively grows a single tree set S by adding the lightest crossing edge.
Binary Min-Heap implementation yields O((V + E) log V). A Fibonacci Heap optimizes decreaseKey operations to amortized O(1), improving overall time complexity to O(E + V log V), which is superior for dense graphs where E ≈ V².
Prim's algorithm works correctly with negative edge weights. However, if the graph is disconnected, Prim's will only build an MST for the connected component containing the starting node. To span all components, Prim's must be launched on each unvisited component (Minimum Spanning Forest).
Designing physical fiber-optic cables, electrical power grids, water supply pipe connections, and telecommunication layout networks to minimize physical infrastructure construction costs.
to join the discussion
Hand-picked resources to deepen your understanding
© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0