破圈法构造最小生成树算法探讨

Research of Algorithm of Constructing Minimum Spanning Tree by Destroying Loop Rule

求解最小生成树是《数据结构》课程教学中的一个学生重点学习的图论问题,但是目前的教材中普遍讲解Prim算法和Kruskal算法,这两个算法的基本思想均是基于避圈法。而从相反的角度求解最小生成树:破圈法构造最小生成树算法,虽然该算法的时间复杂度较高(O(n3)),但从教学的角度来看,有利于训练学生深刻理解和掌握最小生成树算法。

To obtain the minimum spanning tree is the Guizhou 551700, China） key point of Graph theory in the teaching of Data Structure. However, the prevailing textbooks tend to focus on the algorithms of Prim and Kruskal. These two methods are based on preventing loop rule. This paper obtans the minimum spanning tree a contrary angle, which derive the minimum spanning tree algorithm. Though this method shows a high time complexity（O（n3））, it can benefit students＇ understanding and help them master the minimum spanning tree in the actual training practice.