第4章貪心算法

1第4章貪心算法計算機與信息工程學(xué)院2第4章貪心算法

顧名思義，貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。決策一旦作出，就不可更改。 當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。 在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。例：找零錢問題設(shè)有4種硬幣，面值分別是25分、10分、5分、1分?，F(xiàn)找給顧客67分，而且要使總的硬幣數(shù)最少。蠻干法：窮舉所有可能貪心法：每次加入一個面值不超過零錢數(shù)的最大硬幣：25+25+10+5+1+1舉例例：找零錢問題貪心法并不能保證任何情況下都能得到最優(yōu)解。如硬幣面值改為1分、5分、11分；現(xiàn)在須找15分。若按貪心算法：11+1+1+1+1而實際最優(yōu)解為：5+5+5舉例54.1活動安排問題

活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。

該問題要求高效地安排一系列爭用某一公共資源的活動。

貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。64.1活動安排問題設(shè)有n個活動的集合E={1,2,…,n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源?；顒酉嗳莸亩x：每個活動i都有一個要求使用該資源的起始時間si和一個結(jié)束時間fi,且si<fi

。如果選擇了活動i，則它在半開時間區(qū)間[si,fi)內(nèi)占用資源。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動i與活動j是相容的。也就是說，當(dāng)si≥fj或sj≥fi時，活動i與活動j相容。74.1活動安排問題publicstaticintgreedySelector(int[]s,int[]f,booleana[]){intn=s.length-1;a[1]=true;intj=1;intcount=1;for(inti=2;i<=n;i++){

if(s[i]>=f[j]){a[i]=true;j=i;count++;}elsea[i]=false;}returncount;}在下面所給出的解活動安排問題的貪心算法greedySelector:各活動的起始時間和結(jié)束時間存儲于數(shù)組s和f中且按結(jié)束時間的非減序排列

84.1活動安排問題 由于輸入的活動以其完成時間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。

算法greedySelector的效率極高。當(dāng)輸入的活動已按結(jié)束時間的非減序排列，算法只需O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用O(nlogn)的時間重排。94.1活動安排問題

例：設(shè)待安排的11個活動的開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下：i1234567891011S[i]130535688212f[i]4567891011121314104.1活動安排問題

算法greedySelector的計算過程如左圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動，而空白長條表示的活動是當(dāng)前正在檢查相容性的活動。114.1活動安排問題若被檢查的活動i的開始時間si小于最近選擇的活動j的結(jié)束時間fj，則不選擇活動i，否則選擇活動i加入集合A中。

貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題，貪心算法greedySelector卻總能求得整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。這個結(jié)論可以用數(shù)學(xué)歸納法證明。4.1活動安排問題正確性證明（用數(shù)學(xué)歸納法證明） 1、貪心選擇性質(zhì) 即證明活動安排問題總存在一個最優(yōu)解從貪心選擇開始。4.1活動安排問題正確性證明（用數(shù)學(xué)歸納法證明） 1、

貪心選擇性質(zhì) 設(shè)E={1,2,…,n}為所給的活動集合。由于E中的活動按結(jié)束時間的非遞減排序，故活動1具有最早完成時間。首先證明活動安排問題有一個最優(yōu)解以貪心選擇開始，即該最優(yōu)解中包含活動1.4.1活動安排問題正確性證明（用數(shù)學(xué)歸納法證明） 1、

貪心選擇性質(zhì) 設(shè)A?E是所給活動安排問題的一個最優(yōu)解，且A中的活動也按結(jié)束時間非遞減排序，A中的第一個活動是k。4.1活動安排問題正確性證明（用數(shù)學(xué)歸納法證明） 1、

貪心選擇性質(zhì) 若k＝1,則A就是以貪心選擇開始的最優(yōu)解。 若k>1,設(shè)B=A-{k}∪{1}。因為f1<=fk且A中的活動是相容的。故B中的活動也是相容的。又由于B中的活動個數(shù)與A中的活動個數(shù)相同，故A是最優(yōu)的，B也是最優(yōu)的。即B是以選擇活動1開始的最優(yōu)活動安排。 由此可見，總存在以貪心選擇開始的最優(yōu)活動安排方案。4.1活動安排問題正確性證明（用數(shù)學(xué)歸納法證明） 2、最優(yōu)子結(jié)構(gòu)性質(zhì) 在作出了貪心選擇，即選擇了活動1后，原問題簡化為對E中所有與活動1相容的活動進(jìn)行活動安排的子問題。即若A是原問題的最優(yōu)解，則A’=A-{1}是活動安排問題的E’={i∈E:Si≥f1}的最優(yōu)解。4.1活動安排問題正確性證明（用數(shù)學(xué)歸納法證明） 2、最優(yōu)子結(jié)構(gòu)性質(zhì) 反證法：若E’中存在另一個解B’，比A’有更多的活動，則將1加入B’中產(chǎn)生另一個解B，比A有更多的活動。與A的最優(yōu)性矛盾。4.1活動安排問題正確性證明（用數(shù)學(xué)歸納法證明） 因此，每一步所作出的貪心選擇都將問題簡化為一個更小的與原問題具有相同形式的子問題。對貪心選擇次數(shù)用歸納法可知，貪心算法greedySelector產(chǎn)生問題的最優(yōu)解。194.2貪心算法的基本要素 本節(jié)著重討論可以用貪心算法求解的問題的一般特征。 對于一個具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個問題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有2個重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。

204.2貪心算法的基本要素1、貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。214.2貪心算法的基本要素

當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。2、最優(yōu)子結(jié)構(gòu)性質(zhì)224.2貪心算法的基本要素 貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是2類算法的一個共同點。但是，對于具有最優(yōu)子結(jié)構(gòu)的問題應(yīng)該選用貪心算法還是動態(tài)規(guī)劃算法求解?是否能用動態(tài)規(guī)劃算法求解的問題也能用貪心算法求解?下面研究2個經(jīng)典的組合優(yōu)化問題，并以此說明貪心算法與動態(tài)規(guī)劃算法的主要差別。3、貪心算法與動態(tài)規(guī)劃算法的差異234.2貪心算法的基本要素0-1背包問題：

給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?在選擇裝入背包的物品時，對每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。244.2貪心算法的基本要素背包問題：

與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。

這2類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。254.2貪心算法的基本要素

首先計算每種物品單位重量的價值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過C，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。 具體算法可描述如下頁：

用貪心算法解背包問題的基本步驟：264.2貪心算法的基本要素publicstaticfloatknapsack(floatc,float[]w,float[]v,float[]x){intn=v.length;Element[]d=newElement[n];for(inti=0;i<n;i++)d[i]=newElement(w[i],v[i],i);MergeSort.mergeSort(d);inti;floatopt=0;for(i=0;i<n;i++)x[i]=0;for(i=0;i<n;i++){if(d[i].w>c)break;x[d[i].i]=1;//可以完全裝入；opt+=d[i].v;c-=d[i].w;}if(i<n){//不能完全裝入d[i].w;x[d[i].i]=c/d[i].w;//裝入部分；opt+=x[d[i].i]*d[i].v;}returnopt;}

算法knapsack的主要計算時間在于將各種物品依其單位重量的價值從大到小排序。因此，算法的計算時間上界為O（nlogn）。當(dāng)然，為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質(zhì)。270-1背包問題不適用貪心算法背包容量50kg，三物品的容量和價值分別為(10kg,$60),(20kg,$100)和(30kg,$120)。單位重量價值最高的是物品1。但是依照貪心算法首選物品1卻不能獲得最優(yōu)解：物品1物品2物品3總價值為$160,空余20kg總價值為$180,空余10kg總價值為$220,沒有空余物品1物品2物品3284.2貪心算法的基本要素 對于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因為在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。事實上，在考慮0-1背包問題時，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問題。這正是該問題可用動態(tài)規(guī)劃算法求解的另一重要特征。 實際上也是如此，動態(tài)規(guī)劃算法的確可以有效地解0-1背包問題。294.3單源最短路徑 給定帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)是非負(fù)實數(shù)。另外，還給定V中的一個頂點，稱為源?，F(xiàn)在要計算從源到所有其它各頂點的最短路長度。這里路的長度是指路上各邊權(quán)之和。這個問題通常稱為單源最短路徑問題。 1、算法基本思想 Dijkstra算法是解單源最短路徑問題的貪心算法。304.3單源最短路徑 其基本思想是，設(shè)置頂點集合S并不斷地作貪心選擇來擴(kuò)充這個集合。一個頂點屬于集合S當(dāng)且僅當(dāng)從源到該頂點的最短路徑長度已知。 初始時，S中僅含有源。設(shè)u是G的某一個頂點，把從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個頂點所對應(yīng)的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到S中，同時對數(shù)組dist作必要的修改。一旦S包含了所有V中頂點，dist就記錄了從源到所有其它頂點之間的最短路徑長度。314.3單源最短路徑

例如，對右圖中的有向圖，應(yīng)用Dijkstra算法計算從源頂點1到其它頂點間最短路徑的過程列在下頁的表中。4.3單源最短路徑迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}510503060Dijkstra算法的迭代過程：2.正確性證明 1)貪心選擇性質(zhì) 貪心選擇：從V-S中選擇具有最短特殊路徑長度的頂點u，從而確定源點到u的最短路徑長度dist[u]。 這種選擇為什么導(dǎo)致最優(yōu)解？即為什么從源到u沒有更短的其它路徑呢？4.3單源最短路徑2.正確性證明 1)貪心選擇性質(zhì) 反證法：若存在一條從源到u且長度比dist[u]更短的路。設(shè)這條路初次走出S之外到達(dá)的頂點為x∈V-S，然后徘徊于S內(nèi)外若干次，最后離開S到達(dá)u。

dist[x]≤d(v,x)≤d(v,x)＋d(x,u)=d(v,u)<dist[u]得出矛盾。4.3單源最短路徑Svux2.正確性證明 2)最優(yōu)子結(jié)構(gòu)性質(zhì) 即在作出貪心選擇后，如何保證剩余的問題仍是與原問題相似的子問題。 關(guān)鍵是要確保dist數(shù)組在將u加入到S后仍使每個i的dist[i]是當(dāng)前最短的特殊路徑長度。

如何確保？ 在u加入S后，原來從源到i的最短特殊路徑長度可能會因為u的加入而縮短，須進(jìn)行調(diào)整。

4.3單源最短路徑2.正確性證明 2)最優(yōu)子結(jié)構(gòu)性質(zhì) 將添加u之前的S稱為老S?？紤]三種可能： i)dist[i]-原來的經(jīng)過老的S直接到達(dá)i ii)dist[u]+d[u][i]－－經(jīng)過老的S到u，再從u經(jīng)過一條邊直接到達(dá)i iii)dist[u]+d(u,x)+d(x,i)－－經(jīng)過老的S到u，再從u回到老S中某個頂點x，最后才到達(dá)i

4.3單源最短路徑Svixu2.正確性證明 2)最優(yōu)子結(jié)構(gòu)性質(zhì) 考慮iii)dist[u]+d(u,x)+d(x,i)－－經(jīng)過老的S到u，再從u回到老S中某個頂點x，最后才到達(dá)i： d(v,x)=dist[x]<dist[u]=d(v,u)d(v,x)<d(v,u)+d(u,x)

dist[i]≤d(v,x)+d(x,i)<d(v,u)+d(u,x)+d(x,i)

故不必考慮這種路徑4.3單源最短路徑Svixu2.正確性證明

如此調(diào)整后，使得在加入u到S后，dist數(shù)組中存放的仍然是從源到V-S中頂點的最短特殊路徑長度。 問題變?yōu)榕c加入u前同樣的子問題。 如此繼續(xù)，由歸納可知當(dāng)V-S為空時，dist數(shù)組中將存放所有從源到該頂點的最短路徑。

4.3單源最短路徑voiddijkstra(intv,floata[][],floatdist[],intprev[]){intn=dist.length-1;boolean[]s=newboolean[n+1]; if(v<1||v>n)return; for(i=1;i<=n;i++) { dist[i]=a[v][i];s[i]=false; if(dist[i]==MAX_VALUE) prev[i]=0; else prev[i]=v; } dist[v]=0;s[v]=true; for(i=1;i<n;i++){ u=v;temp=MAX_VALUE; for(j=1;j<=n;j++) if((!s[j])&&(dist[j]<temp)){ u=j;temp=dist[j];} s[u]=true; for(j=1;j<n;j++) if((!s[j])&&(a[u][j]<MAX_VALUE)) if(dist[u]+a[u][j]<dist[j]){dist[j]=dist[u]+a[u][j];prev[j]=u;} }}

輸入的帶權(quán)有向圖G=（V，E），v是源點，a是一個二維數(shù)組，a[i][j]表示邊（i，j）的權(quán)。404.3單源最短路徑計算復(fù)雜性 對于具有n個頂點和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個圖，那么Dijkstra算法的主循環(huán)體需要時間。這個循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要時間。算法的其余部分所需要時間不超過。414.4最小生成樹設(shè)G=(V,E)是無向連通帶權(quán)圖，即一個網(wǎng)絡(luò)。E的每條邊(v,w)的權(quán)為c[v][w]。如果G的一個子圖G’是一棵包含G的所有頂點的樹，則稱G’為G的生成樹。生成樹各邊權(quán)的總和稱為其耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小(優(yōu))生成樹。424.4最小生成樹最小生成樹性質(zhì) 用貪心算法設(shè)計策略可以設(shè)計出構(gòu)造最小生成樹的有效算法。本節(jié)介紹的構(gòu)造最小生成樹的Prim算法和Kruskal算法都可以看作是應(yīng)用貪心算法設(shè)計策略的例子。盡管這2個算法做貪心選擇的方式不同，它們都利用了下面的最小生成樹性質(zhì)： 設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。如果(u,v)∈E，且u∈U，v∈V-U，且在所有這樣的邊中，(u,v)的權(quán)c[u][v]最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。這個性質(zhì)有時也稱為MST性質(zhì)。

43樹的基本性質(zhì)連通無回路的圖G稱為樹。樹是點比邊多一且連通，q=p–1且連通

。樹是點比邊多一且無回路：q=p–1且無回路。樹若添條邊就有回路：G無回路，若u,v∈G且uv?E(G)，則G+uv中恰有一條回路。樹若減條邊就不連通：G連通，對?e∈E(G),G–e不連通。n個頂點的連通圖的生成樹含有n–1條邊。44求最小生成樹的思路一個很直觀的簡單想法：依次選出依據(jù)圖G的權(quán)重較輕的n–1條邊。這樣得到的n–1條邊的權(quán)重之和肯定是最小的。但是這樣是否就得到了G的一棵最小生成樹呢？不行！因為不能保證這n–1條邊構(gòu)成樹？怎樣才能保證這n–1條邊構(gòu)成樹呢？生成樹是含有n個頂點和n–1條邊的連通并且無回路的圖。45求最小生成樹的兩種策略策略一：在保證連通的前提下依次選出權(quán)重較小的n–1條邊(在實現(xiàn)中體現(xiàn)為n個頂點的選擇)。策略二：在保證無回路的前提下依次選擇權(quán)重較小的n–1條邊。Prim算法的做法Kruskal算法的做法46Prim算法基本思想：設(shè)G=(V,E)為無向連通帶權(quán)圖，令V={1,…,n}。在保證連通的前提下依次選出權(quán)重較小的n–1條邊。設(shè)置一個集合S，初始化S={1}，T=?。如果V–S中的頂點j與S中的某點i連接且(i,j)是E-T中的權(quán)重最小的邊，于是就選擇j(將j加入S)，并將(i,j)加入T中。重復(fù)執(zhí)行貪心策略，直至V–S為空。47Prim算法的示例給定一個連通帶權(quán)圖如下：1234561655536624初始時S={1}，T=?

；1第一次選擇：∵(1,3)權(quán)最小∴S={1,3}T={(1,3)}；348Prim算法的示例給定一個連通帶權(quán)圖如下：1234561655536624初始時S={1}，T=?

；136第二次選擇：∵(3,6)權(quán)最小∴S={1,3,6}，T={(1,3),(3,6)}；49Prim算法的示例給定一個連通帶權(quán)圖如下：1234561655536624初始時S={1}，T=?

；136第三次選擇：∵(6,4)權(quán)最小∴S={1,3,6,4}，T={(1,3),(3,6),(6,4)}；450Prim算法的示例給定一個連通帶權(quán)圖如下：1234561655536624初始時S={1}，T=?

；1364第四次選擇：∵(2,3)權(quán)最小∴S={1,3,6,4,2}，T={(1,3),(3,6),(6,4),(2,3)}251Prim算法的示例給定一個連通帶權(quán)圖如下：1234561655536624初始時S={1}，T=?

；13642第五次選擇：∵(5,2)權(quán)最小∴S={1,3,6,4,2,5}，T={(1,3),(3,6),(6,4),(3,2)(2,5)}552Prim算法中的數(shù)據(jù)結(jié)構(gòu)圖用鄰接矩陣C[i][j]給出，即C[i][j]為結(jié)點i到結(jié)點j的權(quán)重。為了有效地找出V–S中滿足與S中的某個點i連接且(i,j)權(quán)重最小的頂點j，對其中每個頂點j設(shè)立兩個數(shù)組closest[j]和lowcost[j]：closest[j]是S中與j最近的頂點，(closest[j],j)即為選中的邊，而lowcost[j]是相應(yīng)這條邊的權(quán)重。53Prim算法的實現(xiàn)Prim(intn,Type**c){

執(zhí)行以下操作n–1次：依據(jù)lowcost[]找出與S最近的點j并放入S；

調(diào)整lowcost[]和closest[]；}

初始化：結(jié)點1放入S；并初始化lowcost[]和closest[]；54Prim算法的實現(xiàn)Prim(intn,Type**c){

執(zhí)行以下操作n–1次：intj=1;s[j]=true;for(inti=2;i<=n;i++){s[i]=false;closest[i]=1;lowcost[i]=c[1][i];}依據(jù)lowcost[]找出與S最近的點j并放入S；

調(diào)整lowcost[]和closest[]；}將結(jié)點1放入S中其余結(jié)點都不在S中且與S的最近距離是與結(jié)點1的距離。55Prim算法的實現(xiàn)Prim(intn,Type**c){intj=1;s[j]=true;for(inti=2;i<=n;i++){s[i]=false;closest[i]=1;lowcost[i]=c[1][i];}

調(diào)整lowcost[]和closest[]；}for(inti=1;i<n;i++){min=inf;for(intk=2;k<=n;k++)if(lowcost[k]<min&&!s[k]){min=lowcost[k];j=k;}s[j]=true;依據(jù)lowcost[]找出與S最近的點j并放入S。56Prim算法的實現(xiàn)Prim(intn,Type**c){intj=1;s[j]=true;for(inti=2;i<=n;i++){s[i]=false;closest[i]=1;lowcost[i]=c[1][i];}for(inti=1;i<n;i++){min=inf;for(intk=2;k<=n;k++)if(lowcost[k]<min&&!s[k]){min=lowcost[k];j=k;}s[j]=true;s中僅加入了一個新成員j，因此只需要依據(jù)結(jié)點j調(diào)整lowcost[]和closest[]；}57Prim算法的實現(xiàn)Prim(intn,Type**c){intj=1;s[j]=true;for(inti=2;i<=n;i++){s[i]=false;closest[i]=1;lowcost[i]=c[1][i];}for(inti=1;i<n;i++){min=inf;for(intk=2;k<=n;k++)if(lowcost[k]<min&&!s[k]){min=lowcost[k];j=k;}s[j]=true;for(intk=2;k<=n;k++){if(c[j][k]<lowcost[k]&&!s[k]){lowcost[k]=c[j][k];closest[k]=j;}}}58Kruskal算法基本思想：在保證無回路的前提下依次選出權(quán)重較小的n–1條邊。具體做法：若(i,j)是E中尚未被選的邊中權(quán)重最小的，且(i,j)不會與已經(jīng)選擇的邊構(gòu)成回路，于是就選擇(i,j)。問題：如何知道(i,j)不會造成回路？59Kruskal算法基本思想：在保證無回路的前提下依次選出權(quán)重較小的n–1條邊。具體做法：若(i,j)是E中尚未被選的邊中權(quán)重最小的，且(i,j)不會與已經(jīng)選擇的邊構(gòu)成回路，于是就選擇(i,j)。若邊(i,j)的端點i和j屬于同一個連通分支，則選擇(i,j)造成回路，否則不造成回路。初始時將圖的n個頂點看成n個孤立分支。60Kruskal算法的數(shù)據(jù)結(jié)構(gòu)數(shù)組e[][]表示圖的邊，e[i][u]、e[i][v]和e[i][w]分別表示邊i的兩個端點及其權(quán)重。函數(shù)Sort(e,w)對數(shù)組e按權(quán)重w排序。一個連通分支中的頂點表示為一個集合。函數(shù)Initialize(n)將每個頂點作為一個集合。函數(shù)Find(u)給出頂點u所在的集合。函數(shù)Union(a,b)給出集合a和集合b的并集。重載算符!=判斷集合的不相等。61Kruskal算法的實現(xiàn)Kruskal(intn,**e){Sort(e,w);initialize(n);k=1;j=1;while(k<n){a=Find(e[j][u]);b=Find(e[j][v]);if(a!=b){t[k++]=j;Union(a,b);}j++;}}將邊按權(quán)重從小到大排序。初始時每個頂點為一個集合。k累計已選的邊數(shù)，j為邊在e中序號，從權(quán)重最小的邊開始選取。選擇了n–1條邊后終止循環(huán)。找出第j條邊兩端點所在集合。若兩端點屬于不同集合，則將第j條邊放入樹中并把這兩個集合合并。繼續(xù)考察下一條邊。62Kruskal算法的例子1234561655536624131462253364145235345126356566初始時為6個孤立點。123456uvw63Kruskal算法的例子1234561655536624131462253364145235345126356566123456選擇了邊1，于是1、3點合并為同一個集合?！蘵vw64Kruskal算法的例子1234561655536624131462253364145235345126356566123456√選擇了邊2，于是4、6點合并為同一個集合?！蘵vw65Kruskal算法的例子1234561655536624131462253364145235345126356566123456√√uvw選擇了邊3，于是2、5點合并為同一個集合?！?6Kruskal算法的例子1234561655536624131462253364145235345126356566123456√√uvw√選擇了邊4，于是1、3、4、6點合并為同一集合?！?7Kruskal算法的例子1234561655536624131462253364145235345126356566123456√√uvw√√考察邊5，因為1、4點屬于同一個集合，被放棄?！?8Kruskal算法的例子1234561655536624131462253364145235345126356566123456√√uvw√√×選擇了邊5，于是1、3、4、6、2、5點屬于一個集合?！?9Kruskal算法的例子1234561655536624131462253364145235345126356566123456√√uvw√√×√已經(jīng)選擇了n–1條邊，算法結(jié)束。結(jié)果如圖所示。70Prim與Kruskal算法的復(fù)雜性Prim算法為兩重循環(huán)，外層循環(huán)為n次，內(nèi)層循環(huán)為O(n)，其復(fù)雜性為O(n2)。Kruskal算法中，設(shè)邊數(shù)為e