 # Prim’s Minimum Spanning Tree Algorithm

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:

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.

## 12 thoughts on “Prim’s Minimum Spanning Tree Algorithm”

1. fdk says:

Have the same problem as Kruskal in here too..help to rectify it.

• kartik kukreja says:

The solution is also the same. The problem gives vertices in 1-based representation. Subtract off 1 from u and v after line 116.

2. fdk says:

Is this the eager or lazy version of prim’s algorithm ?

• kartik kukreja says:

It is eager implementation. You can read about the differences between eager and lazy versions here: http://algs4.cs.princeton.edu/43mst/

3. fdk says:

So can we modify it to be lazy version too ?

4. competitivecoder says:

Hello bhaiya…Can you please write some comment in your Git of prim’s lazy implementation.My humble request 🙂

• kartik kukreja says:

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

5. competitivecoder says:

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 🙂

• kartik kukreja says:

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.