# 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:

 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.

## 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.

• 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 ?

3. fdk says:

So can we modify it to be lazy version too ?

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

5. 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.