Algorithms in a Nutshell

Minimum Spanning Tree Algorithms | 169

Graph

Algorithms

Minimum Spanning Tree Algorithms

Given an undirected, connected graphG=(V,E), one might be concerned with

finding a subset ST of edges fromEthat “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’SALGORITHM, 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 algo-

rithm makes forward progress toward a solution without reversing earlier

decisions. PRIM’SALGORITHMgrows a spanning treeTone edge at a time until

an MST results (and the resulting spanning tree is provably minimum). It

randomly selects a start vertexs∈Vto belong to a growing setS, and it ensures

thatTforms a tree of edges rooted ats.PRIM’SALGORITHMis greedy in that it

incrementally adds edges toTuntil an MST is computed. The intuition behind

the algorithm is that the edge (u,v) with lowest weight betweenu∈Sandv∈V–S

must belong to the MST. When such an edge (u,v) with lowest weight is found, it

is added toT and the vertexv is added toS.

The algorithm uses a priority queue to store the vertices v∈V–Swith an associ-

ated priority equal to the lowest weight of some edge (u,v) whereu∈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 of the priority queue that is central to PRIM’SALGORITHM. Ordi-

narily, using a binary heap would be inefficient because of the check in the main

loop for whether a particular vertex is a member of the priority queue (an opera-

tion not supported by binary heaps). However, the algorithm ensures that vertices

are only removed from the priority queue as it processes, so we need only main-

tain a status arrayinQueue[]that is updated whenever a vertex is extracted from

the priority queue. In another implementation optimization, we maintain an

external arraykey[]that records the current priority key for each vertex in the

queue, which again eliminates the need to search the priority queue for a given

vertex identifier.

Example 6-9. Prim’s Algorithm implementation with binary heap

/**

* Given undirected graph, compute MST starting from a randomly

* selected vertex. Encoding of MST is done using 'pred' entries.

*/

void mst_prim (Graph const &graph, vector<int> &pred) {

// initialize pred[] and key[] arrays. Start with arbitrary

// vertex s=0. Priority Queue PQ contains all v in G.

const int n = graph.numVertices( );

pred.assign(n, -1);

vector<int> key(n, numeric_limits<int>::max( ));

key[0] = 0;

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use