1. 集合的表示
集合运算:交、并、补、差，判定一个元素是否属于某一集合
并查集:集合并、查某元素属于什么集合
-
并查集问题中集合存储如何实现?
可以用树结构表示集合，树的每个结点代表一个集合元素
-
采用静态链表存储
typedef int ElementType;
typedef struct {
ElementType data;
int parent;
}SetType;
2. 集合运算
(1) 查找某个元素所在的集合（用根结点表示）
#define MaxSize 10
int Find(SetType S[], ElementType X)
{
int i;
for (i = 0; i < MaxSize && S[i].data != X; i++) ;
if(i >= MaxSize) return -1;
for (; S[i].parent >= 0; i = S[i].parent) ;
return i;
}
(2) 集合的并运算
- 分别找到X1和X2两个元素所在集合树的根结点。
- 如果他们不同根，则将其中一个根结点的父结点指针设置成另一个根结点的数组下标。
void Union(SetType S[], ElementType X1, ElementType X2)
{
int root1, root2;
root1 = Find(S, X1);
root2 = Find(S, X2);
if (root1 != root2) {
S[root2].parent = root1;
}
}
3. 集合的简化表示
- 元素值和数组下标一一对应，数组内存放父结点索引。
typedef int ElementType;
typedef int SetName; /*默认用根结点的下标作为集合名称*/
typedef ElementType SetType[];
SetName Find(SetType S, ElementType X)
{
for (; S[X]>=0; X=S[X]);
return X;
}
void Union(SetType S, SetName root1, SetName root2)
{
S[root2] = root1;
}
案例
有5个电脑，输入C表示检查两个电脑是否连通，输入I表示连接两个电脑，输入S表示结束并输出有几个连通网络。
void Input_connection(SetType S)
{
ElementType u, v;
SetName root1, root2;
cin >> u >> v;
root1 = Find(S, u-1);
root2 = Find(S, v-1);
if (root1 != root2) {
Union(S, root1, root2);
}
}
void Check_connection(SetType S)
{
ElementType u, v;
SetName root1, root2;
cin >> u >> v;
root1 = Find(S, u-1);
root2 = Find(S, v-1);
if (root1 == root2) {
cout<<"yes"<<endl;
}else{
cout<<"no"<<endl;
}
}
void Check_network(SetType S, int n)
{
int i, count = 0;
for (i = 0; i < n; i++) {
if (S[i] < 0) {
count++;
}
}
if (count == 1) {
cout<<"The network is connected."<<endl;
}else{
cout<<"There are "<<count<< " components."<<endl;
}
}
int main(int argc, const char * argv[]) {
// insert code here...
SetType s = {-1, -1, -1, -1, -1};
char in;
do{
cout<<"请输入标识："<<endl;
cin>>in;
switch (in) {
case 'I':
Input_connection(s);
break;
case 'C':
Check_connection(s);
break;
case 'S':
Check_network(s, 5);
break;
default:
break;
}
}while(in != 'S');
return 0;
}
4. 按秩归并
- 前提是没有简化前的集合
- 因为我们用根结点表示集合，每次将root2 挂载到 root1上 因此树越来越高。每次查找Find(1)的根结点时需要T=O(n), 因此进行n次Union的时候时间复杂度为T = O(n2)
为什么树会越来越高？
- 将较高的树贴到较低的树上，会使树变高一层。
- 应该将较低树贴到高树上！
树高应该存在哪里呢？
可以将树根的值改成负的树高
S[Root] = -树高;
if (S[Root2] < S[Root1]) {
S[Root1] = Root2;
}else{
if (S[Root1] == S[Root2]) S[Root1]--;
S[Root2] = Root1;
}
另一种做法：比规模
把小树贴到大树上 S[Root] = -元素个数;
if (S[Root2] < S[Root1]) {
S[Root2] += S[Root1];
S[Root1] = Root2;
}else{
S[Root1] += S[Root2];
S[Root2] = Root1;
}
5. 路径压缩
路径压缩
SetName compressionPath(SetType S, ElementType X)
{
if (S[X] < 0) {
return X;
}else{
return S[X] = compressionPath(S, S[X]);
}
}
