季 飛，李建林

（南京信息職業(yè)技術(shù)學(xué)院，江蘇南京 210023）

一、引言

最小生成樹(shù)（MST）是圖論的一個(gè)經(jīng)典問(wèn)題，普遍存在于諸多領(lǐng)域中。對(duì)于MST算法，有兩套獨(dú)立的支撐理論。其一是：對(duì)于連通圖上的任一割，e是其中權(quán)值最小的邊，則e屬于該圖的最小生成樹(shù)的邊集。本文稱之為割定理。其二是：對(duì)于連通圖中的任一圈，e是其中權(quán)值最大的邊，則e不屬于該圖的最小生成樹(shù)的邊集。本文稱之為圈定理。

1926年，Boru?vka首先提出最小生成樹(shù)問(wèn)題并給出相應(yīng)的算法[1]；此后，Kruskal和Prim分別于1956年和1957年提出了各自的算法[2,3]。大多數(shù)的后續(xù)研究[4-10]，或者輔助以高效的排序、散列算法，或者引入高效的數(shù)據(jù)結(jié)構(gòu)及操作，以提高算法的整體效率。這些研究依據(jù)的是割定理。1975年，管梅谷依據(jù)圈定理，提出了破圈法[11]，并證明了其正確性：最小生成樹(shù)與破圈次序無(wú)關(guān)。破圈法直觀明了，但其中缺少“尋找圈”這一關(guān)鍵步驟的深入描述，只適合人工目測(cè)，不適合程式化處理，需要進(jìn)一步完善。有關(guān)破圈法的后續(xù)研究不多，且主要表現(xiàn)為中文文獻(xiàn)。文獻(xiàn)[12]與[13]分別給出了其正確性的另外兩種證明；文獻(xiàn)[14]與[15]通過(guò)給任選的一棵生成樹(shù)添加邊，來(lái)尋找圈進(jìn)而破圈，分別給出了兩種實(shí)現(xiàn)方法，效率均為O(|E|×|V|)，不太理想。

本文基于分治理念，設(shè)計(jì)出一種新的破圈算法，證明了割定理與圈定理的等價(jià)性，并依據(jù)圈定理證明了算法的正確性。新算法依據(jù)邊的權(quán)值中位數(shù)，將圖中的邊一分為二，將原問(wèn)題分解、演變?yōu)橐粋€(gè)或多個(gè)規(guī)模較小的子問(wèn)題，降低了邊與邊之間的耦合；在技術(shù)細(xì)節(jié)上，不是刻意地去尋找圖中的圈，而是通過(guò)邊合并操作來(lái)尋找圈。該算法的實(shí)現(xiàn)難度不大，在極端情況下的效率為O(|E|×log2|V|)，在一般情況下的效率為O(|E|×log2(log2|V|))。

二、相關(guān)概念

首先，我們給出一些定義和必要的說(shuō)明，以方便后續(xù)內(nèi)容的陳述。

定義1（無(wú)向權(quán)圖）：無(wú)向圖定義為G=（V,E）。其中：V={v1,v2,…,vn}是有限的非空集合，v∈V代表圖中的一個(gè)結(jié)點(diǎn)；E={e1,e2,…,em}是無(wú)序偶對(duì)的集合，e∈E代表vi∈V、vj∈V兩結(jié)點(diǎn)之間的邊，記為e=(vi,vj)=(vj,vi)。對(duì)于e∈E，若存在權(quán)值w(e)，則稱G為無(wú)向權(quán)圖。

定義2（最小生成樹(shù)）：設(shè)G=(V,E)，T=（V,ET）是G的一個(gè)子圖。若T連通且不存在回路，則T是G的一棵生成樹(shù)；在所有生成樹(shù)中，邊之權(quán)值總和最小者，稱為G的一棵最小生成樹(shù)。

定義3（中位數(shù)）：對(duì)于一組數(shù)據(jù)，若將其按大小順序排列，位于中間位置的那個(gè)元素，叫做這組數(shù)據(jù)的中位數(shù)。

說(shuō)明：我們?cè)谒惴ㄖ兄皇褂谩皽?zhǔn)中位數(shù)”，它是“中位數(shù)的中位數(shù)”[16]，在最壞情況下，將規(guī)模為n的一組數(shù)據(jù)，分為規(guī)模介于（3n/ 10 -6）和（7n/ 10 +6）之間的兩組，相應(yīng)算法的效率為O（n）。本文其他地方提及的中位數(shù)，即指“準(zhǔn)中位數(shù)”。

定義4（邊合并）：設(shè)G=（V,E），Gsub=（Vsub,Esub）是G的一個(gè)連通子圖。邊合并是這樣的一組操作：將圖G中所有鄰接到結(jié)點(diǎn)vsub∈Vsub的、但不屬于Esub的邊，全部合并鄰接到子圖Gsub中的某一個(gè)結(jié)點(diǎn)v上；對(duì)于結(jié)點(diǎn)v上可能出現(xiàn)的“平行邊組”，刪除組中權(quán)值較大的邊，每組只保留一條權(quán)值最小的邊。

圖1是邊合并示例圖。其中，Vsub={a,c,v,d}，Esub={(a,c),(c,v),(v,d),(d,a),(d,c)}；以實(shí)線表示Esub中的邊，以虛線表示鄰接到結(jié)點(diǎn)vsub∈Vsub的但不屬于Esub的邊；將虛線邊全都合并鄰接到Gsub中的一個(gè)結(jié)點(diǎn)v后，結(jié)點(diǎn)v上有兩組平行邊，分別保留權(quán)值17、11的邊，刪除權(quán)值18、16的邊。從該示例可以看出，若實(shí)線邊的權(quán)值小于虛線邊的權(quán)值，則邊合并操作具有破圈功能。

三、算法介紹

算法基于分治理念，依據(jù)邊的權(quán)值中位數(shù)，將圖中的邊分為規(guī)模大致相同、權(quán)值一大一小的兩個(gè)部分。若從圖中移除所有大權(quán)值的邊，則圖可能不再連通，分解為多個(gè)連通子圖。顯然，這些子圖中的邊，小于那些被移除的邊。依據(jù)圈定理，在這些子圖上執(zhí)行前述的邊合并操作，即可實(shí)現(xiàn)破圈功能。隨著遞歸的深入，不在最小生成樹(shù)中的邊不斷被刪除，最終余下的邊構(gòu)成圖的最小生成樹(shù)。

（一）算法步驟

1.準(zhǔn)備一個(gè)空集合F、空棧s，壓原始圖入棧s。

2.若棧s不為空，反復(fù)執(zhí)行下述步驟：

（1）從s中彈出一個(gè)圖，記為G=（V,E）；

（2）若G為一棵樹(shù)，則將e∈E加入集合F，轉(zhuǎn)至步驟2；

（3）計(jì)算所有邊的權(quán)值中位數(shù)，記為m；

（4）依據(jù)m構(gòu)造集合Emin和Emax，使得Emin∪Emax＝E，Emin∩Emax＝φ，且w（e∈Emin）＜w（e∈Emax）；

（5）從G中移除Emax中的邊，得到n≥1個(gè)連通的、但兩兩不連通的子圖G1,G2,...,Gn；

（6）對(duì)于每個(gè)1≤i≤n：

（a）若Emax中的邊，鄰接了Gi中的兩個(gè)結(jié)點(diǎn)，則從Emax中刪除；

（b）在Gi上執(zhí)行前文定義的邊合并操作，合并時(shí)所選擇的結(jié)點(diǎn)記為vi；

（c）壓Gi入棧s；

（7）此時(shí)若Emax不為空，則其中的邊，鄰接到各個(gè)vi，構(gòu)成圖Gleft，壓Gleft入棧s。

3.返回集合F，得到原始圖的一棵最小生成樹(shù)。

說(shuō)明：步驟（5）中的“移除”，所操作的邊并未被舍棄，仍然保留在集合Emax中；而步驟（a）中的“刪除”，以及步驟（b）中執(zhí)行邊合并操作時(shí)的“刪除”，所操作的邊則被舍棄，不再保留在集合Emax中。

（二）理論證明

定理1：割定理與圈定理等價(jià)。

證明：割定理的逆否命題為：若邊e不屬于連通圖的最小生成樹(shù)的邊集，則對(duì)于圖上的任一割，e都不是其上權(quán)值最小的邊。圈定理的逆否命題為：若邊e屬于連通圖的最小生成樹(shù)的邊集，則對(duì)于圖中的任一圈，e都不是其中權(quán)值最大的邊。

首先，我們由圈定理，證明割定理的逆否命題。設(shè)圖中有一個(gè)圈，由結(jié)點(diǎn)v1,v2,...,vn,v1依次兩兩鄰接而成，邊ei=（vi1,vi2）是圈中的最大邊，不屬于最小生成樹(shù)的邊集。對(duì)于圖上任一割C=（V1,V2），若vi1∈V1，vi2∈V2，即ei跨接于割C，那么，圈中一定另有一條不同的邊ej=（vj1,vj2）跨接于割C。由于ei為圈中的最大邊，所以ei＞ej不是割C上的權(quán)值最小的邊。若邊ei不跨接于割C，則顯然不是其上權(quán)值最小的邊。

其次，我們由割定理，證明圈定理的逆否命題。設(shè)圖中有一個(gè)割，邊e1,...,en跨接于該割，邊ei是其中的最小邊，屬于最小生成樹(shù)的邊集。對(duì)于圖中任一圈Q，若ei是該圈中的邊，那么，割上一定另有一條不同的邊ej存在于圈中。由于ei為割上的最小邊，所以ei＜ej不是圈Q中的權(quán)值最大的邊。若邊ei不是圈Q中的邊，則顯然不是其中的權(quán)值最大的邊。

因?yàn)槟娣衩}與原命題等價(jià)，所以割定理與圈定理等價(jià)。

斷言：設(shè)結(jié)點(diǎn)v是連通圖G=（V,E）中的一個(gè)割點(diǎn)，現(xiàn)于v處將圖G分割為兩個(gè)連通圖G1=（V1,E1）和G2=（V2,E2），這里V1∪V2＝V、V1∩V2＝{v}且E1∪E2＝E、E1∩E2＝φ；再設(shè)T1、T2分別為G1、G2的最小生成樹(shù)。則合并T1、T2即可得到G的最小生成樹(shù)T。

定理2：設(shè)在連通圖G上執(zhí)行算法步驟（3）～（7），T1,T2,...,Tn,Tleft分別是圖G1,G2,...,Gn,Gleft的最小生成樹(shù)。則合并T1,T2,...,Tn,Tleft即得到圖G的最小生成樹(shù)T。

證明：至步驟（7），v1,v2,...,vn均演變?yōu)楦铧c(diǎn)，Gleft通過(guò)這些割點(diǎn)連通到G1,G2,...,Gn，構(gòu)成一個(gè)連通圖Gend，據(jù)上述斷言，合并T1,T2,...,Tn,Tleft即得Gend之最小生成樹(shù)Tend。步驟（6）將圖G演變?yōu)閳DGend，步驟（3）～（5）使得在步驟（6）中：刪除的邊是圈中權(quán)值最大者，最小生成樹(shù)T中的邊留存于Gend中；未刪除的邊，若在G內(nèi)是圈中權(quán)值最大者則在Gend內(nèi)仍然是?？梢?jiàn)，步驟（6）維持最小生成樹(shù)不變，Tend≡T。

（三）效率分析

我們選用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)。在一次遞歸過(guò)程中，與效率相關(guān)的主要步驟是（3）～（6）。顯然，步驟（3）～（5）的效率是O（|E|）。至于步驟（6），著眼每個(gè)Gi，遍歷其中的結(jié)點(diǎn)，以檢查其上先前是否連結(jié)有Emax中的邊，并且將集合Emax實(shí)現(xiàn)為雙向鏈表。這樣，步驟（6）子循環(huán)執(zhí)行的效率也是O（|E|）。因此，一次遞歸的效率為O（|E|）。

1.最壞情況

經(jīng)分析，算法的最壞情況是指，在每次遞歸過(guò)程中，步驟（5）執(zhí)行完成之后，圖G同時(shí)展示出如下兩個(gè)特征：其中一半的結(jié)點(diǎn)，因其上連結(jié)的邊均屬于集合Emax，而被全部移除，一個(gè)結(jié)點(diǎn)即構(gòu)成一個(gè)子圖；而余下的另一半結(jié)點(diǎn)，則通過(guò)集合Emin中的邊，連通成一體，僅僅構(gòu)成一個(gè)子圖，記為Gmin=（Vmin,Emin）。步驟（a）或（b）中沒(méi)有邊被刪除，集合Emax中的所有邊均保留在Gleft中，進(jìn)入了下層遞歸。

這樣，最壞情況下的每次遞歸，將G＝（V,E）分解演變?yōu)镚min＝（Vmin,Emin）和Gleft＝（Vleft,Emax）兩個(gè)連通圖。這里，Vmin∪Vleft＝V，Vmin∩Vleft＝{v}（v是集合Vmin中任選的一個(gè)結(jié)點(diǎn)）。因此，遞歸樹(shù)為一棵滿二叉樹(shù)，深度為log2|V|，對(duì)于其中的任一層，邊的總輸入量保持為|E|不變。綜上所述，算法在最壞情況下的效率為：

2.一般情況

一般情況下，集合Emin中的邊，均勻地分布連結(jié)在圖G的各個(gè)結(jié)點(diǎn)上，因而執(zhí)行完步驟（5）之后，幾乎沒(méi)有結(jié)點(diǎn)的度為零。這樣，步驟（5）完成后，若步驟（a）或（b）中沒(méi)有邊被刪除，則得到的子圖數(shù)量n＞|V|1/2，亦即Gleft中的結(jié)點(diǎn)數(shù)大于|V|1/2。因?yàn)椋粋€(gè)圖中邊的數(shù)量不可能超過(guò)相應(yīng)的完全圖。

若n≈|V|1/2，則Gleft近似為完全圖，算法的效率將趨于線性。為簡(jiǎn)潔起見(jiàn)，我們?nèi)∽訄D的數(shù)量n=|V|1/2，且各個(gè)子圖的規(guī)模相同，并假設(shè)步驟（a）或（b）中沒(méi)有邊被刪除。再設(shè)遞歸樹(shù)的深度為h，則有|V|1/2h=2，進(jìn)而有h=log2（log2|V|）。因此，算法在一般情況下的效率可以估算為：

四、實(shí)驗(yàn)驗(yàn)證

最后，通過(guò)實(shí)驗(yàn)，參照Kruskal和Prim兩個(gè)算法驗(yàn)證本文的新算法。實(shí)驗(yàn)平臺(tái)的OS是Windows 7、CPU是Intel（R）Core（TM）i3-2330M 2.20GHz，編程語(yǔ)言為JavaSE-1.8，開(kāi)發(fā)工具是Eclipse Mars.2 Release(4.5.2)。

（一）輸入圖生成算法

實(shí)驗(yàn)中輸入的圖均為隨機(jī)生成，算法如下：

1.確定圖G中結(jié)點(diǎn)的數(shù)量n、邊的數(shù)量m；

2.初始化圖G為一棵樹(shù)，使得其中包含n個(gè)結(jié)點(diǎn)v1,v2,...,vn和n-1條邊e1,e2,...,en-1。具體如下：

（1）將結(jié)點(diǎn)v1加入圖G中

（2）for（i=2；i＜=n；i++）{

3.將其余的邊添加到圖G中。具體如下：

4.返回圖G。

下面，我們以隨機(jī)生成的圖作為輸入，驗(yàn)證本文之算法的有效性和高效性。下文及表格中的V、E、Sw、C分別表示結(jié)點(diǎn)數(shù)、邊數(shù)、最小生成樹(shù)的邊權(quán)之和、基本操作次數(shù)，C：E則表示基本操作次數(shù)與邊數(shù)的比值，E：V則表示邊數(shù)與結(jié)點(diǎn)數(shù)的比值。

（二）有效性驗(yàn)證

這里，在一組輸入的各個(gè)圖上，分別執(zhí)行Kruskal、Prim和本文的算法，實(shí)驗(yàn)數(shù)據(jù)記錄于表1中?？梢钥闯?，對(duì)于同一個(gè)圖，三個(gè)算法輸出相同的Sw。依據(jù)Sw的唯一性，可見(jiàn)本文的算法有效。

表1.不同算法輸出的不同輸入圖G 的Sw

表2.(C：E)隨E 變化實(shí)驗(yàn)記錄（V=1000 保持不變）

表3.(C：E)隨V 變化實(shí)驗(yàn)記錄（E=64000 保持不變）

（三）高效性驗(yàn)證

這里，使用了三組輸入：第一組，各圖的結(jié)點(diǎn)數(shù)保持不變，數(shù)據(jù)記錄于表2中；第二組，各圖的邊數(shù)保持不變，數(shù)據(jù)記錄于表3中；第三組，各圖的邊數(shù)與結(jié)點(diǎn)數(shù)的比值保持不變，數(shù)據(jù)記錄于表4中。對(duì)于Kruskal算法，實(shí)驗(yàn)選用基于中位數(shù)的快速排序，記錄的是排序操作開(kāi)銷，未計(jì)入不相交集合上的操作開(kāi)銷；對(duì)于Prim算法，實(shí)驗(yàn)引入最小二叉堆，以擇取割上的最小邊，記錄的是堆上的操作開(kāi)銷。

表4.(C：E)隨E 變化實(shí)驗(yàn)記錄（E：V=2：1 保持不變）

三組實(shí)驗(yàn)數(shù)據(jù)顯示，相對(duì)于兩個(gè)經(jīng)典算法，本文算法的C：E較為穩(wěn)定，幾乎呈現(xiàn)常量特征?？梢?jiàn)，一般情況下，本文算法的效率較高。

五、結(jié)束語(yǔ)

本文基于分治法理念，設(shè)計(jì)出一種新的最小生成樹(shù)算法，并給出了理論證明及實(shí)驗(yàn)結(jié)果。算法基于邊權(quán)中位數(shù)，將圖中的邊一分為二，以降低邊與邊之間的耦合。在遞歸過(guò)程中，不是刻意地尋找圈，而是使用邊合并操作，以刪除不在最小生成樹(shù)中的邊。分析表明，新算法在最壞情況下的效率為O（|E|×log2|V|），與經(jīng)典算法持平。然而，最壞情況是一種很少出現(xiàn)的極端情況：一半結(jié)點(diǎn)構(gòu)成一個(gè)連通圖，通過(guò)小權(quán)值的邊連通；另一半結(jié)點(diǎn)也構(gòu)成另一個(gè)連通圖，通過(guò)大權(quán)值的邊連通，兩圖之間只有極少量的大權(quán)值邊相連。若各個(gè)結(jié)點(diǎn)鄰接小權(quán)值邊的機(jī)會(huì)均等，則新算法的效率為O（|E|×log2（log2|V|）），遠(yuǎn)高于經(jīng)典算法，最后的實(shí)驗(yàn)驗(yàn)證了這一點(diǎn)。算法中權(quán)值中位數(shù)m的作用，類似于快速排序中的pivot，將邊按權(quán)值大小分為兩組。算法平均效率較高的另一個(gè)原因在于：部分大權(quán)值組中的邊，在處理小權(quán)值組中的邊時(shí)，被刪除了。

另外，算法中可以方便地引入并行計(jì)算，由遞歸樹(shù)同一層的各個(gè)節(jié)點(diǎn)，并發(fā)地進(jìn)入下一層對(duì)應(yīng)的子節(jié)點(diǎn)。最壞情況下，步驟（a）或（b）中沒(méi)有邊被刪除，遞歸樹(shù)各層的輸入量都為|E|，但自上而下，操作的時(shí)間開(kāi)銷則依次為|E|，|E|/ 2，|E|/ 4，...因此，若引入并行計(jì)算，算法的執(zhí)行時(shí)間為：Tconcurrent＝O（|E|）。