基于Java语言对动态连通性算法的研究

张帅 方欢 鞠悦

摘要：动态连通性是图论中的一种用于表示两点之间是否相连的数据结构，它可以准确地反映出图中个点之间的连接信息。动态连通性的应用广泛，为寻找出一种能够有效解决动态连通性问题的方法，基于java语言对三种动态连通性算法进行实现和测试，通过对结果的分析，判断每种算法的运行时间及效率，选择出最为有效的解决动态连通性问题的算法。

关键词：动态连通性;快速合并;快速查找;加权快速查找;运行效率

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

文章编号：1009-3044（2020）01-0267-04

动态连通性是一种在计算机图论中的一种数据结构，它可以有效地反映出图结构中对象与对象相连接的组信息，包括在图中各个点是否相互连接、连接之后会组成多少个信息组。动态连通性在实际生活中的应用也很多，如油田井间、网络节点、路劲优化等方面都有着广泛的应用。本文针对动态连通性问题进行算法实践和研究，利用java语言编程对图节点快速查找、快速合并以及加权快速合并算法的实现和测试，并总结出三种算法的运行特点以及其中效率最高的解决动态连通性问题的算法。

1问题的提出

1.1问题提出

先来详细地说明一下所要求解的问题，假设共有N个对象，这些对象是可以相互连通的，使用0到n的整数对其进行标记，现在假设程序拥有两个操作，一个操作是用来连接两个对象，通过参数将两个对象p和q传入该命令，該命令会对其进行连接操作;另一个操作是对两个对象连通性的查询，即查询p和q之间是否存在连通的路径，当然，只需要判断这条路径是否存在，并不需要找此路径。

例如图1所示，假设已经执行过相关的连接操作rF文简称union），连接了4和8，连接了2和3，连接了3和7等等，接下来可以对图1进行连通性查询操作（下文简称connected），程序执行connected（O，7）操作，观察图1，显然0与7是不具有连通性的，程序执行connected（1，9）操作，显然1与9是连通的。在此也可以进行大量的union操作，女Iunion（3，1），使得图中的连通分量不断的减小，最终使得图1中的每个对象之间都具有连通性，而所要处理的问题是如何在较短的时间内执行大量的合并操作和连通查询操作。

1.2动态连通性性质

对问题性质的分析，可以更好地实现和改进算法，在动态连通性问题中，根据离散数学，假设两个对象之间的“相连”是一种等价关系，这也就意味着动态连通性会具有三个性质：

1）自反性：针对同一个对象是相连的，如p与p是相连的;

2）对称性：两个对象相互连接是双向的，如：p与q是相连的，那么q与p也是相连的;

3）传递性：对象与对象的连接是传递的，如：p与q是相互连接的，q与r是相互连接的，那么p与r也是相互连接的。结合对问题性质的分析，对所提出的问题进行简单的实现。

1.3问题的简单实现

先对此问题进行简单的实现，在解决问题时，数据结构的选择往往将会直接影响到算法的效率，因此，在解决此问题时，可以使用一个以标识符0到n作为索引的数组a[]来解决此问题，通过判断和改变每个元素所保存的信息（用整数表示）实现连接和判断连接的操作，若两个对象所保存的a口值相等，则代表它们在同一连通分量中，它们是相连的。

在实现问题之前，首先需要了解所要实现的操作有哪些，见表1。

根据表1，对问题进行简单的代码实现：

首先读取一个正整数N来表示所要研究的对象个数，利用DC的构造函数来初始化a口数组，判断p和q是否已经连通，若不连通则执行连通操作。

在对问题进行简单实现之后，下面对相关算法做出介绍。

2算法的介绍及实现

2.1快速查找（quick-find）

第一个算法为快速查找算法，通过对问题的分析，最终选择了数组作为本次求解问题的数据结构，而数组中的每一项所记录的为此元素的相连信息，因此当利用java语言实现con-nected（p，q）操作时，只需要判断两个对象p和q所记录的数值是否相同来判断他们是否相连，在实现union（p，q）操作时，需要将p节点所记录的数值保存，之后将q所记录的数值赋值给p，并利用循环，将与p所在的同一连通分量的所有对象的a口值全部更改为q所记录的a口值，来实现合并操作。

结合图1和图2，未实现union（3，1）操作时，图中总共有4个连通分量，分别为{0}，{4，8}，{2，3，7}和{1，6，5，9}，根据图2所示，在同一个连通分量中的对象所记录的a口值是相同的。在执行完union（3，1）操作，对象3所记录的a口值变为了1，并且与对象3所在同一连通分量的所有对象的a口值均变为1，连通分量减少了1，对象3和1实现了连接，代码实现如下：

2.2快速合并（quick-union）

再利用java语言实现快速合并算法时，将图中的每一个连通分量以树的方式表示，在数组中将每一个元素所记录的a[]值与父节点相联系，在执行union（p，q）操作时，首先，找到p和q节点的根节点，之后将p节点的根节点的a口记录值设置为q节点的根节点，通过对两个根节点相连来实现连通分量的合并。

执行union（3，1），首先找到1节点的根节点为1，然后找到3节点的根节点为2，在图中将2节点和1节点相连，则实现了将3节点与1节点的连接操作，使得两结点在同一连通分量中，而在数组中只需要将2节点的a口记录值设置成为1节点，便可实现union操作，而connected操作，只需要判断两个节点的根节点是否相同便可，代码实现如下：

通过代码可以看出快速合并算法有一个较大的缺点为快速合并算法依赖于输入整数对的随机性，当操作数量过大时，快速合并算发所产生的树的高度会逐渐增高，最终导致回溯树寻找根节点的时间增多，降低算法的运行效率。