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
Cleveland
S412 Chicag
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 effective 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.