C++并查集算法简单详解

1、并查集的初始化

并查集是用一个数组实现的。首先先定义一个数组：

int father[N];

father[i]表示元素i的父亲结点。

接下来进行初始化。一开始，每个元素都分别是独立的一个集合，父亲结点就是它自己，所以初始化时将所有father[i]等于i：

for(int i = 1; i <= N; i++){
    father[i] = i;
}

这样，就将father数组初始化完毕。

2、并查集的查找操作

由于规定同一个集合中只存在一个根结点，因此查找操作，就是查找给定结点的根结点的过程。可以通过递推或递归来实现，思路都是一样的，都是反复寻找父亲结点，直到找到根结点为止。

递推代码：

//findFather函数返回元素x所在集合的根结点
int findFather(int x){
    while(x != father[x]){    //如果不是根结点，继续循环
        x = father[x];    //获得自己的父亲结点
    }
    return x;
}

上述代码中， while(x != father[x])，说明当x的父亲结点不等于本身时，也就是x不是根结点时就继续循环，因为父亲结点等于本身这个情况，只有在根结点才会出现。

递归代码：

int findFather(int x){
    if(x == father[x]) return x;    //如找到根结点，就返回根结点编号x
    else return findFather(father[x]); //否则，递归判断x的父亲结点是否是根结点
}

3、并查集的合并操作

合并，就是把两个集合合并成一个集合。实现过程是：先判断两个元素是否属于同一个集合，不属于同一个集合，就开始进行合并操作。判断两个元素是否属于同一个集合的具体思路，就是调用上面的findFather函数，分别查找两个元素所属集合的根结点，根结点不同，则两个元素不属于同一个集合。合并两个集合的具体思路，就是将其中一个集合的根结点的父亲指向另外一个集合的根结点即可。

合并操作的代码实现：(假设有两个集合，一个集合里有元素a，一个集合有元素b)

void Union(int a, int b){
    //让一个集合的根结点的父亲指向另一个集合的根结点
    father(findFather(a)) = findFather(b); 
}

注意，合并操作之前，最好先判断下待合并的两个元素是否位于同一个集合。

4、为什么要路径压缩？

5、实现路径压缩

由于findFather函数目的就是查找根结点，所以，我们在查找结点的路径上直接将所有结点的父亲都指向根结点，查找的时候就不必一直回溯去寻找父亲了，查询的复杂度可以降为O(1)。

比如下面这张图：

观察图不难发现，上图中father[1] = 1，father[2] = 1，father[3] = 2，father[4] = 3。经过路径压缩，就变成下面这幅图：

相当于将所有结点的父亲都直接指向根结点，这就是路径压缩。

如何用代码实现路径压缩呢？以下是具体代码：

int findFather(int x){
    if(father[x] != x) father[x] = findFather(father[x]);
    return father[x];
}

以上代码，实现了在查询获取根结点的同时，将路径进行压缩优化，代码虽然很短，但是很巧妙，下面解释下上述代码：

if(father[x] != x)，当所查找的元素x的父亲结点不是自己，也就是x不是根结点时，

findFather(father[x])，就继续递归查找父结点，直到找到根结点为止，

father[x] = findFather(father[x])，然后将找到的根结点直接赋给x的父亲结点。

这样就实现了路径压缩，即将结点的父亲直接指向根结点。

return father[x]，返回查找到的根结点。

频道导航