数据结构7 Disjoint Set_settype find ( elementtype x, disjset s ) { elemen

定义

如果K中元素k和M中元素m满足二元关系kRm，则说明K和M是同类集。

用一个数组记录所有元素的根。一个元素和它的根属于同一个集合。

根为0的元素本身为根，是最终的根。

修改的时候都是最终根的操作，因此可能会本来是最终根，但是被归并后就不是了。

操作

1.将Rt2归入到Rt1所属集合中

只需要把Rt2的根赋值为Rt1就行。

void  SetUnion ( DisjSet S, SetType Rt1,SetType Rt2 )
{
    S [ Rt2 ] = Rt1 ;     
}
1
2
3
4

2.查找元素X最终的根

需要找到X的根，但是X的根可能还有根，因此需要不断找到最终的根，即根为0的元素。

如果x的根不为0，则将x的根赋值为x，寻找x的根的根。

SetType  Find ( ElementType X, DisjSet S )
{   
	for ( ; S[X] > 0; X = S[X] )   ;
    return  X ;
}
1
2
3
4
5

3.给定关系，建立集合

比如给定9组等价关系，建立对应的集合。需要做的就是输入一组关系，看他们是否是同一个集合，若不是则归并。

有一个小改动是一开始全部赋值为自己的值。

因此最终的根是根等于自己的元素

Algorithm using union-find operations
{  
	Initialize  Si = { i }  for  i = 1, ..., 12 ;
   for  ( k = 1; k <= 9; k++ )  {  
   /* 此时输入等价关系iRj */
      if  ( Find( i ) != Find( j ) )
          SetUnion( Find( i ), Find( j ) );
   }
}
1
2
3
4
5
6
7
8
9

4.按大小归并

显然将小集合归并到大集合中，所需要改的根的个数较少。

将最终根的值变为-size即可解决。

Algorithm using union-find operations
{  
	Initialize  Si = 0  for  i = 1, ..., 12 ;
	for  ( k = 1; k <= 9; k++ )  {  
	/*   此时输入等价关系iRj  */
		if  ( abs(Find( i )) > abs(Find( j )) )
			SetUnion( Find( i ), Find( j ) );
      	else
      		SetUnion( Find( i ), Find( j ) );	
   }
}
1
2
3
4
5
6
7
8
9
10
11

5.路径压缩

寻找的时候每次都需要循环上去找最终根。

利用递归，找到最终根以后直接修改每一个根的最终根。

SetType  Find ( ElementType  X, DisjSet  S )
{
    if ( S[ X ] <= 0 )
        return  X;
    else    
    	return  S[ X ] = Find( S[ X ], S );
}
1
2
3
4
5
6
7

迭代

SetType  Find ( ElementType  X, DisjSet  S )
{   ElementType  root,  trail,  lead;
    for ( root = X; S[ root ] > 0; root = S[ root ] );  /* find the root */
    for ( trail = X; trail != root; trail = lead ) {
       lead = S[ trail ] ;   
       S[ trail ] = root ;   
    }  /* 重复再找一次，找的时候把每一层根的最终根都改掉 */
    return  root ;
}
1
2
3
4
5
6
7
8
9

题目

1.In Union/Find algorithm, if Unions are done by size, the depth of any node must be no more than N/2, but not O(logN).

每做一次归并，都会使得小的集合深度加1，但是总的深度还是看大的集合。只有深度相同的归并才能使得总的深度加1，2,2归并，深度变为3；3,3归并深度变为4。因此深度最大为${\log }_{2}N+1$

所以，N次归并和M次查找，复杂度为O($N+M{\log }_{2}N$)

2.The array representation of a disjoint set containing numbers 0 to 8 is given by { 1, -4, 1, 1, -3, 4, 4, 8, -2 }. Then to union the two sets which contain 6 and 8 (with union-by-size), the index of the resulting root and the value stored at the root are

正的数代表根，负的数代表最终根以及集合的元素个数。最后结果是{0，1，2，3}，{4，5，6}，{8，9}

3.The array representation of the disjoint sets is given by {2, –4, 2, 3, -3, 5, 6, 9, -2}. Keep in mind that the elements are numbered from 1 to 9. After invoking Union(Find(4), Find(6)) with union-by-size, which elements will be changed in the resulting array?
(4分)
A.a. elements of index 4 and 5
B.a. elements of index 2 and 5
C.a. elements of index 4 and 6
D.a. elements of index 2 and 6

改变的是小的集合的根和大的集合的根（size被改变），所以是4，6的根，即2，5