賀軍忠，王麗君

(隴南師范高等專科學(xué)校 電子商務(wù)學(xué)院，甘肅 成縣 742500)

關(guān)于最小生成樹(shù)問(wèn)題有兩種經(jīng)典的算法，克魯斯克爾(Kruskal)算法和普里姆(Prim)算法。在程序設(shè)計(jì)中，最小生成樹(shù)問(wèn)題出現(xiàn)的次數(shù)并不是很多，所以直接使用這些算法的機(jī)會(huì)也不多。不過(guò)，Kruskal算法是互斥集合數(shù)據(jù)結(jié)構(gòu)的優(yōu)秀應(yīng)用示例[1]，相同結(jié)構(gòu)的算法常常得到廣泛應(yīng)用，值得研究。而Prim算法與迪杰斯特拉算法類似，幾乎與迪杰斯特拉算法具有完全相同的形態(tài)，也常常被使用。雖然Kruskal算法和Prim算法都使用貪心法，工作原理相同，從沒(méi)有任何邊線的狀態(tài)開(kāi)始向樹(shù)結(jié)構(gòu)逐條添加邊線。但兩種算法的運(yùn)行機(jī)制大不相同，執(zhí)行方式存在很大差異。

1 Kruskal算法分析

1.1 Kruskal算法概述

通常是加權(quán)值最小的邊線包含于最小生成樹(shù)。Kruskal的最小生成樹(shù)算法也是基于這種原理設(shè)計(jì)而成的[2]。該算法會(huì)按照升序排列圖結(jié)構(gòu)中的所有邊線，然后把各條邊線逐條添加到生成樹(shù)。當(dāng)然，并不能因?yàn)榧訖?quán)值小就把邊線無(wú)條件添加到生成樹(shù)，這樣做有可能產(chǎn)生回路。因此，需要先考慮那些會(huì)產(chǎn)生回路的邊線并排除。Kruskal算法會(huì)按照這種方式檢查所有邊線，之后終止算法[3]。

1.2 Kruskal算法執(zhí)行過(guò)程分析

圖1表示Kruskal算法對(duì)圖結(jié)構(gòu)找出最小生成樹(shù)的執(zhí)行過(guò)程。圖1中用粗實(shí)線表示添加到最小生成樹(shù)的邊線，a～f表示頂點(diǎn)，1～5表示兩頂點(diǎn)間的加權(quán)值。剛開(kāi)始先選擇兩條最短的邊線(a，c)和(b，d)，然后按順序選擇了加權(quán)值為2和3的邊線。需要說(shuō)明的是從圖(d)到圖(e)的過(guò)程，此過(guò)程中，雖然還有兩條加權(quán)值為3的邊線，但是添加了權(quán)值為4的(c，d)。因?yàn)槿籼砑恿思訖?quán)值為3的邊線，就會(huì)形成回路而破壞樹(shù)結(jié)構(gòu)。最終得到的圖(f)中，邊線連接了圖結(jié)構(gòu)的所有頂點(diǎn)，而且沒(méi)有產(chǎn)生任何回路。

1.3 Kruskal算法的時(shí)間復(fù)雜度分析

通過(guò)分析算法的執(zhí)行過(guò)程就能了解Kruskal算法的實(shí)現(xiàn)方法與時(shí)間復(fù)雜度。首先得到邊線目錄并按照加權(quán)值大小排序，然后遍歷這些邊線并添加到生成樹(shù)。此時(shí)最重要的部分是，添加新邊線后，判斷此邊線和已添加的邊線是否形成回路。這可以說(shuō)是Kruskal算法的核心部分。要完成這種高效判斷，首先想到的方法是，把邊線添加到樹(shù)結(jié)構(gòu)后，對(duì)樹(shù)結(jié)構(gòu)進(jìn)行深度優(yōu)先搜索，確認(rèn)是否存在逆向邊[4]。這種方法會(huì)對(duì)每條邊線都執(zhí)行1次深度優(yōu)先搜索，因此，整個(gè)算法的時(shí)間復(fù)雜度是深度優(yōu)先搜索的時(shí)間復(fù)雜度O(|V|+|E|)再乘上|E|的結(jié)果值，即O(|E|2)。

1.4 Kruskal算法的實(shí)現(xiàn)方法分析

代碼1-1表示Kruskal算法的實(shí)現(xiàn)方法，此代碼使用了DisjointSet類。排序邊線目錄時(shí)，把邊線添加到pair

代碼1-1Kruskal最小生成樹(shù)算法

structDisjointSet;

constint MAX_V=100;

int V;

vector

intkruskal(vector&selected){

int ret=0;

selected.clear();

vectoredges;

for(int u=0;u

for(inti=0;i

int b=adj[u][i].first,cost=adj[u][i].second;

edges.push_back(make_pair(cost,make_pair(u,v)));

}

sort(edges.begin(),edges.End());

Disjointsetsets(V);

for(inti=0;i

int cost.edges(i).first;

int u=.edges[i].second.first,v.=edges[i].second second;

if(sets.find(u)==sets.find(v))continue;

sets.merge(u,v);

selected.push_back(make_pair(u,v));

ret=+cost;

}

return ret;

}

2 Prim算法

2.1 Prim算法概述

Prim最小生成樹(shù)算法的工作原理與Kruskal算法相同，但二者的執(zhí)行方式存在很大差異[5]。Kruskal算法主要把零星生成的樹(shù)結(jié)構(gòu)碎片合并以生成最小生成樹(shù)，而Prim算法會(huì)從單個(gè)起始點(diǎn)構(gòu)成的樹(shù)結(jié)構(gòu)開(kāi)始，向樹(shù)結(jié)構(gòu)逐條添加邊線以生成樹(shù)，因此，該過(guò)程中選擇的邊線始終保持連接狀態(tài)。對(duì)已經(jīng)生成的樹(shù)結(jié)構(gòu)，Prim算法只會(huì)考慮其相鄰邊線。除了這點(diǎn)外，Prim算法與Kruskal算法完全相同。因?yàn)镻rim算法也會(huì)反復(fù)執(zhí)行在可選邊線中選擇加權(quán)值最小的邊線的操作。

2.2 Prim算法執(zhí)行過(guò)程分析

圖2表示Prim算法在圖結(jié)構(gòu)中找出最小生成樹(shù)的執(zhí)行過(guò)程。圖中，包含于生成樹(shù)的頂點(diǎn)用同心圓表示，而粗實(shí)線表示包含的邊線，a～f表示頂點(diǎn)，1～5表示兩頂點(diǎn)間的加權(quán)值。由圖可知，每個(gè)階段都會(huì)向樹(shù)結(jié)構(gòu)添加1條邊線。圖中灰色虛線表示可能在下一階段添加到樹(shù)結(jié)構(gòu)的候選邊線，這些候選邊線會(huì)連接1個(gè)隸屬于樹(shù)結(jié)構(gòu)的頂點(diǎn)和1個(gè)不屬于樹(shù)結(jié)構(gòu)的頂點(diǎn)。圖(c)中的邊線(a，b)連接了兩個(gè)屬于樹(shù)結(jié)構(gòu)的頂點(diǎn)，所以此邊線不能成為候選邊線。Prim算法會(huì)找出加權(quán)值最小的候選邊線，并將其添加到樹(shù)結(jié)構(gòu)。這種過(guò)程會(huì)反復(fù)進(jìn)行，直到找出生成樹(shù)。

圖2 Prim算法的執(zhí)行過(guò)程

2.3 Prim算法的時(shí)間復(fù)雜度分析

整理上述說(shuō)明就能編寫(xiě)實(shí)現(xiàn)Prim算法的代碼。此代碼會(huì)把各頂點(diǎn)是否包含于樹(shù)結(jié)構(gòu)的信息保存到布爾類型數(shù)組added[]，然后在每個(gè)階段遍歷所有邊線，找出下一條要添加到樹(shù)結(jié)構(gòu)的邊線。雖然這種實(shí)現(xiàn)方法比較容易理解，但會(huì)耗費(fèi)很長(zhǎng)的運(yùn)行時(shí)間。添加1個(gè)頂點(diǎn)會(huì)耗費(fèi)O(|E|)的運(yùn)算時(shí)間，所以這樣編寫(xiě)的代碼會(huì)具有O(|V||E|)的時(shí)間復(fù)雜度。Kruskal算法的時(shí)間復(fù)雜度是O(|E|lg|E|)，這樣看來(lái)，這種時(shí)間復(fù)雜度的算法幾乎沒(méi)有什么實(shí)用性。如果連接到1個(gè)頂點(diǎn)的邊線超過(guò)兩條，此時(shí)會(huì)逐一檢查所有邊線，因而會(huì)浪費(fèi)寶貴的運(yùn)算時(shí)間。若理解了這個(gè)道理，就能對(duì)上述算法進(jìn)行優(yōu)化[6]。例如，在圖2(b)共有兩條邊線連接著樹(shù)和頂點(diǎn)b。此時(shí)，因存在長(zhǎng)度為1的邊線(d，b)，所以長(zhǎng)度為5的邊線(a，b)就沒(méi)有任何意義了。因此，對(duì)不屬于樹(shù)結(jié)構(gòu)的頂點(diǎn)，只保存連接樹(shù)結(jié)構(gòu)和頂點(diǎn)的最短邊線即可。然后遍歷各頂點(diǎn)并找出下一個(gè)要添加的頂點(diǎn)，就能夠在O(|V|)的運(yùn)算時(shí)間內(nèi)完成操作。

2.4 Prim算法的實(shí)現(xiàn)方法分析

Prim算法會(huì)生成數(shù)組min Weight[]以保存連接樹(shù)結(jié)構(gòu)和頂點(diǎn)邊線的最小權(quán)值。每次添加新頂點(diǎn)時(shí)，此數(shù)組就會(huì)遍歷連接此頂點(diǎn)的各條邊線，并進(jìn)行更新[7]。通過(guò)這種方法就能在O(|V|)的時(shí)間內(nèi)找出需要添加的新頂點(diǎn)，而只需對(duì)所有邊線檢查兩次，因?yàn)榘製和v添加到樹(shù)結(jié)構(gòu)時(shí)，各檢查1次邊線(u，v)。所以整個(gè)時(shí)間復(fù)雜度將會(huì)是O(|V|2+|E|)。代碼2-1表示實(shí)現(xiàn)這種方法的算法源代碼。為了確認(rèn)各頂點(diǎn)連接到樹(shù)結(jié)構(gòu)時(shí)實(shí)際使用的邊線，把使用邊線的另一個(gè)頂點(diǎn)保存到parent[]。

代碼2-1普里姆算法的實(shí)現(xiàn)方法

costint MAX_V=100;

constint INF=987654321;

// 頂點(diǎn)個(gè)數(shù)

int V;

// 圖結(jié)構(gòu)的鄰接表。保存成對(duì)(連接的頂點(diǎn)序號(hào)，邊線加權(quán)值)

vector

// 對(duì)給出的圖結(jié)構(gòu)，把最小生成樹(shù)中的邊線目錄保存到selected，并返回加權(quán)值之和

int prim(vector

selected.clear();

//相應(yīng)頂點(diǎn)是否已包含到樹(shù)結(jié)構(gòu)。

vectorsbool> added(V,false);

// 保存樹(shù)結(jié)構(gòu)相鄰邊線中接到相應(yīng)頂點(diǎn)的最小邊線的信息。

vectorminweight(V,INF),parent(V,-1);

//保存加權(quán)值之和的變量

Intren=0;

// /以0號(hào)頂點(diǎn)為起點(diǎn)：總是最先添加到樹(shù)結(jié)構(gòu)。

Minweight[0]-parent[0]=0

for(intiter=0;iter

//找出下一個(gè)要添加到樹(shù)結(jié)構(gòu)的頂點(diǎn)u

int u=1;

for(int v=0;v

if(!added[v]&&s(u==-1 ||minweight[u]>minweitght[v]))

u=v;

//把(parent[u],u)加到樹(shù)結(jié)構(gòu)。

if(parent[u]!=0)

selected.push_back(nake_pair(parent[u],u));

ret+=minweight[u];

added[u]=true;

//檢u的相鄰邊線(u,v)

for(inti=0;i

int v=adj[u][i].first,weight=adj[u[i].second;

if(!added(v)&&minweight[v]>weight){

parent[v]=u;

minweight[v]=weight;

}

}

}

return ret;

}

3 Kruskal和Prim算法比較

Prim算法和Kruskal算法都是最小生成樹(shù)的經(jīng)典算法，都可以用貪心法證明兩種算法的正確性。根據(jù)Kruskal算法的執(zhí)行過(guò)程得知，需要對(duì)所有邊線按權(quán)重從小到大進(jìn)行排序，在沒(méi)有形成回路的前提下，依次將邊線權(quán)重最小的加到最小生成樹(shù)中。因此，邊數(shù)較少時(shí)可以用Kruskal算法。Kruskal算法在找最小生成樹(shù)結(jié)點(diǎn)之前，將排序好的權(quán)重邊依次加到最小生成樹(shù)中，當(dāng)所有的結(jié)點(diǎn)都加到最小生成樹(shù)中后，就找到了這個(gè)連通圖的最小生成樹(shù)[8]。當(dāng)邊數(shù)較多時(shí)可以用Prim算法，因?yàn)樗敲看渭右粋€(gè)頂點(diǎn)，對(duì)邊數(shù)多的適用。雖然Prim最小生成樹(shù)算法的工作原理與Kruskal算法相同，但二者的執(zhí)行方式存在很大差異。Prim算法是從單個(gè)起始點(diǎn)構(gòu)成的樹(shù)結(jié)構(gòu)開(kāi)始，向樹(shù)結(jié)構(gòu)逐條添加邊線以生成樹(shù)。也就是說(shuō)，Prim最小生成樹(shù)是從一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)無(wú)向完全圖中選擇n-1條邊并使這個(gè)圖連通，同時(shí)使生成樹(shù)的權(quán)值最小。Prim算法從圖中的一個(gè)頂點(diǎn)開(kāi)始，把這個(gè)頂點(diǎn)包含在一個(gè)集合中，反復(fù)尋找一個(gè)頂點(diǎn)已在該集合中而另一個(gè)頂點(diǎn)還不在該集合中的最小權(quán)邊，把新邊和新結(jié)點(diǎn)歸并到生成樹(shù)中，找到這個(gè)連通圖的最小生成樹(shù)。從方法上來(lái)看，Kruskal是需要先對(duì)權(quán)重邊線排序后再查找，一次就能根據(jù)權(quán)重邊線找到最小生成樹(shù)；而Prim算法是直接查找，多次迭代尋找鄰邊的權(quán)重最小值，所以從時(shí)間復(fù)雜度上來(lái)說(shuō)，Kruskal在算法效率上比Prim更快[9]。

4 結(jié)論

通過(guò)對(duì)克魯斯克爾(Kruskal)算法和普里姆(Prim)算法進(jìn)行分析研究，并從兩種算法的執(zhí)行過(guò)程，時(shí)間復(fù)雜度、實(shí)現(xiàn)方法等幾個(gè)方面進(jìn)行對(duì)比分析，得出了在不同圖結(jié)構(gòu)中，兩種算法各自的優(yōu)缺點(diǎn)，為解決實(shí)際問(wèn)題提供相應(yīng)的理論依據(jù)。具體而言，從執(zhí)行方法上來(lái)看，Kruskal是需要先對(duì)權(quán)重邊線排序后再查找，一次就能根據(jù)權(quán)重邊線找到最小生成樹(shù)；而Prim算法是直接查找，多次迭代尋找鄰邊的權(quán)重最小值，最終找到最小生成樹(shù)；從時(shí)間復(fù)雜度上來(lái)說(shuō)，Kruskal在算法效率上比Prim更快?？傊?，在圖結(jié)構(gòu)中邊數(shù)較少時(shí)采用Kruskal算法，邊數(shù)較多時(shí)采用Prim算法較合理。