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 uMST and vMST
add v and the least-cost edge (u, v) to the MST such that uMST and vMST
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

12 thoughts on “Prim’s Minimum Spanning Tree Algorithm

  1. Pingback: Dijkstra’s single source shortest path algorithm | Everything Under The Sun

  2. Pingback: Indexed Min-Priority Queue C++ implementation | Everything Under The Sun

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s