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

被引：13

作者：

孙凌宇 ^{[1
]}

冷明 ^{[1
,2
]}

谭云兰 ^{[1
]}

郁松年 ^{[2
]}

机构：

[1] 井冈山大学计算机科学系

[2] 上海大学计算机工程与科学学院

来源：

计算机工程 | 2010年 / 36卷 / 02期

关键词：

赋权有向图; 最小生成树; Prim算法; Kruskal算法;

D O I：

暂无

中图分类号：

TP301.6 [算法理论];

学科分类号：

摘要：

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

引用

页码：61 / 63+66 +66

页数：4