赋权连通图最小生成树分析研究

摘要：

结合克鲁斯卡尔算法，提出通过增加辅助边集合，在应用克鲁斯卡尔算法构造赋权连通图最小生成树的过程中，同时保留权值较小的、非最小生成树的边的方法对克鲁斯卡尔算法进行补充，最终得到两个边集，一个为原来克鲁斯卡尔算法构造的最小生成树的边集，另一个为考虑工程修改变化而保留的辅助边集，两个边集互不影响。应用最小生成树解决工程问题时，若不考虑工程后续修改变化，则仅需要考虑原克鲁斯卡尔算法构造的最小生成树的边集；当需要考虑工程后续修改变化时，则需要同时考虑原克鲁斯卡尔算法构造的边集和现在提出的辅助边集，才能保证根据工程实际情况发生修改变化后构造的生成树总权值仍然能够保持最小。

关键词：赋权、最小、生成树、分析

分类号：TP311.1(计算技术、计算机技术)

资助基金：渭南师范学院科研计划项目:自动机理论在航天测控设备故障诊断专家系统中的应用研究14YKF003;渭南师范学院特色学科建设项目:数学方法在秦东经济社会发展中的应用14TSXK02

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

页数：共4页

页码：44-47