Discrete Mathematics for Computer Science

Spanning Trees 377

Kruskal's algorithm to find a spanning tree can be viewed as the special case of

finding an MCST in a graph with each edge having weight one. The modifications

needed to find an MCST where the edges have arbitrary weights are included in the next

algorithm.

INPUT: Connected graph G = (V, E) with weighted edges

OUTPUT:- A minimum cost spanning tree T of G

V(T) = V(G) /* Initialize */

E(T) = 0

Sort E(G) in order of increasing weight

for each e e E(G) in increasing order of edge weights do

if (e U E(T) is acyclic) then

E(T) = E(T) U {e)

Figure 6.37 shows MCST in the graph from Figure 6.36.

Boston

Minneapolis S412 Chicag Cleveland 437 NN216

-^341 ll109
Philadelphia

San Francisco Kansas City^252 St. Louis Richmond

SI /529

16 4951

Atlanta

Dallas

Figure 6.37 Minimum cost spanning tree.

Several approaches are used to determine which edge to examine next. One method is

to sort the edges of the graph in increasing order by weight and then examine the edges in

that order. A second approach involves repeating a process whereby only the next edge to

be examined is identified rather than preprocessing all the edges by sorting them. An ef-

fective data structure for this second possibility is explored in Exercise 26 of Section 6.13.

No matter what procedure is used to determine which edge to examine next, however, the

procedure can be stopped as soon as number of edges chosen is one less than the number

of vertices in the graph.