1. 前言
并查集是一种抽象数据结构，可以从名字上解释其功能。
-
集：操作对象是集合群，并查集是与
集合操作有关的数据结构。 - 查：查询元素所在的集合。
- 并：合并元素之间关系的集合。
并查集是一种优雅而灵动的数据结构。
让我想到清晨荷叶上的一颗一颗水珠，初始是分开的。在微风摇曳中，小水珠们开始跳动并彼此融合，最终由最初的十几个水珠变成了几个较大的水珠，在清晨的微阳中温润透澈。
并查集的应用非常广泛。并查集能根据个体或小集体之间的特定关系建立起更大的群体组织，类似于人类社会从远古到当今的自治性融合。并查集在社交应用开发等领域使用非常广泛。
本文将通过一个问题引入并查集工作细节。
2. 问题驱动
在公考之类的考试中，经常会出现一些思维逻辑题。好吧，现在给你出一个。
现有一公司，有 9 名员工，分别工作在不同的部门。员工入职时，给其分配有编号，分别从1~9。
如下，提供员工与员工之间的关系信息，请你根据这些关系判断 (2,6)是否在同一部门?以及此公司共有几个部门?
2 4 //编号为 2 、4 的员工在同一部门
5 7
1 3
8 9
1 2
5 6
2 3
2.1 自引用思想
常规思维和第一感觉会告诉我们，这个问题其实很简单。
你只要从某一个员工开始，顺藤摸瓜，就能把和此员工有直接或间接关系的员工全部找出来，类似于数据库中的自查询操作，自查询是基于表设计时的自引用。
如从编号为2的员工开始：
- 在同一张表中，查找与其有
直接关系的员工2->(4,1,3)。 - 还是在同一张表中，继续查找与直接关系有关系的
间接关系的员工4->(无)、3->(1)、1->(3)。 - 最终结论，可知
2,4,1,3是在同一部门。可判断(2,6)不在同一个部门。 - 当然，你可以使用相同的过程找出所有在同一部门的员工，最终也将知道公司有几个部门。
说起来轻巧，数据库系统有自查询语句，而C++没有，如何编码？
潜意识会告诉你，嘿！这种先查近亲、再查远房亲戚类似于波浪向外推动的查找方式不就是书本上所说的广度搜索吗！
好吧！现在马上开工，编写一个程序。
- 直接使用二维数组存储员工与员工之间的关系。
- 编码实现。
#include <iostream>
#include <queue>
using namespace std;
//员工之间的关系
int emps[7][2] = {
{2,4},
{5,7},
{1,3},
{8,9},
{1,2},
{5,6},
{2,3}
};
//关系是否已经使用
int isUse[7][2] = {
{false,false},
{false,false},
{false,false},
{false,false},
{false,false},
{false,false},
{false,false}
};
//队列
queue<int> myQueue;
//结果
vector<int> path;
/*
*相邻员工压入队列
*/
void pushQueue(int val,int* pos) {
if(pos[1]==0 && isUse[ pos[0] ][ pos[1]+1 ]==false ) {
//右边
myQueue.push( emps[ pos[0] ][ pos[1]+1 ] );
isUse[ pos[0] ][ pos[1]+1 ]=true;
} else if( pos[1]==1 && isUse[ pos[0] ][ pos[1]-1 ]==false ) {
//左边
myQueue.push( emps[ pos[0] ][ pos[1]-1 ] );
isUse[ pos[0] ][ pos[1]-1 ]=true;
}
}
/*
* 根据值查找员工在二维表中的位置
*/
void findPos(int val) {
int* pos= new int[2];;
for(int row=0; row<7; row++) {
for(int col=0; col<2; col++) {
if( emps[row][col]==val) {
pos[0]=row;
pos[1]=col;
//本身值为已经处理
isUse[row][col]=true;
//相邻员工
pushQueue(val,pos);
}
}
}
}
/*
* 深度搜索
* 参数说明
* startId 起始员工编号
* endId 结束员工编号
*/
void bfsPath(int startId) {
//压入队列
myQueue.push(startId);
int tmpId;
while(!myQueue.empty()) {
//取队头数据
tmpId= myQueue.front();
//加入路径
path.push_back(tmpId);
myQueue.pop();
//找到与之相邻的员工，且压入队列
findPos(tmpId);
}
}
//测试
int main(int argc, char** argv) {
bool isConn=false;
bfsPath(2);
for(int i=0; i<path.size(); i++ ) {
cout<<path[i]<<"\t";
if(path[i]==6)isConn=true;
}
if (isConn)
cout<<"\n2、6 是同一部门"<<endl;
else
cout<<"\n2、6 不是同一部门"<<endl;
return 0;
}
输出结果：
编号为3的员工出现了 2 次，不考虑自己与自己的关系，则表示关系中会有一个环。
2.2 图论思想
至此，你没有什么成就感。
相信内心应该会闪过一丝不甘，虽然结论正确，但是，代码繁琐，没有丝滑之感。
原因何在？
因为上述代码中，要通过值在二维表中查找位置，再通过位置找到有关系的值，非常繁琐。意味着数据结构的设计不是很恰当。
思考之后，会发现，员工与员工的关系是多对多关系，图论的思想立马涌上心头。
可以以员工为顶点，员工之间的关系为边，构建出一个图数据结构。
图的关系存储常用的有 邻接矩阵和链表。本文使用邻接矩阵，如下图所示。
现在查询员工之间是否有关系，相当于在图中查询顶点之间的连通性。如下使用相邻矩阵描述图中顶点间的关系。矩阵值为 1 处表示员工编号和行编号和列编号相同的员工有关系。
重构数据结构之后，编码是不是会简单些？
编写一下不就知道了吗！
#include <iostream>
#include <queue>
using namespace std;
//邻接矩阵
int emps[10][10] = {
{0,0,0,0,0,0,0,0,0,0},
{0,0,1,1,0,0,0,0,0,0},
{0,0,0,1,1,0,0,0,0,0},
{0,1,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,1,1,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,1,0},
{0,0,0,0,0,0,0,0,0,0}
};
queue<int> myQueue;
vector<int> path;
/*
* 深度搜索
* 参数说明
* startId 起始员工编号
*/
void bfsPath(int startId) {
//起始员工编号压入队列
myQueue.push(startId);
while( !myQueue.empty() ){
//队头员工编号
int topId= myQueue.front();
path.push_back(topId);
myQueue.pop();
//查找与之有关系员工
for(int col=1;col<10;col++){
if( emps[topId][col]==1 ){
//找到时相邻压入队列
myQueue.push(col);
//-1 表示已经查找
emps[topId][col]=-1;
}
}
}
path.erase(path.begin());
}
//测试
int main(int argc, char** argv) {
bool isConn=false;
bfsPath(2);
for(int i=0; i<path.size(); i++ ) {
cout<<path[i]<<"\t";
if(path[i]==6)isConn=true;
}
if (isConn)
cout<<"\n2、6 是同一部门"<<endl;
else
cout<<"\n2、6 不是同一部门"<<endl;
return 0;
}
输出结果：
结果是一样的。
为什么在搜索算法思路不变的情况下，仅改变了数据结构，代码量的区别这么大？
原因很简单，因为算法在意的是员工之间的关系，如果能快速查找到关系，算法可专注核心逻辑，而无须再提供大量查找关系的代码。这也是数据结构对算法的影响。
行和列的编号与员工编号相映射，图的邻接矩阵又直接存储了员工关系，当然要方便很多。
但是，当公司规模变大，邻接矩阵会随着员工人数的激增而变成一张巨大的表格。因邻接矩阵是一个稀疏矩阵，显然，使用图数据结构除了会浪费空间，还有点像在一堆黄豆中找一颗豌豆，空间和性能都不划算。
是否还有更好的数据结构可选择？
当然有！并查集。
3.3 并查集
3.3.1 并查集思想
并查集对数据管理的过程类似小水珠融合成大水珠的过程。在并查集中，给水珠重新起一个名字：集合。
- 初始，一个员工为一个集合，并且给集合一个唯一的代表符号。
-
并查集会根据员工之间的关系，分析员工是否在同一集合（根据集合的唯一代表符区分），如果不在，则合并员工所在的集合。如下
(2,4)、(5,7)、(1,3)、(8,9)是合并后的集合。Tips：
合并的字面意思是把一个集合的数据搬移到另一个集合，然后删除本集合。当然，代码层面，各有各的技巧。
- 继续根据员工之间的关系考虑是否合并集合。因为
(1,2)在不同的集合，合并所在的两个集合。同样(5,6)在不同集合，合并。
-
(2,3)已经在同一个集合，不用合并。最后融合成3个集合。同一个集合中的员工必然在同一个部门。
使用并查集自身的查找、合并就完成了部门的归类。演示图中，很清楚得到编号为2和6的员工不在同一部门的结论。
3.3.2 并查集的实现
并查集是抽象数据结构。物理结构上可以使用数组或链表的方式存储。本文选择数组。
并查集的抽象API主要有 3 个：
-
initSets(x)：初始化集合群，此函数只需要调用一次。 -
find(x)：查找某个元素所在的集合，返回集合的唯一标识符。 -
union(x,y)：合并2个集合。
并查集类：
#include <iostream>
using namespace std;
/*
*并查集类
*/
class UnionSet {
private:
//集合群
int* sets;
//集合数
int size=0;
public:
/*
*构造函数
*/
UnionSet(int size) {
this->size=size;
this->sets=new int[size];
this->initSets();
};
/*
*初始化集合群
*/
void initSets();
/*
*查找数据所在集合的唯一标志符
*/
int find(int data) ;
/*
*合并集合
*/
int unionSet(int sId,int sId_) ;
/*
*显示
*/
void showAll() {
cout<<"集合数:"<<this->size-1<<endl;
for(int i=1; i<10; i++)
cout<<"员工编号"<<i<<"，父结点编号："<<this->sets[i]<<endl;
cout<<endl;
}
};
initSets初始化函数：
功能描述：初始集合群。
随着集合的合并，集合的容量会增强。一般会以其中一个元素作为标志符，其它元素需要直接或间接存储这个无素，方能证明自己是一家人。集合中元素之间的逻辑关系可用树结构描述，用作标志符的元素称为根结点。
-
初始化时，员工的信息存储在数组中与员工的
编号相同的索引位，且初始值为员工编号。 -
意味着一个员工为一个集合（树），且使用自己的编号作为集合的唯一标志符号。 也意味着树只有唯一的根结点。
Tips： 数组索引号为
0位置不用。
/*
*初始化并查集
*/
void UnionSet::initSets() {
for(int i=0; i<UnionSet::size; i++) {
//初始，集合以自己的值为标志符
UnionSet::sets[i]=i;
}
}
find(x)查询函数：
功能描述： 检查员工所在的集合，返回员工所在集合的唯一标志符（员工所在树的根结点）。
在集合（树）中，如果根结点是自己则返回，否则根据存储的直接父结点一路向上追溯到根结点。
/*
* 查询数据所在集合
* 返回集合唯一标志符
*/
int UnionSet::find(int data) {
while (UnionSet::sets[data]!=data) {
//得到父结点编号
data=sets[data];
}
return data;
}
union(x,y)函数：
功能描述：合并2 个元素所在的集合。合并流程如下所示：
- 查找元素的根结点是否相同。不相同，说明不在同一个集合，则合并。如下合并
(2,4)、(5,7)、(1,3)、(8.9)的过程。
- 合并时，修改一个集合的根结点指向另一个集合的根结点。如下合并
(1,2)过程。
/*
*合并集合
* 参数：sId，sId_ 2个集合的根结点
*/
int UnionSet::unionSet(int sId,int sId_) {
if(sId!=sId_) {
//不是同一个集合
UnionSet::sets[sId]=sId_;
//或者
// UnionSet::sets[sId_]=sId;
UnionSet::size--;
return sId;
}
return 0;
}
测试：
//测试
int main(int argc, char** argv) {
UnionSet unionSet(10);
int emps[7][2] = {
{2,4},
{5,7},
{1,3},
{8,9},
{1,2},
{5,6},
{2,3}
};
int sId=0;
int sId_=0;
for(int i=0; i<7; i++) {
sId= unionSet.find( emps[i][0]);
sId_= unionSet.find( emps[i][1]);
unionSet.unionSet(sId,sId_);
}
unionSet.showAll();
if(unionSet.find(2)==unionSet.find(6) )
cout<<"(2,6)在同一个部门"<<endl;
else
cout<<"(2,6)不在同一个部门"<<endl;
return 0;
}
输出结果：
为了讲明白并查集的细节，用了点篇幅。
而实际上并查集的实现代码量并不多，且在解决员工是否在同一部门这个问题时，仅需要并查集自己的API就可实现。并不需要额外的算法逻辑。
在此基础之上，可以提供函数，得到所有部门，且包括部门中的所有员工信息。有兴趣者可自行研究。
3. 优化并查集
优化不是心血来潮之意。只有明白并查集性能瓶颈之处，方能对症下药。
并查集的性能瓶颈在查找元素所在集合时。如下图所示的集合：
如果要查找值为 6的结点的根结点位置。则需要一路向上追溯。
当树的深度越大或说树不平衡时，时间代价高，追溯性能越低。
并查集中，数据之间以树为逻辑结构，无非是看重了树结构中根结点的唯一性特点，正是用这个唯一性来标志集合的唯一性。树本身是什么结构其实并不重要。
提高性能的方向，尽可能地降低树的深度。 合并性能依赖于查找性能，查找性能上来了，大家皆大欢喜。
具体优化实施
优化合并函数
- 合并时，让深度低的树作为深度高的树的子树。如下图所示。
- 如果让根结点
4合并到根结点3上，则会让树越来越高。反之，可以降低树的深度。
在并查集中可以提供一个计算树高度的API。这将略显繁琐，可以使用一维数组记录每棵树的高度。
class UnionSet {
private:
//省略……
//记录集合（树）的深度
int* deep;
public:
//省略……
重构初始化函数：
/*
*初始化并查集
*/
void UnionSet::initSets() {
for(int i=0; i<UnionSet::size; i++) {
//初始，集合以自己的值为标志符
UnionSet::sets[i]=i;
//初始只有根结点，高度为 0
UnionSet::deep[i]=0;
}
}
重构合并函数：
/*
*合并集合
*/
int UnionSet::unionSet(int sId,int sId_) {
if(sId==sId_)return 0;
if( UnionSet::deep[sId]==UnionSet::deep[sId_] ) {
//高度相同，谁合并谁都没关系
UnionSet::sets[sId]=sId_;
//高度增加
UnionSet::deep[sId_]++;
} else if( UnionSet::deep[sId]>UnionSet::deep[sId_] ) {
//低树向高树合并，整体高度不变
UnionSet::sets[sId_]=sId;
} else {
UnionSet::sets[sId]=sId_;
}
UnionSet::size--;
return 1;
}
输出结果： 可见 5，6都指向 7。
通过保持树的相对平衡性，可以让查找函数的时间复杂达到O(logN)。
优化查找函数
在查时对集合(树)进行路径压缩。
- 如下图要查找值为
1的结点所在树的根结点时。
- 使用递归思路，把此结点以及向上所有结点的父指针都指向根结点。
重构查找函数：
int UnionSet::find(int data) {
if( UnionSet::sets[data]==data) {
//根结点
return data;
}
//向上查找父结点
int parent= UnionSet::find(UnionSet::sets[data]);
//回溯时赋值
UnionSet::sets[data]=parent;
return parent;
}
最后可以扁平化树结构，再查找时的时间复杂度可以达到O(1)。
但是，如果不是查找值为1的结点，而是值为3的结点，树会变成如下图所示。当然，可以为结点添加指向子结点的指针，当结点的父指针发生变化后，让子结点也同步更新。
在数据量巨大的真实应用场景中，随着每次查找、合并操作，每一棵树会有逐渐趋向于扁平化走势。要相信积累的力量。
在重构合并和查找函数之后再测试如下代码
//测试
int main(int argc, char** argv) {
UnionSet unionSet(10);
int emps[8][2] = {
{2,4},
{5,7},
{1,3},
{8,9},
{1,2},
{5,6},
{2,3},
{1,8} //添加了新的关系
};
int sId=0;
int sId_=0;
for(int i=0; i<8; i++) {
sId= unionSet.find_( emps[i][0]);
sId_= unionSet.find_( emps[i][1]);
unionSet.unionSet(sId,sId_);
}
unionSet.showAll();
if(unionSet.find_(2)==unionSet.find_(6) )
cout<<"(2,6)在同一个部门"<<endl;
else
cout<<"(2,6)不在同一个部门"<<endl;
return 0;
}
输出结果：
合并后会有 2 棵树： 扁平化趋势较明显。
4. 总结
本文从一个问题出发，引出了并查集，并讨论了并查集的优化问题。并查集不难理解，就看在真正需要的场景，你是否能想起它。
除此之外，并查集在物理结构上也可以选择链表实现。