不相交集合

不相交集合

等价关系

满足三个性质

- 自反性
- 对称性
- 传递性

基本数据结构

基本思路

使用一个数组,下标表示该集合,内容表示指向的父亲

实现

类型声明

1
2
3
4
5
6
7
typedef int DisjSet[NumSets + 1] ;
typedef int SetType ;
typedef int ElementsType ;

void Intialize(DisjSet S) ;
void SetUnion(DisjSet S,SetType Root1,SetType Root2) ;
SetType Find(ElementType X,DisjSet S) ;

初始化

1
2
3
4
5
6
7
void Intialize(DisjSet S)
{
int i ;

for(i = NumSets; i > 0;i--)
S[i] = 0 ;
}

Union操作

不是最好的方法

1
2
3
4
void Union(DisjSet S,SetType Root1,SetType Root2)
{
S[Root2] = Root1 ;
}

Find操作

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

更好的Find操作

让根节点的数组内容为高度的相反数,也就是用负数表示

1
2
3
4
5
6
7
8
9
10
11
void SetUnion(DisjSet S,SetType Root1,SetType Root2)
{
if(S[Root2] < S[Root1]) //R2高
S[Root1] = Roo2 ;
else
{
if(S[Root1] == S[Root2])
S[Root1]-- ;
S[Root2] = Root1 ;
}
}

路径压缩

执行Union操作最终都会形成最坏情形的树

改进Find方法

改进的Find函数

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