并查集相关知识点

并查集是这样的使用数据结构：它可以检测两个节点之间的连通状态。比如下图一个网络中有两堆节点，如何快速准确的判断某两个节点之间的连通性、或者改变某个节点的连通状态，这是并查集需要考虑的问题

归纳来说，一个并查集所涉及到的方法有下面两个：

（1）union(p, q) --> 合并两个集合（“并”）合并两个集合（“并”）

（2）find(p) --> 判断两个元素是否属于同一个集合

1 quick find方法

显而易见，我们可以创建一个status数组，status数组保存着每个节点的状态，如下表所示：

 0123456status0111222

节点0的状态数组时0，说明它自成一组；节点1,2,3的状态数组都是1，说明这三个节点自成一组；节点4,5,6的状态数组都是2说明这三个节点自成一组，是连通的。当两个节点的状态相同的时候（比如status[1]和status[3]相等），我们可以判定该两个节点是相连的，其时间复杂度是O(1)级别的；但是，当我们要合并两个节点的状态的时候，我们就需要遍历整个数组，将所有和p节点相同状态的节点都置为q节点的状态，其时间复杂度是O(n)级别的。可见此方法find的速度比较快，而union(p,q)的速度就比较慢了，该方法称之为quick find方法。

这时候就需要思考，有没有什么方法可以提高union函数速度的嘛？

2 quick union方法

要提高union方法的速度，我们首先要清楚上面quick find算法的union方法为什么会慢？假如我们要改变节点q的状态，难的不是找到节点q，不是改变节点q的状态，而是维护和节点q同一状态的其他节点的状态。在quick find中，我们通过遍历的方法将和节点q状态相同的节点的状态也进行相应的改变。这是quick find算法慢的原因——要进行遍历。因此，有没有什么方法，当改变节点q的状态的时候，能够快速将和它同一状态的其他节点的状态也相应的进行更新？

我们将同一状态的节点“堆起来”，从而构成一个树形结构，每个节点指向其父节点：

因此，我们可以使用一个parent数组保存每个节点所指向的父节点的索引，如下表格所示：

 0123456parent5222155

表中，parent[0]的值为5表示节点0的父节点是节点5，parent[2]值为2表示节点2的父节点就是节点2。因此，我们可以简单总结一下parent数组的规律

（1）parent数组中保存着每个节点所指向的父节点的索引。比如parent[4]等于1就表示节点4的父节点为节点1

（2）当parent[i] = i时，表示节点i就是该子树的父节点。

当我们需要进行union的时候，我们只需要改变改变该子树根节点的指向就行，也就是改变该子树根节点的父节点，比如我们要union(4,6)的是时候我们就需要找到4和6节点所在的根节点，然后将其中任意一个子树的根节点指向另一个子树的根节点就行，如下图所示：

在parent数组就只需要找到该子树的根节点，然后重新赋值就可以就不需要挨个进行重新赋值，此时的parent数组更新为：

 0123456parent5252155

因此，我们就需要一个函数find()函数：用来寻找某个节点的根节点，当parent[i]=i是，节点i就是该子树的父节点。find函数代码如下：

int find(int p){ // 不断去查询自己的父亲节点, 直到到达根节点 // 根节点的特点: parent[p] == p while( p != parent[p] ) p = parent[p]; return p; } // 递归实现 int find(int p){ if(parent[p] == p) return p; return find(parent[p]);

此时的union函数就可以这样理解：对于节点i和节点j，我们首先要找到两个节点所在子树的根节点，然后将其中的一个根节点的指向另外一个就行，union的代码如下：

void unionElements(const int p, const int q) { int qRoot = find(p); int pRoot = find(q); if (qRoot = pRoot) return; // 让q子树的根节点指向p节点的根节点 parent[qRoot] = pRoot; }

但是，这种union方法并不是最优的，当两个子树的元素的个数不一致的时候，通常来说节点多的子树find的时间就比较耗时，如果我们在union的时候任选一个根节点作为另一个子树的新的根节点的时候，可能会造成子树的高度增加，就比如下面这种情况：

当树的高度增加的时候，会额外增加find函数的时间消耗，因此我们可以让子树元素小的根节点指向那个子树数量多的子树的根节点。

3 基于size的优化

因此，我们需要一个额外的sz数组来保存每个根节点所代表的子树中元素的数量，在union中修改子树根节点指向的时候，作为哪个根节点需要进行修改的标准。优化之后的union方法就如下：

/*操作：将两个节点的状态置为同一状态*/ /*结果：无返回值。同一状态的某个节点发生变化了，原同一状态的其他节点也要变化*/ void unionElements(const int p, const int q) { int qRoot = find(p); int pRoot = find(q); if (qRoot = pRoot) return; // 让树节点少的指向树结点多的 if (sz[pRoot] < sz[qRoot]) { parent[pRoot] = qRoot; sz[qRoot] += sz[pRoot]; } else { parent[qRoot] = pRoot; sz[pRoot] += sz[qRoot]; } }

但是，有时候还会出现另外一种情况，节点多的子树可能高度并不会大于节点少的子树，就比如下面这种情况：

当让元素少的根节点指向元素多的根节点的时候，反而造成了子树的高度增加，因此，我们可以代替sz数组，使用rank数组用来保存每个子树的各节点的树高。

4 基于rank的优化

rank数组中保存着每个节点的高度，但是我们其实只关注根节点的树高，因此这才是整个子树的树高，其他节点的rank数组的意义其实不大。因此，在union的时候，我们让树矮的指向树高的根节点。需要注意一下，当树矮的指向树高的根节点的时候，树高的高度并没有改变，即rank[root]并没增加；只有当两个子树的高度相同的时候，才会增加新子树的高度。基于rank的优化union的代码如下：

/*操作：将两个节点的状态置为同一状态*/ /*结果：无返回值。同一状态的某个节点发生变化了，原同一状态的其他节点也要变化*/ void unionElements(const int p, const int q) { int qRoot = find(q); int pRoot = find(p); if (qRoot = pRoot) return; // 让树矮的指向树高的根节点 if (rank[pRoot] < rank[qRoot]) parent[pRoot] = qRoot; else if (rank[pRoot] > rank[qRoot]) parent[qRoot] = pRoot; else { // rank[pRoot] == rank[qRoot]，两个数等高,让qRoot指向pRoot的数 parent[qRoot] = pRoot; rank[pRoot] += 1; } }

从上面的优化思路我们可以看出，我们的最终目的就是让更新之后的新子树的高度尽量的“矮”一些。既然明白了这一点，我们能不能让数组在刚开始的时候就尽可能的矮一些。其实，在刚开始的时候，相连的节点状态时一直的，如果我们把每个状态看成一个子树的根节点，这个子树就是最矮的。因此，我们的最终目的就是这样的：让相同状态的节点直接指向子树的根节点，这样对find函数会轻松很多。难点就是，即使刚开始的子树最矮，但是随着union函数的调用，会让整个树的高度只增不减，因此我们只处理跟节点的指向。我们如何在处理某个节点的时候，当发现它的父节点不是根节点的时候，对其进行修改，让其父节点修改成该子树的根节点？我们可以在find函数中处理：当寻找某个节点的根节点的时候，如果发现该节点的父节点不是根节点，我们就修改其父节点为根节点。这个方法我们称之为路径压缩。

5 路径压缩

路径压缩是将某个节点的父节点修改成该子树的根节点的方法，我们可以在find函数的时候就进行修改：

该find方法的思路就是：如果当前节点不是根节点，就修改其父节点为根节点，然后返回根节点；如果当前节点是根节点，就直接返回当前节点就行。

优化之后的find函数代码如下，我们可以发现，相比于原来的代码，find函数只不过在其中加入了修改其父节点的一行代码。

/*操作：寻找节点p的根节点*/ /*结果：返回int类型数据。表示p节点的根节点*/ int find(int p) { if (parent[p] == p) return p; parent[p] = find(parent[p]); return find(parent[p]); }

6 实验

在这一部分，我们对比了基于rank优化和基于size优化的时间损耗，它们在find函数上都使用了优化版的find函数，整个代码如下（只放了基于size的优化的代码，基于rank的对照上面的代码进行修改即可）

#pragma once #ifndef _UNIONFIND2_H_ #define _UNIONFIND2_H_ namespace UF2{ class UnionFind { private: int *parent; int *sz; int count; public: /*构造函数和析构函数*/ UnionFind(int count) { this->count = count; parent = new int[count]; sz = new int[count]; // 初始化parent和rank for (int i = 0;i < count;i++) { parent[i] = i; sz[i] = 1; } } ~UnionFind() { delete[] parent; delete[] sz; } /*操作：寻找节点p的根节点*/ /*结果：返回int类型数据。表示p节点的根节点*/ int find(int p) { if (parent[p] == p) return p; parent[p] = find(parent[p]); return find(parent[p]); } /*操作：判断两个节点是否相连*/ /*结果：返回bool类型数据。如果相连返回true；否则，返回false*/ bool isConnected(const int p, const int q) { return find(p) == find(q); } /*操作：将两个节点的状态置为同一状态*/ /*结果：无返回值。同一状态的某个节点发生变化了，原同一状态的其他节点也要变化*/ void unionElements(const int p, const int q) { int qRoot = find(p); int pRoot = find(q); if (qRoot = pRoot) return; // 让树节点少的指向树结点多的 if (sz[pRoot] < sz[qRoot]) { parent[pRoot] = qRoot; sz[qRoot] += sz[pRoot]; } else { parent[qRoot] = pRoot; sz[pRoot] += sz[qRoot]; } } }; } #endif // !_UNIONFIND2_H_

实验1：规模为10000000数据量的数组

实验结果如下

第一个是基于rank的优化，第二个是基于size的优化，我们发现基于size的优化要略优一些，下面我们增加数据量来看看

实验2：规模为100000000数据量的数组