You are previewing Algorithms in a Nutshell.

Algorithms in a Nutshell

Cover of Algorithms in a Nutshell by George T. Heineman... Published by O'Reilly Media, Inc.
O'Reilly logo

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 sV 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 uS and vV-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 uS. 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 ...

The best content for your career. Discover unlimited learning on demand for around $1/day.