賀軍忠，王麗君

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

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

1 Kruskal算法分析

1.1 Kruskal算法概述

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

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

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

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

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

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

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

代碼1-1Kruskal最小生成樹算法

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

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

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

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

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

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

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

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

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

costint MAX_V=100;

constint INF=987654321;

// 頂點個數(shù)

int V;

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

vector

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

int prim(vector

selected.clear();

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

vectorsbool> added(V,false);

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

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

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

Intren=0;

// /以0號頂點為起點：總是最先添加到樹結(jié)構(gòu)。

Minweight[0]-parent[0]=0

for(intiter=0;iter

//找出下一個要添加到樹結(jié)構(gòu)的頂點u

int u=1;

for(int v=0;v

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

u=v;

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

4 結(jié)論

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