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

摘要：

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

机标关键词：kruskal算法、判定问题、最小生成树、回路检测、检测算法、算法的实现、计算机求解、适用范围、复杂度、实际应用

分类号：TN911?34

在线出版日期：2013-03-28（万方平台首次上网日期，不代表论文的发表时间）

页码：22-24