Analysis of Algorithms : An Active Learning Approach

174 GRAPH ALGORITHMS

FindRoot( s )

s the element whose partition root we want

result = s

while Parent[result] > 0 do

result = Parent[result]

end while

return result

TheFindRoot routine begins at Parent[s], which has the location of

the parent of the element s. If this value is negative, it means that s is the root

of a partition, so the result of s is returned. If, however, s is not a root, we

update result to be the parent of s and check to see if that is the root of the

partition. We continue to work our way up this partition until we reach the

root. An efficiency improvement not included here would then follow this

path again and update all of the entries along it to point to the root directly.

This process takes a little more time, but future attempts to find the root for

those updated elements will be done faster.

6.8 Programming Exercises

For these problems, you will be generating complete weighted graphs with N

nodes. This is easiest using an adjacency matrix because you just need to fill

every entry, except for those along the diagonal, which should be zero. You

will work with undirected graphs, so you need to make sure that AdjMat[i,j]

has the same value as AdjMat[j,i].

These problems ask you to compare two spanning trees or paths. This will

be easier if you make sure that the edges involved are listed with the smaller

label first, which is possible because these problems work with undirected

graphs. Then you can sort the edges based on their nodes. If two minimum

spanning trees or paths are the same, their two sorted lists should match exactly.

1. Generate a complete weighted undirected graph with 50 nodes. Run the
   Dijkstra–Prim minimum spanning tree algorithm starting at each of the
   nodes, and determine how many different minimum spanning trees are
   found. Do this process four times with a maximum random edge weight of
   10, 25, 50, and 100. Write a report of your results with an explanation of