摘要： 针对赋权有向图最小生成树问题存在可行解的情况，根据树节点入度最大值为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

中图分类号: 

• TP391