检索
E-mail
RSS
作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2010, Vol. 36 ›› Issue (2): 61-63.doi: 10.3969/j.issn.1000-3428.2010.02.022

• 软件技术与数据库 • 上一篇    下一篇

赋权有向图的最小生成树算法

孙凌宇1，冷 明1,2，谭云兰1，郁松年2   

  1. (1. 井冈山大学计算机科学系，吉安 343009；2. 上海大学计算机工程与科学学院，上海 200072)
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2010-01-20 发布日期:2010-01-20

Minimum Spanning Tree Algorithm of Weighted Directed Graph

SUN Ling-yu1, LENG Ming1,2, TAN Yun-lan1, YU Song-nian2   

  1. (1. Computer Science Department, Jinggangshan University, Ji’an 343009;2. School of Computer Engineering and Science, Shanghai University, Shanghai 200072)
  • Received:1900-01-01 Revised:1900-01-01 Online:2010-01-20 Published:2010-01-20

PDF

4493

被引次数

27 | 3

摘要： 针对赋权有向图最小生成树问题存在可行解的情况，根据树节点入度最大值为1的性质，提出赋权有向图最小生成树性质。采用反证法，调整生成树根节点到弧头的路径来证明赋权有向图MST性质的正确性。基于赋权有向图MST性质，给出改进的Prim和Kruskal算法及其时间复杂度分析。实验给出构造某赋权有向图实例最小生成树的具体步骤，表明这2种算法能正确有效地构造赋权有向图最小生成树。

关键词: 赋权有向图, 最小生成树, Prim算法, Kruskal算法

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.

Key words: weighted directed graph, Minimum Spanning Tree(MST), Prim algorithm, Kruskal algorithm

中图分类号: