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