关于Kruskal算法的环路判定问题研究

摘要： 最小生成树（MST）问题在很多现实应用中发挥着重要的作用，Kruskal算法是求最小生成树的常用算法之一。由于该算法需要反复进行回路检测，故而在实际应用中更适合在图上直接作业而不适于直接使用计算机进行求解。讨论了算法的实现步骤，着重设计并分析了相关回路检测算法，证明了他们的正确性。通过程序对算法的复杂度进行分析，并对其有效性进行了测试，找出了这些回路检测算法的优缺点及适用范围，对于使用Kruskal算法进行计算机求解的过程有一定的指导意义。

关键字： 复杂度分析； 最小生成树； Kruskal算法； 回路检测算法

中图分类号： TN911?34 文献标识码： A 文章编号： 1004?373X（2013）06?0022?03

0 引 言

图是一种多对多的复杂的网状数据结构，当给图的各条边赋予具有一定实际意义的数值时，就成为赋权图（也称为网），赋权图是解决一些实际问题的非常有效的工具，而基于连通赋权图的最小生成树问题是其相关应用中非常重要的一个方面。

求最小生成树问题，就是要在连通赋权网络中，寻找最小权数的支撑树。给定网络设为的一个支撑树，令表示的权和，中权和最小的支撑树称为的最小生成树[1]。

1 实例问题

2 Kruskal算法

2.1 算法思想

3 回路判定算法

对于回路判定常用两种算法，本文称之为割边判定法和改进BFS判定法。

3.1 割边判定法

3.1.1 算法描述

对于图G，查找其度为1的顶点，如果存在则将其相关边删除，并将该顶点及其邻接点度数减1，并且继续查找度为1的顶点重复上述操作；如果不存在，则可判断出是否存在回路。这时，图G中边数大于等于1，则说明图G存在回路，反之边数为0，则说明不存在回路

3.1.2 算法分析

任意图G，如果存在回路，必存在一个子图，是一个环路。而环路中所有顶点的度[5]必然大于等于2。由此可推论，如果某顶点度为1，则该顶点必然不在环路中，那么将其删除也不会改变图中本来存在的环路，也不会影响到回路的判断。图2中，v1度为1，将其相关边删除，{v0，v2，v3，v0}的回路依然存在。同理继续删除度为1顶点相关边，直到无度为1顶点为止，该回路均不受影响。而此时剩下的边与相关顶点构成了原图G的环路子图（虚线所标出部分），而该子图中的顶点均度数大于等于2。就说明图G存在环路子图，因而判定回路存在。反之，环路子图不存在，而判定不存在回路。

3.1.3 算法实现步骤

step1 建立数组记录每个顶点的度。

step2 在数组中查找度为1的顶点，如果不存在转到step4，否则执行step3。

step3 在图中查找其邻接点，将相关边删除，并将该顶点与其邻接点度数各减1，并跳转回step2。

step4 查找度数大于等于2的顶点，如果存在说明存在回路，否则不存在回路。

3.2 改进BFS判定法

3.2.1 算法描述

假设访问起点为v1，经过改进BFS算法访问若干顶点后访问到vi，直到遍历结束，vi也只被访问过1次。这说明v1到vi之间存在惟一路径，由此可推知经访问起点到任意顶点都只存在惟一路径。又因为判定起始顶点的任意性，也就说明，任意两点之间均只存在惟一路径。故而判定不存在回路。

3.2.3 算法实现步骤

step2 访问队头顶点，将其被访问次数加1；

step3 如果该顶点被访问次数为2则说明存在回路，并且算法结束；

step4 将被访问顶点的前驱顶点外的所有邻接点进队；

step5 如果队列不为空，转到step2，否则说明不存在回路，并且算法结束。

4 算法性能分析

图存储结构采用邻接矩阵法，使用JAVA实现，假定判定对象图G顶点数为n。

4.1时间复杂度分析

4.1.1 割边判定法

4.1.2 改进BFS判定法

4.2 有效性分析

5 结 语

从时间复杂度上来看改进BFS判定法时间复杂度较小，但是该算法在进行判定之前需要判定对象必须为连通图，否则就可能出现判定错误。而割边判定法虽时间复杂度较大，但是对判定对象没有特殊要求。讨论Kruskal算法的推演过程可知，在最小生成树的创建过程中，新边加入不一定能构成连通图，所以割边判定法更适合用于Kruskal算法。

参考文献

[1] 袁卫东.最小生成树的算法及其应用[J].科学技术与工程，2009（15）：51?53.

[2] 黄坤.基于Kruskal算法的最小生成树的构建[J].电脑知识与技术，2010（23）：42?45.

[3] 徐建军，沙力妮.一种新的最小生成树算法[J].电力系统保护与控制，2011（14）：107?112.

[4] 李春葆.数据结构教程[M].2版.北京：清华大学出版社，2007.

[5] 高淑玲，伦怡.判定连通图中欧拉通路（或回路）的算法[J].河北建筑工程学院学报，2002（3）：75?76.

[6] 王学军.数据结构[M].北京：人民邮电出版社，2008.