基于降階的最小生成樹快速算法

摘 要:在分析最小生成樹問題數學性質的基礎上，給出了一種基于降階技術的快速最小生成樹算法。該算法采用降階技術，大大加快了算法的求解速度，在最壞情況下算法的時間復雜度為O(m);另一方面，算法易于找到問題的全部最小生成樹。

關鍵詞:最小生成樹; 算法; 降階; 懸掛點

中圖分類號:TP301.6文獻標志碼:A

文章編號:1001-3695(2010)06-2051-03

doi:10.3969/j.issn.1001-3695.2010.06.015

Solving minimum spanning tree with reduction technology

XIONG Xiao-hua1，2， NING Ai-bing1， MA Liang1

(1. School of Management， University of Shanghai for Science Technology， Shanghai 200093， China; 2. College of Computer Information， Shanghai Second Polytechnic University， Shanghai 201209， China)

Abstract:Based on the mathematical properties of minimum spanning tree (MST)， presented a new and fast MST algorithm with reduction technology. Accelerated the algorithm by using the reduction technolgy and the time complexity in worst case was O(m). On the other hand the algorithm could be used to find all MST of a connected graph at the same time. Key words:minimum spanning tree(MST); algorithm; reduction; pendant vertex

0 引言

最小生成樹[1~3](MST)問題是一個經典的組合優化問題，許多工程問題，如通信網絡設計、物流運輸等，通常都可轉換為求最小生成樹問題。最小生成樹算法最早由Boruvka于1926年提出的，隨后Kruskal、Prim和Sollin分別提出了求解MST的貪婪算法[1～3]。Kruskal算法在執行的每步總是向最小生成樹中添加權值最小的且不形成回路的邊。Prim算法在執行的每步總是尋找兩個節點集的最短割邊，這兩種算法在最壞情況下的時間復雜度均為O(m+nlog n)[2]。其中m表示邊的條數;n表示節點的個數。Sollin算法可以看成是Kruskal與Prim算法的雜交。在每步開始時，所選擇的邊及圖中的n個頂點形成一個生成樹的森林。在每一步中為森林中的每棵樹選擇一條邊，這條邊剛好有一個頂點在樹中且邊的權值最小，將所選擇的邊加入要創建的生成樹中，Sollin算法的時間復雜度為O(mlog n)。其他還有很多學者采用特殊的數據結構對三種最小生成樹貪心算法進行改進[4，5]。目前求解最小生成樹的最快算法是Gabow等人在邊已經排好序的基礎上對Kruskal算法的改進，改進后算法的時間復雜度為O(m+log β(m，n))。其中β(m，n)=min{i|log(i)n≤m/n}。此外還有學者采用DNA算法、螞蟻算法等啟發式算法[6，7]求解最小生成樹問題。這些算法有一個共同的特點:每執行一次算法僅能找到一棵最小生成樹，且若要尋找其他的最小生成樹，需要重新開始執行算法。然而在不少的實際問題中，除了考慮權值最小的目標外，還需兼顧其他的目標，這就需要在若干最小生成樹中進行選擇。

本文在充分分析最小生成樹問題本身的數學性質的基礎上，提出了一個基于降階技術的最小生成樹的快速生成算法。該算法與其他算法不同的地方在于:其易于找到問題的全部最小生成樹，為實際工程項目中需要在多棵最小生成樹中作出選擇提供了方便。由于算法采用了降階技術，大大加快了求解的速度。

1 問題及算法簡介

1.1 問題簡介

考慮一個連通的無向簡單圖(無環無多重邊的圖就稱為簡單圖)G=(V，E)。其中V={ v1，v2，…，vn}是所有節點的集合，E={e1，e2，…，em) 為所有邊的集合。若邊ek的兩個端點為i和j，則邊ek可記為(i，j)，邊(i，j)的權值記為w(i，j)且w(i，j)為非負實數。在G的所有生成樹中，所有邊的權值之和最小的生成樹稱為G的最小生成樹，記為T*=(V，ET*)，T*的總權值記為W (T*)。

1.2 數學符號

為了方便描述，除了問題簡介中定義的符號外，還采用如下的符號:

n表示圖G中節點的數量;

m表示圖G中邊的數量;

表示空集合，即集合中的元素個數為0;

G1算法開始時，G1=G=(V，E);

T是圖G=(V，E)的子圖，它是T*的中間形成結果，當算法開始時T=(V，)，然后把邊逐步加入到T中，并最終形成T*;

w(i，j)表示邊(i，j)的權值;

d(vi)表示頂點vi的度。

2 算法分析及其實現

2.1 數學性質

下面給出算法能用到的數學性質。

定理1 圖G1中的懸掛點(度為1的節點)所關聯的邊一定在最小生成樹T*中。

證明 因為最小生成樹是連通的，若存在最小生成樹，則圖G1中懸掛點所關聯的邊一定在最小生成樹T*中。

由定理1可知，可利用定理1對問題進行降階處理。在算法最開始，將所有懸掛點及其關聯邊從圖G1中移除，并將關聯邊加入到子圖T中，此時可能會產生新的懸掛點，又可利用定理1降階，直到圖G1中不存在懸掛點為止。

定理2 對于經過引理1處理后得到的圖G1，若節點關聯的最短邊惟一(不存在多條最短邊)，則這條最短邊一定在最小生成樹T*中。

證明 用反證法證明。假設G1中存在一個節點k，在G1中k關聯惟一一條最短邊，記為(k，j)，且邊(k，j)不在最小生成樹T*中。由樹的性質可知，此時T*中一定存在一條鏈(k，i1，i2，…，ih，j)，且ig≠j (其中g=1，2，…，h)，此時若用邊(k，j)替換T*中邊(k，i1)，則T*仍然是G的生成樹。由于w(k，j)

由定理2可知，可利用定理2對問題進行二次降階處理。對于經過引理1處理后得到的圖G1(不再包含懸掛點)，找出圖G1中所有關聯的最短邊惟一的節點，將關聯的最短邊添加到子圖T中，并從圖G1中移除該最短邊。

經過兩次降階處理之后，圖G1中已不再含有懸掛點和僅關聯惟一一條最短邊的節點。子圖T中包含了一定在最小生成樹上的邊。若此時邊的條數為n-1，則子圖T即為最小生成樹T*;否則T必包含兩個或多個不連通的子樹。

定理3 對于連通的無向簡單圖G=(V，E)及其一棵生成樹T=(V，ET)，若把T中任意一條邊(i，j)從T中去掉，此時T被分割為兩棵不連通的子樹T1=(VT1，ET1)和T2=( VT2，ET2)，T是G的最小生成樹的充分必要條件是:邊(i，j)是G中能連通子樹T1和T2的最短割邊。

證明

1)充分性

此時已知邊(i，j)是能連通子樹T1和T2最短的一條邊。此時若把E-ET中的任意一邊(g，h)加入到T中，由樹的性質可知此時必然存在一條回路C=( g，i1，i2，…，ik，h，g)。對于回路 C中的任意一條非(g，h)的邊(ik，im) ， 若把邊(ik，im)與邊(g，h)同時從T中去掉，此時T被分割為兩棵不連通的子樹T1=(VT1，ET1)和T2=( VT2，ET2)且g與h分別在不同的子樹中。由于邊(ik，im)是能連通子樹Tk1和Tk2最短的一條邊，有w(ik，im)≤w(g，h)，這說明邊(g，h)是回路C中最長的一條邊。由于邊(i，j)是原來T中的任意一條邊，由最小生成樹的破圈算法可知T是G的最小生成樹。

2)必要性

此時已知T是G的最小生成樹。若此時邊(i，j)不是能連通子樹T1和T2最短的一條邊，假設存在一條能連通子樹T1和T2的邊(g，h)且w(g，h)< w(i，j)，那么可以把邊(i，j)從T去掉，而把邊(g，h)加入到T中得到Tnew，顯然Tnew也是G的生成樹且W(Tnew)

由定理3容易得到下面的引理1。

引理1 F是最小生成樹T*的子樹，S為F中所有節點的集合。若邊(i，j)是連接節點集S和(V-S)的最短割邊，則F中的邊以及邊(i，j)必然在一棵最小生成樹上。

證明 T*是一棵包含了F的最小生成樹。若邊(i，j)T*，將邊(i，j)添加到T*上，則此時形成一個回路C，且C中至少包含一條邊(p，q)，p∈S，q∈(V-S)，且(p，q)≠(i，j)。由假設知w(i，j)≤w(p，q)，而由定理3可知w(p，q)≤w(i，j)，故w(p，q)=w(i，j)。因此在T*上用邊(i，j)替換邊(p，q)，則產生了一棵包含F中的所有邊以及邊(i，j)的最小生成樹。

對于經過兩次降階處理后得到的子圖T，其包含圖G的全部節點以及一定出現在最小生成樹上的邊。若|T|

公式E(i，j)={(h，g)| (h，g)∈EG1且權值最小，節點h在子樹Ti上， g在子樹Tj上， i≠j }用來尋找連通兩棵子樹Ti和Tj的最短割邊。若此時E(i，j)包含不止一條最短割邊，根據引理1可知任取一條最短割邊均可構成一棵最小生成樹。若將各種最短割邊的組合情況全部枚舉出來，即可找到問題的全部最小生成樹。

2.2 算法實現

對連通的無向簡單圖G=(V，E)，在上文分析的基礎上，可得到求圖G的最小生成樹的快速降階算法。

輸入:無向簡單圖G=(V，E)。

輸出:T*=(V，ET*)，T*表示圖G的最小生成樹。

a)//初始化

G1=G=(V，E);T=(V，);

b)//處理懸掛點

在G1中找到一個懸掛點vi，用vh表示vi的惟一鄰接點;

將邊e=(vi，vh)添加到T中，并從G1中移除節點vi和邊(vi，vh);

若不能在G1中找到懸掛點，則跳轉至步驟c);

跳轉至步b);

c)//處理關聯的最短邊惟一的節點

在G1中找到僅關聯一條最短邊的節點vi ，用vh表示最短邊的另一端點;

將邊e=(vi，vh)添加到T中，并從G1中移除邊(vi，vh);

若不能在G1中找到僅關聯一條最短邊的節點，則跳轉至步驟d);

跳轉至步驟c);

d)//尋找連通各子樹的最短割邊以構成最小生成樹

若|T|=n-1則 { T*=T，結束整個算法;}

否則{

找出T中所有不連通的子樹，設子樹的棵數為k;

按照公式E(i，j) 計算子樹1到其他子樹的最短割邊(其中2≤j≤k ，i=1);

Emin={j| E(i，j)中邊的權值最小，2≤j≤k }表示與子樹1連通最短割邊權值最小的子樹;

從Emin任取一棵子樹，記為Tr，從E(1，r)中任取一條邊添加到T中。

跳轉至步驟d);}

2.3 算法時間復雜度分析

步驟b)在最差情況下的時間復雜度為O(n);步驟c)在最壞情況下的時間復雜度為O(m);步驟d)在最壞情況下的時間復雜度為O(m)。因此整個算法的時間復雜度為O(m)。

3 示例分析

為了更清楚地了解算法的原理及應用，下面給出一個示例來進行分析。

示例1 如圖1所示，邊上的數字為邊的權值。

1)處理度為1的節點

ET={(v5，v8)， (v8，v9)，(v8，v10)}，此時G1的情形如圖2 所示。

2)處理關聯的最短邊惟一的節點

節點v1，v2，v3，v4，v5均為關聯惟一一條最短邊的節點，將它們關聯的最短邊分別添加到T上并從G1上移除，此時G1和T的情形如圖3(a)和(b)所示。

3)尋找連通各子樹的最短割邊以構成最小生成樹

由圖3(b)可知T包含三個不連通的子樹T1、T2和T3。其中:VT1={v1，v6}，ET1={(v1，v6)}，VT2={v2，v3}，ET2={(v2，v3)}，VT3={v4，v7，v5，v8，v9，v10}，ET3={(v5，v8)，(v8，v9)，(v8，v10)，(v4，v7)，(v5，v7)}。

計算得E(1，2)={(v1，v2)}，E(1，3)={(v6，v7)，(v6，v5)}Emin={3}。

此時可以從E(1，3)中任取一條添加到T中，假定取邊(v6，v5)，則此時T的情況如圖4所示。

由圖4知T包含兩個不連通的子樹T1和T2。其中:VT1={v1，v6，v4，v7，v5，v8，v9，v10}，ET1={(v1，v6)，(v5，v8)，(v8，v9)，(v8，v10)，(v4，v7)，(v5，v7)，(v6，v5)}，VT2={v2，v3}，ET2={(v2，v3)}。

計算得E(1，2)={(v7，v2)，(v4，v3)}Emin={2}。

任取E(1，2)中一條邊添加到T中，此時T中邊的條數為n-1，即為所求的最小生成樹T*(圖5)，則算法結束。

由前面的分析可知，在3)中存在兩次任取一條最短割邊的情況，兩次取邊的組合情況如下:{(v6，v7)，(v7，v2)}，{(v6，v7)， (v4，v3)}，{(v6，v5)，(v7，v2)}，{(v6，v5)，(v4，v3)}，將這四種組合情況確定的邊加入到2)中處理得到的T，就可以得到問題的全部最小生成樹。

4 結束語

本文給出的最小生成樹快速降階算法，相比傳統的求最小生成樹的貪心算法，充分利用最小生成樹問題的數學性質來實現問題的降階，從而大大提高了問題的求解速度。另一方面，利用本算法可以方便地找到問題的全部最小生成樹。

參考文獻:

[1]AHUJA R K， MAGNANTI T L， ORLIN J B. Network flows:theory， algorithms， and applications(English Version)[M]. Beijing: Mechanical Industry Press， 2005:510-536.

[2]DASGUPTA S， PAPADIMITRIOU C H， VAZIRANI U V. Algorithms[EB/OL].http://www.cs.berkeley.edu/~vazirani/algorithms.html.

[3]SYSLO M M， DEO N， KOWALIK J S. Discrete optimization algorithms:withpascal programs[M].New Jersey:Prentice-Hall，1983:212-236.

[4]KARGER D R， KLEIN P N， TARJAN R E. A randomized linear-time algorithm to find minimum spanning trees[J]. Journal of the ACM，1995，42(2):321-328.

[5]NEUMANN F， WEGENER I. Randomized local search， evolutionary algorithms， and the minimum spanning tree problem[J].Theoretical Computer Science，2007，378(1):32-40.

[6]LIU Xi-kui， LI Yan， XU Jin. Solving minimum spanning tree problem with DNA computing[J]. Journal of Electrconics，2005，22(2):112-117.

[7]NEUMANN F， WITT C. Ant colony optimization and the minimum spanning tree problem: learning and intelligent optimization[C]//Proc of the 2nd International Conference.Berlin，Heidelberg:Springer-Verlag，2007:153-166.