文献类型：期刊文章

作　　者：孙凌宇[1] 冷明[1,2] 谭云兰[1] 郁松年[2]

机构地区：[1]井冈山大学计算机科学系,吉安343009 [2]上海大学计算机工程与科学学院,上海200072

出　　处：《计算机工程》

基　　金：上海市教育委员会科研创新基金资助项目(08YZ13);江西省教育厅科学技术研究基金资助项目(GJJ09590)

年　　份：2010

卷　　号：36

期　　号：2

起止页码：61-63

语　　种：中文

收录情况：AJ、BDHX、BDHX2008、CAS、CSA、CSA-PROQEUST、CSCD、CSCD2011_2012、IC、INSPEC、JST、RCCSE、SCOPUS、UPD、ZGKJHX、核心刊

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

关 键 词：赋权有向图  最小生成树 PRIM算法 KRUSKAL算法

分 类 号：TP391]