摘要
最小生成树(MST)问题在很多现实应用中发挥着重要的作用,Kruskal算法是求最小生成树的常用算法之一。由于该算法需要反复进行回路检测,故而在实际应用中更适合在图上直接作业而不适于直接使用计算机进行求解。讨论了算法的实现步骤,着重设计并分析了相关回路检测算法,证明了他们的正确性。通过程序对算法的复杂度进行分析,并对其有效性进行了测试,找出了这些回路检测算法的优缺点及适用范围,对于使用Kruskal算法进行计算机求解的过程有一定的指导意义。
The minimum spanning tree （MST） exerts a crucial role on a great deal of real-world applications. Kruskal algo- rithm is one of the commonly used algorithms to calculate MST. However, because of the repeating loop detections of Kruskal al- gorithm, in the practical application, the algorithm is more suitable to being employed directly in diagrams but not to using com- puter to reach the solutions. The implementation steps of the algorithm are discussed, and the related loop-detection algorithms are designed and analyzed in this paper to prove the correctness of the algorithms. The advantages and the disadvantages of the loop-detection algorithms, and range of application of each algorithm were found by applying computer programs to analyze the complexity of each algorithm and by testing their effectiveness.
出处
《现代电子技术》
2013年第6期22-24,共3页
Modern Electronics Technique
