Analysis of Algorithms : An Active Learning Approach

172 GRAPH ALGORITHMS

6.7 Partitioning Sets

A number of algorithms need to maintain a set of values as a collection of dis-

joint sets, with the ability to combine them. The inherent set capability of

modern programming languages could be used, but there is nothing in their

implementation that guarantees that disjoint sets will occur. Additionally, not

all programming languages have set capabilities. This section will look at a

method for implementing this set partitioning using arrays. We have seen a use

for this capability in our algorithm for Kruskal’s minimum spanning tree algo-

rithm.

We begin with an array called Parent, which has one location for each

element of the set we are working with. We initialize all of the elements to 
1,

which represents that each is the root of a partition (the negative) and that the

partition has one element in it (the 1). As things progress, if some element is

the root of a partition with seven elements, its value in the array Parent will

be
7. As elements are added to a partition, their value in the array Parent

will be set to the root of the partition they are added to. For example, if ele-

ment 5 is added to the partition rooted by element 8, the fifth location of

Parent will have 8 stored in it, and the eight location will have its negative

value “increased” to indicate that there is one more value in the partition. The

elements of the Parent array will only have their immediate parent in the

partition as their value, because when two partitions are combined, only the

root entries of the array will be changed.

Consider the partitioning in Fig. 6.11. We see that there are three partitions

with roots of 5, 6, and 11. These array locations have negative values indicating

the number of elements in those partitions. Each of the other locations has the

value of the immediate parent. If we now joined together the partitions rooted

at 6 and 11, we would change Parent[11] to have the value 6, its new root,

and we would change Parent[6] to be 
5, representing the fact that this

partition has five elements.

The algorithms to accomplish this partition structure follow.

InitializePartition( N )

N the number of elements in the set

For i = 1 to N do

Parent[i] = -1

end do