并查集

1. 适用范围:

1. 用于判断两个非交子集是否属于同一个集合
2. 判断图中是否存在回路(环)

优点

1. 并查集合并多个集合的元素非常快

2. 梗概:

• 并查集即使用哈希表存储森林结构
  • 用哈希表(数组也是一种哈希表)的原因: 这样不用遍历树就能找到元素

常见结构

1. 并查集一般不保存数据
2. 用结点位置（如数组索引）表示结点
3. 结点只存储所属父节点的位置信息
4. 如果没有父节点，则存一个无效位置（如数组索引通常是-1）

集合含义

• 一棵树被视为一个集合
• 一个集合用一个元素作为这个集合的代表
• 一颗树以根节点作为这颗树的代表

3. 操作:

1. 初始化
   1. 参数: 并查集地址
   2. 操作结果: 把所有结点作为互相独立的子集
2. 查找根结点
   1. 参数: 一个子集
   2. 操作结果: 返回该子集的根结点
3. 合并两子集
   1. 参数: 任意两个子集
   2. 操作结果: 如果两子集同属一个集合, 则返回失败(1), 否则把两个子集并入一个集合, 并返回空
4. 合并两子集并压缩
   1. 参数: 任意两个子集, 集合高度数组
   2. 操作结果: 如果两子集同属一个集合, 则返回失败(1), 否则尽量保持高度不变, 把两个子集并入一个集合, 并返回空

4. 性质:

1. 两子集合并高度变化规律:
   1. 短子集的根指向长子集的根, 合并后集合高度=长子集的高度
   2. 两个高度相等的子集, 一个根指向另一个根, 合并后集合高度 = 子集高度+1

5. 在c语言中的实现

5.1. 定义:

#define MFSetSize 8
int parent[MFSetSize]

5.2. 初始化

void InitialMFSet(int parent[]){
    int i;
    for(i=0;i<MFSetSize;i++){
        /*-1表示根结点*/
        parent[i]=-1;
    }
}

5.3. 找根

int Find(int x, int parent[]){
    int x_root = x;
    for(;parent[x_root]!=-1;){
        x_root = parent[x_root];
    }
    //parent[x]=x_root;压缩路径的话就加上
    return x_root;
}

5.4. 普通合并子集

int Union(int x, int y, int parent[]){
    int x_root = Find(x, parent);
    int y_root = Find(y, parent);
    if (x_root == y_root)return 0;
    parent[x_root]=y_root;
    return 1;
}

5.5. 压缩合并子集

梗概:

1. 利用性质: 两子集合并高度变化规律 代码:

int Union_compact(int x, int y, int parent[], int rank[]){
//rank[]下标表示根结点,值表示层数
    int x_root = Find(x, parent);
    int y_root = Find(y, parent);
    if (x_root == y_root)return 0;
    if (rank[y_root]<rank[x_root])
        parent[y_root]=x_root;
    else if(rank[x_root]<rank[y_root])
        parent[x_root]=y_root;
    /*只要不是短接长,就变高*/
    else{
        parent[x_root]=y_root;
        rank[y_root]++;
    return 1;
    }
}