The problem is to find the minimum weight spanning tree (i.e., a connected acyclic subgraph) of an undirected weighted graph. Earlier, I described the Kruskal’s algorithm to find the MST in time O(E log V). Prim’s algorithm is another greedy algorithm that finds an MST in time O(E log V). The difference is that the Prim’s algorithm grows an MST, starting from a single vertex, always adding the least-cost edge from a tree vertex to a non-tree vertex to the current set of edges in the MST.
The algorithm can be described as follows:
Let the MST contain a single vertex v, where v is any arbitrary vertex of the graph | |
while it is possible to add an edge (u, v) to the MST such that u ∈ MST and v ∉ MST | |
add v and the least-cost edge (u, v) to the MST such that u ∈ MST and v ∉ MST | |
return MST |
An efficient implementation of Prim’s algorithm requires the use of indexed min-priority queue. For each vertex, the priority queue stores the least-cost edge weight to that vertex from some tree vertex. At each iteration, we choose the minimum weight vertex (or equivalently, the least-cost edge from a tree vertex to a non-tree vertex), add it to the MST, pop it off the priority queue and potentially find lower cost edges from this vertex to some non-tree vertices (thereby decreasing their weights).
Running time analysis: Each edge is processed exactly once and may potentially cause a decrease in the weight of some non-tree vertex. Decreasing the weight takes O(log V) time. So the overall running time of the algorithm is O(E log V).
Take a look at the C++ implementation.
Try your hand at problem MST, which uses this idea.
Reference: Algorithms 4th Edition by Robert Sedgewick and Kevin Wayne
Pingback: Dijkstra’s single source shortest path algorithm | Everything Under The Sun
Pingback: Indexed Min-Priority Queue C++ implementation | Everything Under The Sun
Have the same problem as Kruskal in here too..help to rectify it.
The solution is also the same. The problem gives vertices in 1-based representation. Subtract off 1 from u and v after line 116.
Is this the eager or lazy version of prim’s algorithm ?
It is eager implementation. You can read about the differences between eager and lazy versions here: http://algs4.cs.princeton.edu/43mst/
So can we modify it to be lazy version too ?
You no longer need to use Indexed priority queue but can use standard priority queue that comes with your language of choice. A sample solution in C++: https://github.com/kartikkukreja/blog-codes/blob/master/src/Lazy%20Prim's%20MST%20algorithm.cpp
It gets accepted for http://spoj.com/problems/MST
Hello bhaiya…Can you please write some comment in your Git of prim’s lazy implementation.My humble request 🙂
There isn’t much difference between the lazy and the eager versions of Prim’s algorithm. The lazy version leaves edges connecting a newly added vertex to the tree, on the priority queue, deferring the ineligibility tests to when we remove them. For the lazy version, we don’t need an indexed priority queue and can use the standard priority queue.
Here’s a C++ implementation: https://github.com/kartikkukreja/blog-codes/blob/master/src/Lazy%20Prim's%20MST%20algorithm.cpp
And one more thing bhaiya…The Lazy implementation seem much similar to dijktra’s just a difference of calculating the cost.Am i correct or I have overlooked something 🙂
Both versions are pretty much the same as Dijkstra’s. Dijkstra’s algorithm can also be implemented in both lazy or eager fashion. Yes, the only difference between Prim’s and Dijkstra’s is what is used to order nodes on the priority queue. Prim’s uses immediate edge cost to a node from a tree node while Dijkstra’s uses the total path cost from the source node.