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