| 破圈法构造最小生成树算法探讨 |
| |
| 引用本文： | 龙亚.破圈法构造最小生成树算法探讨[J].毕节学院学报,2007,25(4):108-111. |
| |
| 作者姓名： | 龙亚 |
| |
| 作者单位： | 毕节学院计算机科学系,贵州,毕节,551700 |
| |
| 摘 要： | 求解最小生成树是《数据结构》课程教学中的一个学生重点学习的图论问题,但是目前的教材中普遍讲解Prim算法和Kruskal算法,这两个算法的基本思想均是基于避圈法。而从相反的角度求解最小生成树:破圈法构造最小生成树算法,虽然该算法的时间复杂度较高(O(n3)),但从教学的角度来看,有利于训练学生深刻理解和掌握最小生成树算法。
|
| 关 键 词： | 最小生成树 破圈法 邻接矩阵 |
| 文章编号： | 1673-7059（2007）04-0108-04 |
| 修稿时间： | 2006-03-04 |
Research of Algorithm of Constructing Minimum Spanning Tree by Destroying Loop Rule |
| |
| LONG Ya.Research of Algorithm of Constructing Minimum Spanning Tree by Destroying Loop Rule[J].Journal of Bijie University,2007,25(4):108-111. |
| |
| Authors: | LONG Ya |
| |
| Institution: | Dept. of Computer Science, Bijie University, Bijie, Guizhou 551700, China |
| |
| Abstract: | To obtain the minimum spanning tree is the 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. |
| |
| Keywords: | Minimum Spanning Tree Destroying Loop Rule Adjoint Matrix |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
