并查集算法及其应用浅析

摘 要：并查集是一种树型的数据结构，用来处不相交集合的查询与合并问题。本文介绍了并查集的算法及其思想，针对其某些问题提出改进措施，并探讨并查集的应用。

关键词：并查集;应用;算法分析

问题引入

2020年新型冠状病毒席卷全球。如果一个感染者走进一个群体，并且没有任何个人防范措施，那么这个群体需要尽快找到并且隔离。那么如何找到与感染者接触的群体？我们可以用并查集来进行解决。

下面将上述问题提取出数学模型，便于我们进一步分析问题。

首先我们对群体中的每个人进行编号，用N来表示，为了在数组中表示方便，我们将N的取值范围设置为0～N-1。我们将群体数目用M来进行表示。

接着我们从算法的角度讨论程序的输入与输出。程序的输出是，给定一个编号，寻找和这个人接触的群体。即假设编号为x是我们发现的感染者，输出与x接触的人的编号以及所有接触者的数量。同样上个例子，我们寻找与编号5接触的人的编号，即输出6，7，8，9，数目为4人。

1.并查集算法及其思想

1.1存储结构

Bernard A. Galler和Michael J. Fischer于1964年提出了并查集的森林表示形式：用一颗多叉树来表示一个集合，树中的每个节点都保存着对它父节点的引用，所有的不相交集合即可形成一个森林，并且每个集合的“代表”就是对应的树的根节点。

可以用双亲表示法，下面以数组存储结构为例介绍集合的表示方法。数组中每个元素的类型可以表示为如下：

typedef struct{

elementType data;

int parent;

}set

其中elementType 是在头部定义的数据类型，可以根据需要进行更改。

比如如下集合

可以用结构体数组来进行存储，存储方式如下：

注：我们用负数表示根节点，非负数表示表示双亲节点的下标。

1.2算法实现

并查集算法主要涉及三种操作，初始化，查找和合并。其中初始化是将所有数据的parent变量赋值为-1。

查找某个元素属于哪个集合，以及对两个集合进行合并。

查找某个元素所在的集合，采用上述存储结构，代码如下，我们用根节点表示所在集合。以C语言为例。

int find（set s[]，elementType x）

{

int i;

for（i=0;i

if（i>=maxsize） return -1;

for（;s[i].parent>=0;i=s[i].parent）

return i;

}

void union（set s[]，elementType x1， elementType x2）

{

int root1，root2;

root1=find（s，x1）;

root2=find（s，x2）;

if（root1！=root2）

s[root2].parent=root1;

}

2.并查集改进

2.1数据结构的改进：当数据为int 类型时，我们可以用数组的下标来表示数据。

程序的改进如下：

相应的函数变为如下：

int find（set s[]，elementType x）

{

for（;s[x]>=0;x=s[x]）

return x;

}

union 函數中将最后一行代码改为如下

s[root2]=root1;

分析：改造后的程序，从空间上减少了对于数据编号的存储，降低了数据的冗余，从时间看，在find函数中减少了一次for循环，当数据量很大，比如超过10的4次方时，会大大加快程序的速度。但是这种改进仅限于存储的数据类型也是int类型的时候，具有一定的局限性。

2.2union函数的改进

我们发现union 函数要调用find函数，即首先找到两个元素的根节点，判断是否在一个集合内，即判断根是否相等，如果不同再进行归并。当数据为n时，union的时间复杂度达到n的平方。所以在进行树之间的合并时，需要先判断树的高度，将矮的树挂在高的树上，这样就不会存在树随着合并次数的增多逐渐增高的问题。

那么如何存储树的高度呢，我们可以在结构体中再增加一个变量，保存树的高度，但是这种做法浪费存储空间。可以用大小来表示树的高度。

伪代码如下：

if（root2高度>root1高度）

s[root1]=root2;

else

{  if（两者等高） 树高++;

s[root2]=root1;

}

通过改进时间复杂度降低到logn。这种方法我们称为按秩归并。

2.3路径压缩

上述算法在一定程度上降低了树的高度，但是当两颗树的高度相同时还是会面临像上述所述情况的发生。路径压缩的思想是先找到某个元素x的根节点，然后把根变成x的父节点，然后返回根，这样下次再找x时，通过x就能直接找到根，直接降低了根到元素之间的距离。代码如下：

int find（set s[]，elementType x）

{

if（s[x]<0） return x;

else return s[x]=find（s，s[x]）

}

算法采用了递归，将递归遍历中遍历过的节点都变成根节点的儿子节点，降低了树的高度，提高了算法的效率。但是这种方法适用于元素数量比较大的情况，当数量集比较小的时候，算法的优势表现不出。

3并查集相关应用

并查集的思想在解决很多问题上得到了应用，下面简单举几个例子。

3.1 Kruskal算法中求最小生成树的问题上。的核心思想是在图中将所有的边按照从小到大排序，每次选取最小边并入选出的最小生成树的集合中去，但是选出的边不准许存在环路。我们可以用并查集的思想解决，当选出的边与其他边在同一个集合中，那么跳过这条边。

3.2找亲戚问题。如果某个家族人员过于庞大，要判断两个是否是亲戚也很不容易。可以根据目前已知的亲戚种族关系判断给出的两个人是否有亲戚关系。

结语

并查集这种数据结构十分的巧妙，可以有效快速解决有关集合合并、元素归属等问题。它是一种工具，应用于解决很多问题。其中在图的应用中解决点与点的几何关系，维护图的关系，使问题迎刃而解。

参考文献：

[1]王晓东.数据结构（C语言描述）.第3版.北京.电子工业出版社，2019

作者简介：

姓名：满冉冉，1991 年2  月，籍贯：山东滕州，性别 ： 女 ，最高学历：研究生 ，职称：助理实验师 ，职务： 科员，研究方向：计算机应用技术 ， 毕业院校：大连大学。