一种基于递归堆调整方法的最小生成树求解算法

摘要：

Sollin算法是一种非常适合于并行计算的求解最小生成树方法，但其较高时间复杂度抵消了并行计算带来的好处。本文提出了一种递归的堆调整实现方法以及堆合并原则，解决了Sollin算法在子树合并时快速找到连接两棵相邻子树的最短的边的问题，降低最小生成树求解的时间复杂度。理论分析表明，该改进方法有效地将Sollin算法的时间复杂度由O （n2log2n）降低到了O （elog2n）。同时，根据边权重的分布情况不同，该算法并非必须遍历所有的边才能得到MST，实际时间复杂度将优于O （elog2n），最优可达O(n(log2n)2)。

关键词：最小生成树、Sollin算法、堆调整、递归方法、子树合并

分类号：TP18(自动化基础理论)

资助基金：国家自然科学基金项目编号50875087。

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

页数：共3页

页码：135-137