Analysis of Algorithms : An Active Learning Approach

156 GRAPH ALGORITHMS

category. We loop through the process of picking the smallest weighted edge

connecting a tree node with a fringe node, adding the new node to the tree,

and then updating the nodes in the fringe category. When all the nodes have

been added to the tree, we are done.

Our general algorithm for this process is as follows

select a starting node
build the initial fringe from nodes connected to the starting node
while there are nodes left do
choose the edge to the fringe of the smallest weight
add the associated node to the tree
update the fringe by:
adding nodes to the fringe connected to the new node
updating the edges to the fringe so that they are the smallest
end while

Figure 6.5 gives an example of this algorithm in operation. We have arbi-

trarily chosen node A to begin the process. As we said, a different choice for

the starting node will not change the result, unless there is more than one

MST.

The original graph is shown in Fig. 6.5(a), and as was mentioned, we

choose to start the construction of the MST at node A. All of the nodes

directly connected to node A become the starting fringe set. We see that the

A B

F G

C D E

(^47)
7
6
2
6
6
6
1
58
3
F
D
C
B
A
2
4
7
5
■FIGURE 6.5A
The original graph
■FIGURE 6.5B
First node added. (Dashed
lines show edges to fringe
nodes.)