|
|||||
|
|
| 赋权有向图的最小生成树算法 | |
| 引用本文： | 孙凌宇,冷明,谭云兰,郁松年.赋权有向图的最小生成树算法[J].计算机工程,2010,36(2):61-63. |
| 作者姓名： | 孙凌宇 冷明 谭云兰 郁松年 |
| 作者单位： | 1. 井冈山大学计算机科学系,吉安,343009 2. 井冈山大学计算机科学系,吉安,343009;上海大学计算机工程与科学学院,上海,200072 3. 上海大学计算机工程与科学学院,上海,200072 |
| 基金项目： | 上海市教育委员会科研创新基金资助项目(08YZ13);;江西省教育厅科学技术研究基金资助项目(GJJ09590) |
| 摘 要： | 针对赋权有向图最小生成树问题存在可行解的情况，根据树节点入度最大值为1的性质，提出赋权有向图最小生成树性质。采用反证法，调整生成树根节点到弧头的路径来证明赋权有向图MST性质的正确性。基于赋权有向图MST性质，给出改进的Prim和Kruskal算法及其时间复杂度分析。实验给出构造某赋权有向图实例最小生成树的具体步骤，表明这2种算法能正确有效地构造赋权有向图最小生成树。 |
| 关 键 词： | 赋权有向图 最小生成树 Prim算法 Kruskal算法 |
| 修稿时间： | |
Minimum Spanning Tree Algorithm of Weighted Directed Graph |
|
| SUN Ling-yu,LENG Ming,TAN Yun-lan,YU Song-nian.Minimum Spanning Tree Algorithm of Weighted Directed Graph[J].Computer Engineering,2010,36(2):61-63. | |
| Authors: | SUN Ling-yu LENG Ming TAN Yun-lan YU Song-nian |
| Affiliation: | 1. Computer Science Department/a>;Jinggangshan University/a>;Ji'an 343009/a>;2. School of Computer Engineering and Science/a>;Shanghai University/a>;Shanghai 200072 |
| Abstract: | According to the existence of feasible solutions, this paper proposes the Minimum Spanning Tree(MST) characteristic of weighted directed graph based on the criteria that the maximum in-degree of tree node is less than or equal to one. It proves the correctness of MST characteristic with the reduction to absurdity, by adjusting the path from root of spanning tree to sink of directed edge. Based on the MST characteristic, it also proposes the improved Prim algorithm, the improved Kruskal algorithm and its time complexity analysis. It gives the MST construction of the specified weighted directed graph. Experiment and analysis show that the improved Prim and Kruskal algorithm can find the MST of weighted directed graph correctly and effectively. |
| Keywords: | weighted directed graph Minimum Spanning Tree(MST) Prim algorithm Kruskal algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ | |
| 点击此处可从《计算机工程》浏览原始摘要信息 | |
| 点击此处可从《计算机工程》下载全文 | |