這是一種最小生成樹算法,基于分治理念,采用破圈法。依據(jù)權(quán)值中位數(shù),將圖中的邊一分為二,以降低邊與邊之間的耦合。破圈功能通過邊合并操作實現(xiàn),一次遞歸刪除一些邊,使得分解后子問題的總規(guī)模不大于原問題的規(guī)模。該算法效率較高,最壞情況下為O（|E|×log2|V|）,一般情況下為O（|E|×log2（log2|V|））。 

【文章頁數(shù)】：5 頁

【文章目錄】：
一、引言
二、相關(guān)概念
三、算法介紹
    （一）算法步驟
    （二）理論證明
    （三）效率分析
        1. 最壞情況
        2. 一般情況
四、實驗驗證
    （一）輸入圖生成算法
    （二）有效性驗證
    （三）高效性驗證
五、結(jié)束語


【參考文獻】：
期刊論文
[1]最小樹的一種新的生成方法[J]. 洪燕君.  石河子大學(xué)學(xué)報(自然科學(xué)版). 2013(02)
[2]一種求解最小生成樹問題的算法[J]. 孫小軍,劉三陽,王志強.  計算機工程. 2011(23)
[3]求圖的最優(yōu)樹破圈法算法的一個實現(xiàn)[J]. 魏麗俠,孔毅.  沈陽工業(yè)大學(xué)學(xué)報. 1998(S1)
[4]破圈法的另一種證明[J]. 楊顯中.  四川師范大學(xué)學(xué)報(自然科學(xué)版). 1995(04)
[5]最小生成樹的算法[J]. 徐緒松,李萬學(xué).  計算機學(xué)報. 1993(11)
[6]“破圈法”求最優(yōu)樹的一個簡單證明[J]. 陳正一.  哈爾濱船舶工程學(xué)院學(xué)報. 1990(02)
[7]求最小樹的破圈法[J]. 管梅谷.  數(shù)學(xué)的實踐與認識. 1975(04)



本文編號：3678699