关于动态连通性算法的研究

朱伶虎 吴超 张帅杰 陈健

摘要：在生活中关于动态连通性的案例比比皆是，尤其在油田井间、网络节点等方面应用较为丰富。在此将针对动态连通性问题进行对其常用的三种算法进行探究，完成其三种算法的实现以及测试，而后通过算法的改进，选择出其中运行效率最高的解决动态连通性问题的算法。

关键词：动态连通性;算法;运行效率

中图分类号：TP311     文献标识码：A

文章编号：1009-3044（2021）26-0164-04

开放科学（资源服务）标识码（OSID）：

Research on Dynamic Connectivity Algorithm

ZHU Ling-hu， WU Chao*， ZHANG Shuai-jie， CHEN Jian

（Liupanshui Normal University， Liupanshui 553004， China）

Abstract： In our life， there are many cases about dynamic connectivity， especially in the fields of well to well and network nodes. In this paper， we will explore the three commonly used algorithms for the dynamic connectivity problem， complete the implementation and testing of the three algorithms， and then select the most efficient algorithm to solve the dynamic connectivity problem through the improvement of the algorithm.

Key words： dynamic connectivity; algorithm; operation efficiency

動态连通性是图论中的一种用于判断两点之间是否相连的数据结构 [1]。在生产生活中也有比较广泛的应用，如在计算机网络部署中、油田井间、电路芯片的晶体管、照片的像素、数学集合中的元素等方面。但常见的动态连通性算法已经跟不上现代社会的发展速度。本文主要在动态连通性三种常见算法，quick_find算法（下文用QF表示）、quick_union算法（下文用QU表示）和加权quick_union算法（下文用WQU表示）的基础上进行研究。从连接路径的角度出发，采取压缩路径或者减半策略对动态连通性算法进行优化，比较其与三种常见算法的效率以及其自身所能达到的运算数量级。

1 模型建立

1.1 问题的描述

动态连通性问题的输入是一列整数对，其中每个整数都表示一个某种类型的对象（例如网络中的一台电脑或者朋友关系中的一个人），一对整数R1，R2被理解为相连的，我们假设“相连”是一种等价关系，即具备自反性，对称性，传递性三种特性。

动态连通性问题就是当读取任意一对整数对时，若用已知关系可以判断该对整数相连，则忽略该对整数，否则将该对整数相连，然后打印输出此整数对，当所有整数对读取完毕后，输出连通分量的数量。

1.2 建立模型

根据问题描述，假设用0—N-1个整数表示N个对象，现假设初始状态时每个单独的对象都与本身相连。若对象R1与R2不相连则将他们划分到一个集合中，若相连则忽略。

为方便研究，现以数组作为基本的数据结构，以数组的下标作为研究的对象。如下图所示：

2 QF、QU和WQU

QF算法是以数组ID为基本的数据结构，以数组的下标作为研究对象。初始状态时所有对象都是相互独立的。若读入整数R1与R2，则比较ID[R1]与ID[R2]是否相同，相同则忽略，不同则将ID[R2]与ID[R2]相同的数组内容改为ID[R1]。在最坏的情况下，QF算法的时间复杂度时O（N2）。

QU算法同样是以数组ID为基本的数据结构，以数组的下标作为研究对象。但在对象所构造的数据结构上是以树型结构为基础。每个对象R都是以自己为根节点的一棵树，即数组ID中的内容就是对象R本身。当读入整数R1与R2，若属于同一棵树就忽略，若不同则找到R1与R2所在树的根节点，将R2所在的树的根节点连接到R1所在的树的根节点上，完成对象R1与R2的相连。在最坏的情况下，QU算法的时间复杂度是O（N）～O（N2）。QU算法在整体的效率上要高于QF算法，因为主要影响其时间复杂度的是树的高度。

WQU是在QU算法上的进一步改进，因为影响QU算法的主要问题是树的高度，而树的高度的增加是因为在两棵树连接时，会出现三种情况，小树连在大树上，两颗相同的树连接，大树连在小树上。后两种情况会导致树的高度增加，但两棵树相同时，树的高度只增加1，而大树连在小树上，会使得原来小树的高度大幅度增加，致使QU算法的时间复杂度增加。WQU是使用一个数组RS[]记录树的大小作为权值，当两棵树连接时，将权值小的树连接到权值大的树上。在最坏的情况下，WQU的时间复杂度是O（lgN）。相对前两种算法有了进一步的提高。

3 压缩路径算法（CP_WQU）

3.1 基本思想

WQU是记录分量所构成树的大小作为该分量的权值，然后将权值小的树挂在权值大的树的根上完成分量的合并，其算法的复杂度在最坏的情况下是lgN。在加权QU的基础上还可以进行路径的压缩以进一步提高算法的效率。

基本思想是当第一次遍历存储分量的数组时，将各个分量都指向其根节点。那么在下一次输入整数对R1，R2时，在查找其根节点的时间复杂度就是常数级。缺点是在第一次遍历数组时，其时间复杂度是原来WQU的2倍，但对于之后的算法的效率提高是有显著作用的。