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

摘要：

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

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

所属期刊栏目：36

分类号：TP391(计算技术、计算机技术)

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

在线出版日期：2010-03-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：61-63,66