考研408数据结构复习指南：深入理解并查集详解

这是我参与11月更文挑战的第8天，活动详情查看：2021最后一次更文挑战

考研倒计时：47天

参考资料： 王道数据结构考研

并查集是2022年408新增考点

本篇简要总结并查集的代码实现以及应用. 考纲要求到应用层面，所以代码需要会实现！

逻辑结构

元素之间为集合关系，主要有查操作和并操作，存储结构可以采用双亲表示法。 [图片来源网络]

代码实现

初始化

#define SIZE 13
int UFSets[SIZE];  //集合元素数组

//初始化并查集
void Initial(int S[]){
    for(int i=0;i<SIZE;i++){
        S[i] = -1;
    }
}

”查“操作，返回x所属的根结点。

最坏时间复杂度为O（n）

int Find(int S[],int x){//找x所属的集合
    while(S[x]>0){
        x=S[x];         //循环寻址x的根
    }
    return x;           //根的s[]小于0,返回根结点的编号
}

”并“操作

时间复杂度为O（1）

void Union(int S[],int Root1,int Root2){
    if(Root1 != Root2){//要求Root1和Root2是不同的集合
        S[Root2] = Root1;  //将根Root2连接到另一根Root1的下面
    }
}

优化思路：每次合并的操作让树尽量不长太高。

• 用根结点的绝对值表示树的结点总数
• 让小树合并到大树

优化后的”并“操作

void Union(int S[],int Root1,int Root2){
    if(Root1 == Root2) return;
    if(S[Root2]>S[Root1]){   //Root2的结点数更少
        S[Root1] += S[Root2];  //累加结点个数
        S[Root2] = Root1;      //小树合并到大树
    }esle{
        S[Root2] += S[Root1];  //累加结点个数
        S[Root1] = Root2;      //小树合并到大树
    }
}

该方法构造的树高不超过log2n向下取整+1

所以优化后，Find操作最坏时间复杂度：O（log2n）

应用

判断图的连通分量数

遍历无向图的邻接矩阵的上三角区域，利用并查集进行合并，连通分量会被化为一个集合。

最后遍历并查集，有多少个小于0的值即为连通分量的个数。

int ComponentCount(int g[5][5]){
    //g[5][5]二维数组表示的邻接矩阵
    int S[5];
    for(int i=0;i<5;i++) S[i]=-1;//初始化并查集
    for(int i=0;i<5;i++){//遍历各条边，无向图遍历上三角型。
        for(int j=i+1;j<5;j++){
            if(g[i][j]>0){//结点i、j有边
                int iRoot = Find(S,i);
                int jRoot = Find(S,j);
                if(iRoot != jRoot){ //i，j并入同一集合
                    Union(S,iRoot,jRoot);
                }
            }
        }
    }
    //统计有几个连通分量
    int count=0;
    for(int i=0;i<5;i++){
        if(S[i]<0){
            count++;
        }
    }
    return count;
}

判断图是否有环

已经连通的子图中，但凡再多出来一条边，这个子图就一定有环。

代码在上面的基础上加一条判断即可。

             if(iRoot != jRoot){ //i，j并入同一集合
                    Union(S,iRoot,jRoot);
                }
             else{//!!!i，j原本在同一个集合
                 return 1;//在一个连通子图中，再多一条边，必有环。
             }
                

实现Kruskal算法

各条边按权值递增排序，依次处理各条边。

通过Find操作确定一条边所连接的两个顶点是否属于同一个集合，如果不属于同一个集合，则将这条边加入生成树，并将两个点所属集合Union。

补充并查集优化--压缩路径

Find操作:先找到根结点，再将查找路径上所有结点都挂载到根结点上，下一次再查该节点只需要O（1），可以使树高不超过a(n)增长很慢的函数。

比如下图（来源网络）就是一种压缩路径的表现

int Find(int S[],int x){
    int root = x;
    while(S[root]>=0)  root=S[root];//循环找到根
    while(x!=root){  //压缩路径
        int t=S[x];  //t指向x的父节点
        S[x] = root; //x直接挂载到根结点
        x=t;
    }
    return root;       //返回根结点的编号
}

最后总结如下：

---

部分内容待补充完善~

如有误，请多指正！