基于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操作，只需要判断两个节点的根节点是否相同便可，代码实现如下：
通过代码可以看出快速合并算法有一个较大的缺点为快速合并算法依赖于输入整数对的随机性，当操作数量过大时，快速合并算发所产生的树的高度会逐渐增高，最终导致回溯树寻找根节点的时间增多，降低算法的运行效率。 2.3加权快速合并算法介绍
加权快速合并算法是在快速合并算法的基础上，对快速合并算法的优化，优化方法就是多添加一个数组，用来记录每一棵树的大小，当两个节点合并时程序只需要判断两个节点所在树的大小，将较小的树合并到较大的树上，此操作可以有效地减小生成树的高度，这样就可以解决快速合并算法中因输入整数对的随机性导致树的高度太高，从而降低算法的运行效率的问题。实现代码如下：
3算法的效率分析与对比
3.1算法时间复杂度分析
首先，对三种算法进行算法复杂度分析，然后用过实践，来测试快速查找算法的运算时间。
3.1.1快速查找算法时间的复杂度分析
为方便分析，利用通过计算每个函数访问数组的次数的方法作为参照，来判断算法的复杂程度。union方法所访问数组的次数在（N+3）到（2N+1）之间，假设对象数量为N，当通过若干连接最终只剩下一个连通分量时，至少需要调用N-1次union方法，而union方法访问数组的次数至少为（N+3）次，所以快速查找算法需要至少访问数组（N 1），（N+3）～N2次，因此，可以推算出快速查找算法的时间复杂度为0（n2）。
3.1.2快速合并算法的时间复杂度分析
针对快速合并算法的时间复杂度分析，因为快速合并算法在操作数组时，只需要修改数组中的一个数值便可以实现union操作，所以快速合并算法看起来相比快速查找算法要更快一点，但要准确的分析快速合并算法的时间复杂度要相对困难，因为快速合并算法有一个较大的缺点为快速合并算法依赖于输入整数对的情况，在有些情况树的高度可能太高，需要回溯树的时间大大增加，导致算法的运行效率受到影响，因此快速合并算法的时间复杂度往往取决于合并之后树的高度。
3.1.3加权快速合并算法复杂度分析
加权快速合并算法的执行效率要比快速合并算法的效率要高得多，这是因为合并算法的执行效率与树的高度成正比，树的高度越高，算法的执行效率就越低，在最坏的情况下快速合并算法所产生的树的高度最大为N，而加权快速合并算法所产生的树的高度最大为logN，可以通过简单的数学分析，分析出此结果。
首先，通过代码发现，每次执行连接操作，只有当两棵树的大小相同时，合并之后树的高度会增加1，而当两棵树的大小不相同时，小树合并到大树并不会使得树的高度发生变化，因此最坏的情况是每当执行连接操作时，两棵树的大小相同，这样在执行完所有的连接操作之后所产生树的高度才能达到最大。
假设总共有N个独立的节点，每次执行合并操作时两棵树的大小相同，通过计算合并操作执行的次数来确定出树的高度，每执行一次操作，树的大小变为原来的两倍，设总共执行了x次，则有2x=N，可以计算出总共执行的次数为x=logN，得到的树的最大高度为logN，而相对于高度N所寻找根节点的时间大大减小，使得算法的执行效率变高。
3.2实际运行时间测试
通过设计一个性能测试用例，来对三种算法的实际运行时间进行测试：
利用此代码来对快速查找算法、快速合并算法以及加权快速合并算法的实际运行时间进行测试，首先将对象的数量统一为100000，改变执行操作的数量，针对不同数量的操作对算法的运行时间进行统计，选取5000，7000，10000，50000，70000，100000条连接操作和查询连接操作，通過程序的运行结果，统计出三种算法的运行时间，结果见表2。
从表2中可以看出，随着执行的操作数量在不断地上升，快速合并算法和快速查找算法在操作数量较小时往往运行时间较快，而当操作数达到100000时，快速合并算法相对于快速查找算法要慢了许多，这是因为操作数量的上升会导致树的高度在不断地增加，因此回溯树寻找根节点的时间也在不断地上升，最终导致了快速合并算法的运行时间变慢，而加权快速合并算法的运行效率相对于前两种算法的运行效率要高许多，尤其是在操作数量达到100000时尤为明显。
画出三组数据的拟合图像，见图5，通过图5可以看出前两种算法的运行时间在不断地增长，且增长趋势随着数据量的扩大而不断地增长，而加权快速合并算法的运行效率相对于前两种的算法的运行效率要高许多，且在随着操作数量的不断增大，加权快速合并算法也能够有效和快速的处理和运行。
接下来进一步扩大操作数量，将对象数量扩大到1000000、10000000、100000000，将操作数量也扩大到对应的数量，来测试三种算法的运行时间，通过实验发现，快速查找算法和快速合并算法因为操作数量较大的缘故都无法有效的给出程序的运行时间，因此只能够统计出加权快速合并算法的运行时间，见表3。
通过表3可以看出加权快速合并算法可以有效地解决数量较大的动态连通性问题，但当操作数量达到亿级以上时，也会略显吃力，而快速查找算法和快速合并算法在处理数量较大的动态连通性就会相对较慢甚至无法处理。
4结束语
通过对三种算法的介绍和实际测试，可以总结出在解决动态连通性问题时，快速查找算法和快速合并算法能够有效地解决数量较小的动态连通性问题，而当数量较大时，因为快速合并算法所生成的树的高度太高导致运行效率降低，当操作数量进一步扩大，快速合并算法和快速查找算法就无法解决此类问题，而第三种算法，加权快速合并算法是在快速合并算法的基础上通过将小树连接到大树的操作，减小树的高度，从而提高算法的执行效率，而在面对大数量的动态连通性问题时，也能够有效的解决，但操作数量达到亿级时，也会略显吃力。也可以通过路径压缩的方法对算法继续做出优化，在每次回溯树时，将每个节点的父节点连接到根节点上，从而继续降低树的高度，优化算法的执行时间，提高算法的运行效率。
转载注明来源:https://www.xzbu.com/8/view-15143732.htm
