不相交集合
等价关系
- 自反性
- 对称性
- 传递性
基本数据结构
基本思路
实现
类型声明
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) ;
初始化
void Intialize(DisjSet S)
{
int i ;
for(i = NumSets; i > 0;i--)
S[i] = 0 ;
}
Union操作
void Union(DisjSet S,SetType Root1,SetType Root2)
{
S[Root2] = Root1 ;
}
Find操作
SetType Find(ElementType X, DisjSet S)
{
if(S[X] <= 0)
return X ;
else
return Find(S[X],S) ;
}
更好的Find操作
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 ;
}
}
路径压缩
改进的Find函数
SetType Find(ElementType X,DisjSet S)
{
if(S[X] <= 0)
return X ;
else
return S[X] = Find(S[X],S) ;
}