假設(shè)你是電信的實(shí)施工程師，需要為一個(gè)鎮(zhèn)的九個(gè)村莊架設(shè)通信網(wǎng)絡(luò)做設(shè)計(jì)，村莊位置大致如下圖，其中v0～v8是村莊，之間連線的數(shù)字表示村與村間的可通達(dá)的直線距離，比如v0至v1就是10公里（個(gè)別如v0與v6，v6與v8，v5與v7未測(cè)算距離是因?yàn)橛懈呱交蚝矗挥杩紤]）。你們領(lǐng)導(dǎo)要求你必須用最小的成本完成這次任務(wù)。你說(shuō)怎么辦？
顯然這是一個(gè)帶權(quán)值的圖，即網(wǎng)結(jié)構(gòu)。所謂的最小成本，就是n個(gè)頂點(diǎn)，用n-1條邊把一個(gè)連通圖連接起來(lái)，并且使得權(quán)值的和最小。在這個(gè)例子里，每多一公里就多一份成本，所以只要讓線路連線的公里數(shù)最少，就是最少成本了。
我們?cè)谥v圖的定義和術(shù)語(yǔ)時(shí)，曾經(jīng)提到過(guò)，一個(gè)連通圖的生成樹(shù)是一個(gè)極小的連通子圖，它含有圖中全部的頂點(diǎn)，但只有足以構(gòu)成一棵樹(shù)的n-1條邊。
找連通網(wǎng)的最小生成樹(shù)，經(jīng)典的有兩種算法，普里姆算法和克魯斯卡爾算法。
普里姆（Prim）算法
為了能講明白這個(gè)算法，我們先構(gòu)造下圖的鄰接矩陣，如下圖的右圖所示。
也就是說(shuō)，現(xiàn)在我們已經(jīng)有了一個(gè)存儲(chǔ)結(jié)構(gòu)為MGragh的G。G有9個(gè)頂點(diǎn)，它的arc二維數(shù)組如圖7-6-3的右圖所示。數(shù)組中的我們用65535來(lái)代表∞。
于是普里姆（Prim）算法代碼如下，左側(cè)數(shù)字為行號(hào)。其中INFINITY為權(quán)值極大值，不妨是65535，MAXVEX為頂點(diǎn)個(gè)數(shù)最大值，此處大于等于9即可?，F(xiàn)在假設(shè)我們自己就是計(jì)算機(jī)，在調(diào)用MiniSpanTree_Prim函數(shù)，輸入上述的鄰接矩陣后，看看它是如何運(yùn)行并打印出最小生成樹(shù)的。
/* Prim算法生成最小生成樹(shù) */
void MiniSpanTree_Prim(MGraph G)
{
int min, i, j, k;
/* 保存相關(guān)頂點(diǎn)下標(biāo) */
int adjvex[MAXVEX];
/* 保存相關(guān)頂點(diǎn)間邊的權(quán)值 */
int lowcost[MAXVEX];
/* 初始化第一個(gè)權(quán)值為0，即v0加入生成樹(shù) */
/* lowcost的值為0，在這里就是此下標(biāo)的頂點(diǎn)已經(jīng)加入生成樹(shù) */
lowcost[0] = 0;
/* 初始化第一個(gè)頂點(diǎn)下標(biāo)為0 */
adjvex[0] = 0;
/* 循環(huán)除下標(biāo)為0外的全部頂點(diǎn) */
for (i = 1; i < G.numVertexes; i++)
{
/* 將v0頂點(diǎn)與之有邊的權(quán)值存入數(shù)組 */
lowcost[i] = G.arc[0][i];
/* 初始化都為v0的下標(biāo) */
adjvex[i] = 0;
}
for (i = 1; i < G.numVertexes; i++)
{
/* 初始化最小權(quán)值為∞， */
/* 通常設(shè)置為不可能的大數(shù)字如32767、65535等 */
min = INFINITY;
j = 1; k = 0;
/* 循環(huán)全部頂點(diǎn) */
while (j < G.numVertexes)
{
/* 如果權(quán)值不為0且權(quán)值小于min */
if (lowcost[j] != 0 && lowcost[j] < min)
{
/* 則讓當(dāng)前權(quán)值成為最小值 */
min = lowcost[j];
/* 將當(dāng)前最小值的下標(biāo)存入k */
k = j;
}
j++;
}
/* 打印當(dāng)前頂點(diǎn)邊中權(quán)值最小邊 */
printf("(%d,%d)", adjvex[k], k);
/* 將當(dāng)前頂點(diǎn)的權(quán)值設(shè)置為0，表示此頂點(diǎn)已經(jīng)完成任務(wù) */
lowcost[k] = 0;
/* 循環(huán)所有頂點(diǎn) */
for (j = 1; j < G.numVertexes; j++)
{
/* 若下標(biāo)為k頂點(diǎn)各邊權(quán)值小于此前這些頂點(diǎn)未被加入生成樹(shù)權(quán)值 */
if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j])
{
/* 將較小權(quán)值存入lowcost */
lowcost[j] = G.arc[k][j];
/* 將下標(biāo)為k的頂點(diǎn)存入adjvex */
adjvex[j] = k;
}
}
}
}
- 程序開(kāi)始運(yùn)行，我們由第4～5行，創(chuàng)建了兩個(gè)一維數(shù)組lowcost和adjvex，長(zhǎng)度都為頂點(diǎn)個(gè)數(shù)9。
- 第6～7行我們分別給這兩個(gè)數(shù)組的第一個(gè)下標(biāo)位賦值為0，adjvex[0]=0其實(shí)意思就是我們現(xiàn)在從頂點(diǎn)v0開(kāi)始（事實(shí)上，最小生成樹(shù)從哪個(gè)頂點(diǎn)開(kāi)始計(jì)算都無(wú)所謂，我們假定從v0開(kāi)始），lowcost[0]=0就表示v0已經(jīng)被納入到最小生成樹(shù)中，之后凡是lowcost數(shù)組中的值被設(shè)置為0就是表示此下標(biāo)的頂點(diǎn)被納入最小生成樹(shù)。
- 第8～12行表示我們讀取圖7-6-3的右圖鄰接矩陣的第一行數(shù)據(jù)。將數(shù)值賦值給lowcost數(shù)組，所以此時(shí)lowcost數(shù)組值為{0,10,65535,65535,65535,11,65535,65535,65535}，而adjvex則全部為0。此時(shí)，我們已經(jīng)完成了整個(gè)初始化的工作，準(zhǔn)備開(kāi)始生成。
- 第13～36行，整個(gè)循環(huán)過(guò)程就是構(gòu)造最小生成樹(shù)的過(guò)程。
- 第15～16行，將min設(shè)置為了一個(gè)極大值65535，它的目的是為了之后找到一定范圍內(nèi)的最小權(quán)值。j是用來(lái)做頂點(diǎn)下標(biāo)循環(huán)的變量，k是用來(lái)存儲(chǔ)最小權(quán)值的頂點(diǎn)下標(biāo)。
- 第17～25行，循環(huán)中不斷修改min為當(dāng)前l(fā)owcost數(shù)組中最小值，并用k保留此最小值的頂點(diǎn)下標(biāo)。經(jīng)過(guò)循環(huán)后，min=10，k=1。注意19行if判斷的lowcost[j]!=0表示已經(jīng)是生成樹(shù)的頂點(diǎn)不參與最小權(quán)值的查找。
- 第26行，因k=1，adjvex[1]=0，所以打印結(jié)果為(0,1)，表示v0至v1邊為最小生成樹(shù)的第一條邊。如下圖所示。
第27行，此時(shí)因k=1我們將lowcost[k]=0就是說(shuō)頂點(diǎn)v1納入到最小生成樹(shù)中。此時(shí)lowcost數(shù)組值為{0,0,65535,65535,65535,11,65535,65535,65535}。
第28～35行，j循環(huán)由1至8，因k=1，查找鄰接矩陣的第v1行的各個(gè)權(quán)值，與low-cost的對(duì)應(yīng)值比較，若更小則修改low-cost值，并將k值存入adjvex數(shù)組中。因第v1行有18、16、12均比65535小，所以最終lowcost數(shù)組的值為：{0,0,18,65535,65535,11,16,65535,12}。adjvex數(shù)組的值為：{0,0,1,0,0,0,1,0,1}。這里第30行if判斷的lowcost[j]!=0也說(shuō)明v0和v1已經(jīng)是生成樹(shù)的頂點(diǎn)不參與最小權(quán)值的比對(duì)了。
-
再次循環(huán)，由第15行到第26行，此時(shí)min=11，k=5，adjvex[5]=0。因此打印結(jié)構(gòu)為(0,5)。表示v0至v5邊為最小生成樹(shù)的第二條邊，如下圖所示。
image-20200510201940021 -
接下來(lái)執(zhí)行到36行，lowcost數(shù)組的值為：{0,0,18,65535,26,0,16,65535,12}。ad-jvex數(shù)組的值為：{0,0,1,0,5,0,1,0,1}。12．之后，相信大家也都會(huì)自己去模擬了。通過(guò)不斷的轉(zhuǎn)換，構(gòu)造的過(guò)程如下圖中圖1～圖6所示。
image-20200510202041522
有了這樣的講解，再來(lái)介紹普里姆（Prim）算法的實(shí)現(xiàn)定義可能就容易理解一些。
假設(shè)N=(V,{E})是連通網(wǎng)，TE是N上最小生成樹(shù)中邊的集合。算法從U={u0}(u0∈V)，TE={}開(kāi)始。重復(fù)執(zhí)行下述操作：在所有u∈U,v∈V-U的邊(u,v)∈E中找一條代價(jià)最小的邊(u0,v0)并入集合TE，同時(shí)v0并入U(xiǎn)，直至U=V為止。此時(shí)TE中必有n-1條邊，則T=(V,{TE})為N的最小生成樹(shù)。
由算法代碼中的循環(huán)嵌套可得知此算法的時(shí)間復(fù)雜度為O(n2)。
克魯斯卡爾（Kruskal）算法
普里姆（Prim）算法是以某頂點(diǎn)為起點(diǎn)，逐步找各頂點(diǎn)上最小權(quán)值的邊來(lái)構(gòu)建最小生成樹(shù)的。這就像是我們?nèi)绻⒂^某個(gè)展會(huì)，例如世博會(huì)，你從一個(gè)入口進(jìn)去，然后找你所在位置周邊的場(chǎng)館中你最感興趣的場(chǎng)館觀光，看完后再用同樣的辦法看下一個(gè)?？晌覀?yōu)槭裁床皇孪扔?jì)劃好，進(jìn)園后直接到你最想去的場(chǎng)館觀看呢？事實(shí)上，去世博園的觀眾，絕大多數(shù)都是這樣做的。
同樣的思路，我們也可以直接就以邊為目標(biāo)去構(gòu)建，因?yàn)闄?quán)值是在邊上，直接去找最小權(quán)值的邊來(lái)構(gòu)建生成樹(shù)也是很自然的想法，只不過(guò)構(gòu)建時(shí)要考慮是否會(huì)形成環(huán)路而已。此時(shí)我們就用到了圖的存儲(chǔ)結(jié)構(gòu)中的邊集數(shù)組結(jié)構(gòu)。以下是edge邊集數(shù)組結(jié)構(gòu)的定義代碼：
/* 對(duì)邊集數(shù)組Edge結(jié)構(gòu)的定義 */
typedef struct
{
int begin;
int end;
int weight;
} Edge;
我們將下圖的鄰接矩陣通過(guò)程序轉(zhuǎn)化為下圖的右圖的邊集數(shù)組，并且對(duì)它們按權(quán)值從小到大排序。
于是克魯斯卡爾（Kruskal）算法代碼如下，左側(cè)數(shù)字為行號(hào)。其中MAXEDGE為邊數(shù)量的極大值，此處大于等于15即可，MAXVEX為頂點(diǎn)個(gè)數(shù)最大值，此處大于等于9即可?，F(xiàn)在假設(shè)我們自己就是計(jì)算機(jī)，在調(diào)用MiniSpanTree_Kruskal函數(shù)，輸入下圖右圖的鄰接矩陣后，看看它是如何運(yùn)行并打印出最小生成樹(shù)的。
/* Kruskal算法生成最小生成樹(shù) */
/* 生成最小生成樹(shù) */
void MiniSpanTree_Kruskal(MGraph G)
{
int i, n, m;
/* 定義邊集數(shù)組 */
Edge edges[MAXEDGE];
/* 定義一數(shù)組用來(lái)判斷邊與邊是否形成環(huán)路 */
int parent[MAXVEX];
/* 此處省略將鄰接矩陣G轉(zhuǎn)化為邊集數(shù)組edges
并按權(quán)由小到大排序的代碼 */
for (i = 0; i < G.numVertexes; i++)
/* 初始化數(shù)組值為0 */
parent[i] = 0;
/* 循環(huán)每一條邊 */
for (i = 0; i < G.numEdges; i++)
{
n = Find(parent, edges[i].begin);
m = Find(parent, edges[i].end);
/* 假如n與m不等，說(shuō)明此邊沒(méi)有與現(xiàn)有生成樹(shù)形成環(huán)路 */
if (n != m)
{
/* 將此邊的結(jié)尾頂點(diǎn)放入下標(biāo)為起點(diǎn)的parent中 */
/* 表示此頂點(diǎn)已經(jīng)在生成樹(shù)集合中 */
parent[n] = m;
printf("(%d, %d) %d ", edges[i].begin,
edges[i].end, edges[i].weight);
}
}
}
/* 查找連線頂點(diǎn)的尾部下標(biāo) */
int Find(int *parent, int f)
{
while (parent[f] > 0)
f = parent[f];
return f;
}
1．程序開(kāi)始運(yùn)行，第5行之后，我們省略掉頗占篇幅但卻很容易實(shí)現(xiàn)的將鄰接矩陣轉(zhuǎn)換為邊集數(shù)組，并按權(quán)值從小到大排序的代碼，也就是說(shuō)，在第5行開(kāi)始，我們已經(jīng)有了結(jié)構(gòu)為edge，數(shù)據(jù)內(nèi)容是下圖的右圖的一維數(shù)組edges。
2．第5～7行，我們聲明一個(gè)數(shù)組parent，并將它的值都初始化為0，它的作用我們后面慢慢說(shuō)。
3．第8～17行，我們開(kāi)始對(duì)邊集數(shù)組做循環(huán)遍歷，開(kāi)始時(shí)，i=0。
4．第10行，我們調(diào)用了第19～25行的函數(shù)Find，傳入的參數(shù)是數(shù)組parent和當(dāng)前權(quán)值最小邊(v4,v7)的begin:4。因?yàn)閜arent中全都是0所以傳出值使得n=4。
5．第11行，同樣作法，傳入(v4,v7)的end:7。傳出值使得m=7。
6．第12～16行，很顯然n與m不相等，因此parent[4]=7。此時(shí)parent數(shù)組值為{0,0,0,0,7,0,0,0,0}，并且打印得到“(4,7)7”。此時(shí)我們已經(jīng)將邊(v4,v7)納入到最小生成樹(shù)中，如下圖所示。
7．循環(huán)返回，執(zhí)行10～16行，此時(shí)i=1，edge[1]得到邊(v2,v8)，n=2，m=8，par-ent[2]=8，打印結(jié)果為“(2,8)8”，此時(shí)parent數(shù)組值為{0,0,8,0,7,0,0,0,0}，這也就表示邊(v4,v7)和邊(v2,v8)已經(jīng)納入到最小生成樹(shù)，如下圖所示。
8．再次執(zhí)行10～16行，此時(shí)i=2，edge[2]得到邊(v0,v1)，n=0，m=1，parent[0]=1，打印結(jié)果為“(0,1)10”，此時(shí)parent數(shù)組值為{1,0,8,0,7,0,0,0,0}，此時(shí)邊(v4,v7)、(v2,v8)和(v0,v1)已經(jīng)納入到最小生成樹(shù)，如下圖所示。
9．當(dāng)i=3、4、5、6時(shí)，分別將邊(v0,v5)、(v1,v8)、(v3,v7)、(v1,v6)納入到最小生成樹(shù)中，如下圖所示。此時(shí)parent數(shù)組值為{1,5,8,7,7,8,0,0,6}，怎么去解讀這個(gè)數(shù)組現(xiàn)在這些數(shù)字的意義呢？
從下圖的右下方的圖i=6的粗線連線可以得到，我們其實(shí)是有兩個(gè)連通的邊集合A與B中納入到最小生成樹(shù)中的，如下圖所示。當(dāng)parent[0]=1，表示v0和v1已經(jīng)在生成樹(shù)的邊集合A中。此時(shí)將parent[0]=1的1改為下標(biāo)，由par-ent[1]=5，表示v1和v5在邊集合A中，par-ent[5]=8表示v5與v8在邊集合A中，par-ent[8]=6表示v8與v6在邊集合A中，par-ent[6]=0表示集合A暫時(shí)到頭，此時(shí)邊集合A有v0、v1、v5、v8、v6。我們查看parent中沒(méi)有查看的值，parent[2]=8表示v2與v8在一個(gè)集合中，因此v2也在邊集合A中。再由parent[3]=7、par-ent[4]=7和parent[7]=0可知v3、v4、v7在另一個(gè)邊集合B中。
10．當(dāng)i=7時(shí)，第10行，調(diào)用Find函數(shù)，會(huì)傳入?yún)?shù)edges[7].begin=5。此時(shí)第21行，parent[5]=8>0，所以f=8，再循環(huán)得par-ent[8]=6。因parent[6]=0所以Find返回后第10行得到n=6。而此時(shí)第11行，傳入?yún)?shù)edges[7].end=6得到m=6。此時(shí)n=m，不再打印，繼續(xù)下一循環(huán)。這就告訴我們，因?yàn)檫?v5,v6)使得邊集合A形成了環(huán)路。因此不能將它納入到最小生成樹(shù)中，如上圖所示。
11．當(dāng)i=8時(shí)，與上面相同，由于邊(v1,v2)使得邊集合A形成了環(huán)路。因此不能將它納入到最小生成樹(shù)中，如上圖所示。
12．當(dāng)i=9時(shí)，邊(v6,v7)，第10行得到n=6，第11行得到m=7，因此parent[6]=7，打印“(6,7)19”。此時(shí)parent數(shù)組值為{1,5,8,7,7,8,7,0,6}，如下圖所示。
13．此后邊的循環(huán)均造成環(huán)路，最終最小生成樹(shù)即為下圖所示。
好了，我們來(lái)把克魯斯卡爾（Kruskal）算法的實(shí)現(xiàn)定義歸納一下結(jié)束這一節(jié)的講解。
假設(shè)N=(V,{E})是連通網(wǎng)，則令最小生成樹(shù)的初始狀態(tài)為只有n個(gè)頂點(diǎn)而無(wú)邊的非連通圖T={V,{}}，圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。在E中選擇代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條代價(jià)最小的邊。依次類(lèi)推，直至T中所有頂點(diǎn)都在同一連通分量上為止。
此算法的Find函數(shù)由邊數(shù)e決定，時(shí)間復(fù)雜度為O(loge)，而外面有一個(gè)for循環(huán)e次。所以克魯斯卡爾算法的時(shí)間復(fù)雜度為O(eloge)。
對(duì)比兩個(gè)算法，克魯斯卡爾算法主要是針對(duì)邊來(lái)展開(kāi)，邊數(shù)少時(shí)效率會(huì)非常高，所以對(duì)于稀疏圖有很大的優(yōu)勢(shì)；而普里姆算法對(duì)于稠密圖，即邊數(shù)非常多的情況會(huì)更好一些。
