第4章貪心算法

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

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

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

該問(wèn)題要求高效地安排一系列爭(zhēng)用某一公共資源的活動(dòng)。

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

。如果選擇了活動(dòng)i，則它在半開(kāi)時(shí)間區(qū)間[si,fi)內(nèi)占用資源。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動(dòng)i與活動(dòng)j是相容的。也就是說(shuō)，當(dāng)si≥fj或sj≥fi時(shí)，活動(dòng)i與活動(dòng)j相容。74.1活動(dòng)安排問(wèn)題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;}在下面所給出的解活動(dòng)安排問(wèn)題的貪心算法greedySelector:各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組s和f中且按結(jié)束時(shí)間的非減序排列

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

例如，對(duì)右圖中的有向圖，應(yīng)用Dijkstra算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑的過(guò)程列在下頁(yè)的表中。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算法的迭代過(guò)程：2.正確性證明 1)貪心選擇性質(zhì) 貪心選擇：從V-S中選擇具有最短特殊路徑長(zhǎng)度的頂點(diǎn)u，從而確定源點(diǎn)到u的最短路徑長(zhǎng)度dist[u]。 這種選擇為什么導(dǎo)致最優(yōu)解？即為什么從源到u沒(méi)有更短的其它路徑呢？4.3單源最短路徑2.正確性證明 1)貪心選擇性質(zhì) 反證法：若存在一條從源到u且長(zhǎng)度比dist[u]更短的路。設(shè)這條路初次走出S之外到達(dá)的頂點(diǎn)為x∈V-S，然后徘徊于S內(nèi)外若干次，最后離開(kā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ì) 即在作出貪心選擇后，如何保證剩余的問(wèn)題仍是與原問(wèn)題相似的子問(wèn)題。 關(guān)鍵是要確保dist數(shù)組在將u加入到S后仍使每個(gè)i的dist[i]是當(dāng)前最短的特殊路徑長(zhǎng)度。

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

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

4.3單源最短路徑Svixu2.正確性證明 2)最優(yōu)子結(jié)構(gòu)性質(zhì) 考慮iii)dist[u]+d(u,x)+d(x,i)－－經(jīng)過(guò)老的S到u，再?gòu)膗回到老S中某個(gè)頂點(diǎn)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中頂點(diǎn)的最短特殊路徑長(zhǎng)度。 問(wèn)題變?yōu)榕c加入u前同樣的子問(wèn)題。 如此繼續(xù)，由歸納可知當(dāng)V-S為空時(shí)，dist數(shù)組中將存放所有從源到該頂點(diǎn)的最短路徑。

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

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

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

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

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

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

；1364第四次選擇：∵(2,3)權(quán)最小∴S={1,3,6,4,2}，T={(1,3),(3,6),(6,4),(2,3)}251Prim算法的示例給定一個(gè)連通帶權(quán)圖如下：1234561655536624初始時(shí)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é)點(diǎn)i到結(jié)點(diǎn)j的權(quán)重。為了有效地找出V–S中滿足與S中的某個(gè)點(diǎn)i連接且(i,j)權(quán)重最小的頂點(diǎn)j，對(duì)其中每個(gè)頂點(diǎn)j設(shè)立兩個(gè)數(shù)組closest[j]和lowcost[j]：closest[j]是S中與j最近的頂點(diǎn)，(closest[j],j)即為選中的邊，而lowcost[j]是相應(yīng)這條邊的權(quán)重。53Prim算法的實(shí)現(xiàn)Prim(intn,Type**c){

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

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

初始化：結(jié)點(diǎn)1放入S；并初始化lowcost[]和closest[]；54Prim算法的實(shí)現(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最近的點(diǎn)j并放入S；

調(diào)整lowcost[]和closest[]；}將結(jié)點(diǎn)1放入S中其余結(jié)點(diǎn)都不在S中且與S的最近距離是與結(jié)點(diǎn)1的距離。55Prim算法的實(shí)現(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最近的點(diǎn)j并放入S。56Prim算法的實(shí)現(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中僅加入了一個(gè)新成員j，因此只需要依據(jù)結(jié)點(diǎn)j調(diào)整lowcost[]和closest[]；}57Prim算法的實(shí)現(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算法基本思想：在保證無(wú)回路的前提下依次選出權(quán)重較小的n–1條邊。具體做法：若(i,j)是E中尚未被選的邊中權(quán)重最小的，且(i,j)不會(huì)與已經(jīng)選擇的邊構(gòu)成回路，于是就選擇(i,j)。問(wèn)題：如何知道(i,j)不會(huì)造成回路？59Kruskal算法基本思想：在保證無(wú)回路的前提下依次選出權(quán)重較小的n–1條邊。具體做法：若(i,j)是E中尚未被選的邊中權(quán)重最小的，且(i,j)不會(huì)與已經(jīng)選擇的邊構(gòu)成回路，于是就選擇(i,j)。若邊(i,j)的端點(diǎn)i和j屬于同一個(gè)連通分支，則選擇(i,j)造成回路，否則不造成回路。初始時(shí)將圖的n個(gè)頂點(diǎn)看成n個(gè)孤立分支。60Kruskal算法的數(shù)據(jù)結(jié)構(gòu)數(shù)組e[][]表示圖的邊，e[i][u]、e[i][v]和e[i][w]分別表示邊i的兩個(gè)端點(diǎn)及其權(quán)重。函數(shù)Sort(e,w)對(duì)數(shù)組e按權(quán)重w排序。一個(gè)連通分支中的頂點(diǎn)表示為一個(gè)集合。函數(shù)Initialize(n)將每個(gè)頂點(diǎn)作為一個(gè)集合。函數(shù)Find(u)給出頂點(diǎn)u所在的集合。函數(shù)Union(a,b)給出集合a和集合b的并集。重載算符!=判斷集合的不相等。61Kruskal算法的實(shí)現(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)重從小到大排序。初始時(shí)每個(gè)頂點(diǎn)為一個(gè)集合。k累計(jì)已選的邊數(shù)，j為邊在e中序號(hào)，從權(quán)重最小的邊開(kāi)始選取。選擇了n–1條邊后終止循環(huán)。找出第j條邊兩端點(diǎn)所在集合。若兩端點(diǎn)屬于不同集合，則將第j條邊放入樹(shù)中并把這兩個(gè)集合合并。繼續(xù)考察下一條邊。62Kruskal算法的例子1234561655536624131462253364145235345126356566初始時(shí)為6個(gè)孤立點(diǎn)。123456uvw63Kruskal算法的例子1234561655536624131462253364145235345126356566123456選擇了邊1，于是1、3點(diǎn)合并為同一個(gè)集合?！蘵vw64Kruskal算法的例子1234561655536624131462253364145235345126356566123456√選擇了邊2，于是4、6點(diǎn)合并為同一個(gè)集合?！蘵vw65Kruskal算法的例子1234561655536624131462253364145235345126356566123456√√uvw選擇了邊3，于是2、5點(diǎn)合并為同一個(gè)集合。√66Kruskal算法的例子1234561655536624131462253364145235345126356566123456√√uvw√選擇了邊4，于是1、3、4、6點(diǎn)合并為同一集合。√67Kruskal算法的例子1234561655536624131462253364145235345126356566123456√√uvw√√考察邊5，因?yàn)?、4點(diǎn)屬于同一個(gè)集合，被放棄?！?8Kruskal算法的例子1234561655536624131462253364145235345126356566123456√√uvw√√×選擇了邊5，于是1、3、4、6、2、5點(diǎn)屬于一個(gè)集合?！?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