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

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

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


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



本文編號(hào)：3678699