最小生成樹三種求解方法的分析與實現(xiàn)

李龍霞 陳燕 于曉倩

摘要：圖作為一種典型的非線性結(jié)構(gòu)，用圖來描述問題簡明直觀。而最小生成樹作為圖的重要應(yīng)用之一，用于解決優(yōu)化路線，如何使網(wǎng)絡(luò)通信線路成本最低，電話線路最短等問題。將此類問題轉(zhuǎn)化為最小生成樹問題進(jìn)行求解。最小生成樹是所有生成樹中代價最小的生成樹。它以鄰接矩陣的方式存儲，采用Prim算法，Kruskal算法和破圈法的方法進(jìn)行求解。

關(guān)鍵詞：圖;最小生成樹;Prim算法;Kruskal算法;破圈法

中圖分類號：TP301.6;TP311.12? ?文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2021）33-0044-03

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

Analysis and Realization of Three Methods of Solving Minimum Spanning Tree

LI Long-xia， CHEN Yan， YU Xiao-qian

（School of Maritime Economics and Management， Dalian Maritime University， Dalian 116026， China）

Abstract： Graph， as a typical nonlinear structure， is simple and intuitive to describe the problem. As one of the most important applications of graphs， the minimum spanning tree is used to solve the problems of optimizing routes， minimizing the cost of network communication lines and the shortest telephone lines. This kind of problem is transformed into the minimum spanning tree problem to solve. The minimum spanning tree is the spanning tree with the least cost among all spanning trees. It is stored in the form of adjacency matrix and solved by Prim algorithm， Kruskal algorithm and loop breaking method.

Key words： Graph; Minimum Spanning Tree; Prim algorithm; Kruskal algorithm; Broken Ring Method

1 引言

求解最小生成樹是解決工程類問題的一種重要手段。許多工程類問題（如城市公交，油管鋪設(shè)等）中，涉及n個城市，m條道路的選擇。而這些道路彼此交互，用圖來描述問題更為直觀明晰。若在一個圖中，任意兩個頂點之間都存在一條路徑，則稱此圖為連通圖。若某個連通圖有n個頂點和e條邊，那么由n個頂點，n-1條邊構(gòu)成的是極小連通圖，也稱為該連通圖的生成樹。在實際問題中，往往需要得到成本最低、造價最小的最小生成樹。如利用最小生成樹來解決工程類問題中的網(wǎng)絡(luò)線纜問題，將網(wǎng)絡(luò)線纜問題中的通信網(wǎng)絡(luò)城市看作圖中的頂點，城市間鋪設(shè)的電纜線路看作圖中頂點之間的邊，城市之間所修建的電纜線路的代價看作時圖中各邊上的權(quán)值。這樣就把網(wǎng)絡(luò)線纜問題轉(zhuǎn)換成了求一個連通網(wǎng)的最小生成樹問題。

求解最小生成樹有兩大類解法，即避圈法和破圈法。避圈法的做法是：利用MST性質(zhì)（假設(shè)N=（V，{E}）是一個連通網(wǎng)，U是頂點V的一個非空子集。若（u，v）是一條具有最小權(quán)值（代價）的邊，其中u∈U，v∈V-U，則必存在一棵包含邊（u，v）的最小生成樹。），避免形成回路，介紹兩種不同的算法——Prim算法和Kruskal算法。破圈法的做法是：去掉圖中圈的權(quán)值最大的邊，破掉回路。破圈法的算法是從圖G的任意圈開始，去掉該圈中權(quán)值最大的一條邊，稱為破圈，不斷破圈，直到圖G中沒有圈為止。

2 求解最小生成樹

例如：現(xiàn)需要在南京、合肥、南昌、杭州、武漢、福州和長沙七個城市之間鋪設(shè)寬帶，每個城市用一個頂點表示（這七個城市表示為頂點A，頂點B，...，頂點G），兩個城市要鋪設(shè)寬帶的路線用一條邊表示，鋪設(shè)寬帶線路的成本用邊上的權(quán)值表示。使總的成本最低的過程，就是求解最小生成樹的過程。以此為例說明三種求最小生成樹的方法：

2.1 Prim算法

Prim算法是由美國科學(xué)家羅伯特·普里姆（Robert C. Prim）獨立發(fā)現(xiàn)。

Prim算法的思想是：假設(shè)G連通，V為G上頂點的集合，E為G上邊的集合，U是G最小生成樹中頂點的集合，TE是G最小生成樹中邊的集合。算法初始狀態(tài)為U={u0}，TE={}，不斷從所有滿足（u，v）∈E（u∈U，v∈V-U）的邊中找出權(quán)值最小的邊（u0，v0），若（u0，v0）與TE中的邊不構(gòu)成回路，則將（u0，v0）并入集合TE中，同時v0并入U，直到V=U為止。Prim算法的核心：始終保持TE中的邊集構(gòu)成一棵生成樹。

核心算法：

// 從未加入到最小生成樹的頂點中找出權(quán)值最小的頂點。

while （j < G.vexnumber） {

// 若weights[j]=0，意味著第j個節(jié)點已經(jīng)加入最小生成樹

if （res[j].weight ！= 0 && res[j].weight < min）{

min = res[j].weight;

k = j;

}

j++;

}

//在未加入最小生成樹的頂點中，第k個是權(quán)值最小的頂點

//將第k個頂點加入最小生成樹的結(jié)果數(shù)組中

prims[index++] = G.vex[k];

算法說明：

1）圖的存儲方式有鄰接矩陣、鄰接表、十字鏈表等，但由于鄰接矩陣能更清晰地顯示出點與點之間有無邊以及權(quán)值的大小，故在上面的算法中是以鄰接矩陣的方式存儲。例題中的圖1表示為如圖2的鄰接矩陣。

鄰接矩陣的存儲結(jié)構(gòu)

typedef struct _graph

{ char vex[MAX];? ? ? ?// 頂點集合

int vexnumber，edgnumber;? // 頂點數(shù)和邊數(shù)

int matrix[MAX][MAX]; // 鄰接矩陣

}Graph， *PGraph;

2）借助prims數(shù)組來記錄頂點，res數(shù)組來記錄邊的權(quán)值（包括兩個頂點和權(quán)值）。（注：res[].begin和res[].end并不代表該邊的起點和終點，只是為了將該邊連接的兩個頂點區(qū)分開。）

3）res數(shù)組記錄的不是結(jié)果，而是過程。第k個頂點要加入U中，則res[k].weight置為0;若在這一次循環(huán)中，第k個頂點未被加入到U中，則res[k]的值都要更新，res[k].weight更新為一個頂點在U中，另一個頂點在V中的邊的權(quán)值。

以圖1為例，假設(shè)起點為A，那么U為{A}，TE={}，V={B，C，D，E，F(xiàn)，G}。表1中列出了Prim算法詳細(xì)的求解過程。

Prim算法是從頂點出發(fā)，在已加入的頂點出發(fā)的邊中選擇權(quán)值最小的邊。Prim算法的時間復(fù)雜度為O（n^2），其時間復(fù)雜度與頂點的數(shù)目有關(guān)，與邊的數(shù)目無關(guān)，因此更適合于求稠密圖的最小生成樹。

2.2 Kruskal算法

Kruskal算法是由Joseph Bernard Kruskal Jr.提出。算法步驟是：假設(shè)G是連通的且包含n個頂點，先構(gòu)造一個只含n個頂點的子圖T。1）遍歷圖G，找出權(quán)值最小的邊。2）若將此條邊加入T中不形成回路，則加入最小生成樹T中;若將此條邊加入T中形成回路，則舍棄這條邊，繼續(xù)步驟1;直到子圖T中含n-1條邊為止，算法結(jié)束。此時得到的子圖T就是圖G的最小生成樹。仍以圖1為例，假設(shè)子圖T包含所有點，不含邊，具體步驟見表2。

說明：（A，D）和（C，E）權(quán)值相等，任選其一加入T即可，加入的順序并不影響最終結(jié)果。（A，B）和（B，E）同理。

Kruskal算法是從所有未加入邊集中選擇權(quán)值最小的邊，并把它的頂點加入頂點集。Kruskal算法的時間復(fù)雜度為O（eloge）（e為網(wǎng)中邊數(shù)），只與邊相關(guān)，因此更適合于求稀疏圖的最小生成樹。

2.3 破圈法

破圈法是由我國著名數(shù)學(xué)家管梅谷在1975年提出。破圈法是區(qū)別于避圈法（Prim算法和Kruskal算法）的一種尋找最小生成樹的算法。破圈法是"見圈破圈"，即如果看到圖中有一個圈，就將這個圈的邊去掉一條，直至圖中再無一圈為止。步驟如下：①在圖中找一個回路，去掉該回路中權(quán)值最大的邊，但要保持圖仍為連通。②反復(fù)①過程，直至圖中再無回路（但仍保持連通），得到最小生成樹。

仍然以圖1為例，按照路徑長度從小到大進(jìn)行查找，以避免無序。求解過程如表3。

此時，圖中已無圈，且有（頂點數(shù)-1）條邊。

最小生成樹的總代價=5（A，D）+7（A，B）+6（D，F(xiàn)）+7（B，E）+5（C，E）+9（E，G）=39

3 結(jié)論

這三個算法都是基于貪婪算法的思想設(shè)計的（一個從任意點開始，一個從最小邊開始，一個從任意圈開始），每一步選擇局部最優(yōu)，從而期望得到全局最優(yōu)的算法。Prim算法是對節(jié)點進(jìn)行遍歷，時間復(fù)雜度是平方階，只與點的個數(shù)有關(guān)，因此更適合于求稠密圖的最小生成樹。Kruskal算法是對邊進(jìn)行遍歷，時間復(fù)雜度是對數(shù)階，只與邊的數(shù)目有關(guān)，因此更適合于求稀疏圖的最小生成樹。破圈法算法是對每個回路進(jìn)行破壞。

這三個算法中，Prim算法和Kruskal算法是在數(shù)據(jù)結(jié)構(gòu)課程中學(xué)習(xí)，而破圈法是在管理運(yùn)籌學(xué)課程中學(xué)習(xí)，是從形成回路的邊中找到權(quán)值最大的邊刪除，此方法較為簡單。在學(xué)習(xí)過程中要善于總結(jié)，將不同學(xué)科中解決相同問題的不同方法放在一起去學(xué)習(xí)、比較。這樣，解決實際問題的時候，才能根據(jù)具體問題的特點選擇更合適的方法。

參考文獻(xiàn)：

[1] 陳燕，曹妍，賈紅雨，李曄.數(shù)據(jù)結(jié)構(gòu)[M].北京：科學(xué)出版社，2016.

[2] 嚴(yán)蔚敏，李冬梅，吳偉民.數(shù)據(jù)結(jié)構(gòu)：C語言版[M].2版.北京：人民郵電出版社，2015.

[3] 張淑萍.最小生成樹算法及其在天然氣管道網(wǎng)中的應(yīng)用研究[J].電腦知識與技術(shù)，2020，16（17）：214-216.

[4] 張恒，孫建春，涂鵬，等.利用通風(fēng)網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)構(gòu)造最小生成樹的方法[J].地下空間與工程學(xué)報，2018，14（S2）：887-892.

[5] 楊晶，張兆鑫，王鵬.最小生成樹算法在城市基礎(chǔ)建設(shè)中的應(yīng)用[J].電子測試，2015（2）：37-38，36.

[6] 王化宇.最小生成樹算法及其應(yīng)用[J].內(nèi)蒙古科技與經(jīng)濟(jì)，2011（6）：72-73.

[7] 段東東.最小生成樹算法及其應(yīng)用[J].西安航空技術(shù)高等?？茖W(xué)校學(xué)報，2010，28（1）：55-57.

[8] 王新奇.最小生成樹算法及其應(yīng)用[J].西安文理學(xué)院學(xué)報（自然科學(xué)版），2009，12（3）：23-26.

【通聯(lián)編輯：梁書】