| 寻找最小生成树的度优先算法 |
| |
| 引用本文： | 武继刚. 寻找最小生成树的度优先算法[J]. 烟台大学学报(自然科学与工程版), 1994, 0(1): 32-35 |
| |
| 作者姓名： | 武继刚 |
| |
| 作者单位： | 烟台大学 |
| |
| 摘 要： | ![]()
利用Ｋｒｕｓｋａｌ和Ｐｒｉｍ算法的优点，从图的每个顶点的度数入手，采取删除某些无用边的思想方法，给出了一个寻找最小生成树的算法。算法的最坏复杂度为Ｏ（ｍ－ｎ）ｌｏｇｍ），平均复杂度为Ｏ（（ｍ－ｎ）ｌｏｇｎ），就复杂度的常数因子而言，均优于Ｋｒｕｓｋａｌ算法与ｋｉｍ算法，其中ｍ为图的边数，ｎ为图的顶点数。
|
| 关 键 词： | 最小生成树 度优先 算法 |
Degree First Algorithm for Finding Minimum Spanning Trees |
| |
| Wu Jigang. Degree First Algorithm for Finding Minimum Spanning Trees[J]. Journal of Yantai University(Natural Science and Engineering edirion), 1994, 0(1): 32-35 |
| |
| Authors: | Wu Jigang |
| |
| Affiliation: | Yantai University |
| |
| Abstract: | ![]()
|
| |
| Keywords: | Connected graph. Minimum spanning tree. Degree first.Algorithm. Complexity. |
| 本文献已被 CNKI 维普 等数据库收录！ |
