Algorithms in a Nutshell

Minimum Spanning Tree Algorithms

Given an undirected, connected graph G=(V, E), one might be concerned with finding a subset ST of edges from E that "span" the graph by ensuring that the graph remains connected. If we further require that the total weights of the edges in ST are minimized, then we are interested in finding a minimum spanning tree (MST).

Prim's Algorithm, illustrated in Figure 6-19, shows how to construct an MST from such a graph by using a greedy approach in which each step of the algorithm makes forward progress toward a solution without reversing earlier decisions. Prim's Algorithm grows a spanning tree T one edge at a time until an MST results (and the resulting spanning tree is provably minimum). It randomly selects a start vertex s∈V to belong to a growing set S, and it ensures that T forms a tree of edges rooted at s. Prim's Algorithm is greedy in that it incrementally adds edges to T until an MST is computed. The intuition behind the algorithm is that the edge (u, v) with lowest weight between u∈S and v∈V-S must belong to the MST. When such an edge (u, v) with lowest weight is found, it is added to T and the vertex v is added to S.

The algorithm uses a priority queue to store the vertices v∈V-S with an associated priority equal to the lowest weight of some edge (u, v) where u∈S. This carefully designed approach ensures the efficiency of the resulting implementation.

Solution

The C++ solution shown in Example 6-9 relies on a binary heap to provide the implementation ...