In my algorithm class, I\'m studying disjoint set structures, trying to find two

Question

In my algorithm class, I'm studying disjoint set structures, trying to find two operations, find() and union().

My notes says the following:

Use an integer array of size N

The label of a set is the smallest number in the set, set[x] is the label of x, i.e., x is in set[x]

Initially, set[x]=x

There are two operations, find(x) and union(a,b). Find(x) is supposed to return the label of the set that contains object x.

find1(x)

return set[x] (return set label)

Union(a,b) is supposed to union two sets labeled a and b

What I don't get is the algorithm for union1(a,b). I understand some lines of the algorithm but not others? Could you help me fill in the gaps? It is as follows:

union1(a,b)

i=min(a,b) //so i is supposed to be smaller than a or b

j=max(a,b) // j is supposed to be bigger than a or b

for(k=0;k<N;k++) //what is k?? I think it is a tracker or index to traverse array to find if an element is in a certain set or not? Is that correct? I think N is the number of elements bit what are the elements in? Is N elements in the array after merge 2 sets?

if (set[k]==j) //what is this line doing?

set[k]=i // what is this line do?

I have an example that explains union() operation, it is as follows:

3 sets: {0,4},{1,3,6,9},and {2,5,7,8}

0 1 2 3 4 5 6 7 8 9

set[]=[0 | 1 | 2 | 1 | 0 | 2 | 1 | 2 | 2 | 1]

after union1(2,0)

2 sets: {0,2,4,5,7,8} and {1,3,6,9}

0 1 2 3 4 5 6 7 8 9

set[]=[0 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1]

Explanation / Answer

The idea to find the union of two sets is that - create a third set with elements that are not repeated. So, what we need to do here is

create a new empty set or array,

pull one element from smaller of the two arrays,

check if it exists in the bigger array(the other one)

if it exists - don't add to new array else add

do this for all elements of smaller array

finally add all elements of larger array

In the i = min(a,b), we find which is the smaller array's length and larger arrays's length and loop over the array to add them to the unified array

set[]=[0 | 1 | 2 | 1 | 0 | 2 | 1 | 2 | 2 | 1] this is the final array after union of all three arrays, only the 0s,1s and 2s point to the set which it came from. So, the first element came from 0th set, second element came from 1st set, fourth element came from 0th set and so on and so forth.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.