Analysis of Algorithms : An Active Learning Approach

158 GRAPH ALGORITHMS

The addition of node C and edge AC to the spanning tree (Fig. 6.5(e)) did

not cause any edges to be updated. We next choose the edge AF, so it and the

node F are added to the tree. We also update the links because the edge FD has

a smaller weight than BD and edge FG has a smaller weight than EG. In the

resulting fringe (Fig. 6.5(f )), we see that the edge FD is now the remaining

edge with the smallest weight, so it is added next.

We now just have one node that has not been added to the tree (Fig. 6.5(g)).

When it is added, the process is complete, and we have determined the MST

rooted at node A (Fig. 6.5(h)).

5

6

7

A

B D

G

F

E

C 1

6

B

G

D

E

F

C A

■FIGURE 6.5E

Node C added to the

tree

■FIGURE 6.5F

Node F added to the tree and

edges to nodes D and G are

updated

6

B

G

E

D F

C A

B

E

A

D

C^456 F G

21

3

■FIGURE 6.5G

Only one node is left in the

fringe

■FIGURE 6.5H

The complete minimum spanning

tree rooted at node A