基于中位数的二分破圈法

发布时间：2022-08-23 23:39

　　这是一种最小生成树算法,基于分治理念,采用破圈法。依据权值中位数,将图中的边一分为二,以降低边与边之间的耦合。破圈功能通过边合并操作实现,一次递归删除一些边,使得分解后子问题的总规模不大于原问题的规模。该算法效率较高,最坏情况下为O（|E|×log2|V|）,一般情况下为O（|E|×log2（log2|V|））。 

【文章页数】：5 页

【文章目录】：
一、引言
二、相关概念
三、算法介绍
    （一）算法步骤
    （二）理论证明
    （三）效率分析
        1. 最坏情况
        2. 一般情况
四、实验验证
    （一）输入图生成算法
    （二）有效性验证
    （三）高效性验证
五、结束语


【参考文献】：
期刊论文
[1]最小树的一种新的生成方法[J]. 洪燕君.  石河子大学学报(自然科学版). 2013(02)
[2]一种求解最小生成树问题的算法[J]. 孙小军,刘三阳,王志强.  计算机工程. 2011(23)
[3]求图的最优树破圈法算法的一个实现[J]. 魏丽侠,孔毅.  沈阳工业大学学报. 1998(S1)
[4]破圈法的另一种证明[J]. 杨显中.  四川师范大学学报(自然科学版). 1995(04)
[5]最小生成树的算法[J]. 徐绪松,李万学.  计算机学报. 1993(11)
[6]“破圈法”求最优树的一个简单证明[J]. 陈正一.  哈尔滨船舶工程学院学报. 1990(02)
[7]求最小树的破圈法[J]. 管梅谷.  数学的实践与认识. 1975(04)



本文编号：3678699