匯編語言13章貪心算法-2016

第13章貪心法

引論優(yōu)化問題:貪心法常用于解優(yōu)化問題。應用：（1）貨箱裝船（ContainerLoading)問題（2）背包問題（3）拓撲排序問題

(4)哈夫曼編碼問題（5）最短路徑問題（6）最小代價生成樹

(7)偶圖覆蓋問題13.1優(yōu)化問題一個優(yōu)化問題可以描述如下:（1）問題的解為一復雜的結構，例如元組形式

（2）約束條件：(結構性的約束條件)使為true的元組稱為可行解（feasiblesolution）；（3）目標函數

優(yōu)化解即指使目標函數極大化(或極小化)的可行解，對應的目標函數值稱為優(yōu)化值。例:貨箱裝船問題設有n個集裝箱,集裝箱大小一樣，第i個集裝箱的重量為wi(1≤i≤n),設船的載重量為c.試設計一裝船的方法使得裝入的集裝箱數目最多.令代表一種裝法約束條件

目標函數極大化目標函數很多優(yōu)化問題是NP－難度問題，迄今找不到它們的多項式算法。所以計算上可行的方法就是求其近似解。貪心法是求近似解的主要途徑。貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當然，希望貪心算法得到的最終結果也是整體最優(yōu)的。貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產生整體最優(yōu)解。如單源最短路經問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結果卻是最優(yōu)解的很好近似。13.2貪心算法貪心算法的基本要素對于一個具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個問題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有2個重要的性質：貪心選擇性質和最優(yōu)子結構性質。

1.貪心選擇性質所謂貪心選擇性質是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。對于一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優(yōu)解。2.最優(yōu)子結構性質當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結構性質。問題的最優(yōu)子結構性質是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征。13.2貪心法的步驟貪心法是一種多步(stage)求解的方法;每步按一種局部優(yōu)化的策略選擇解(元組)的一個分量;算法以第n步結束時構造出的對象(元組)作為問題的解.

這種局部優(yōu)化的策略又稱為“貪心標準(greedycriterion).貪心法的主要特點是：不回溯:選定一個分量后，不重試其它可能。使用局部優(yōu)化策略的主要原因是減小計算開銷.但局部優(yōu)化策略不保證得到精確優(yōu)化解，可能得到的是近似解。

特別是對NP－難度問題。不同的“貪心”策略得到不同的算法。常常采納使目標函數有最大增量的策略為貪心策略，增量是局部性概念。遺傳算法、神經網絡等等都是具有這類貪心性質的啟發(fā)式算法。

例：找零錢問題假設有四種硬幣，它們的面值分別為二角五分、一角、五分和一分?，F在要找給某顧客六角三分錢。這時，我們會不假思索地拿出2個二角五分的硬幣，1個一角的硬幣和3個一分的硬幣交給顧客。這種找硬幣方法與其他的找法相比，所拿出的硬幣個數是最少的。這里，我們下意識地使用了這樣的找硬幣算法：首先選出一個面值不超過六角三分的最大硬幣，即二角五分；然后從六角三分中減去二角五分，剩下三角八分；再選出一個面值不超過三角八分的最大硬幣，即又一個二角五分，如此一直做下去。這個找硬幣的方法實際上就是貪心算法。顧名思義，貪心算法總是作出在當前看來是最好的選擇。也就是說貪心算法并不從整體最優(yōu)上加以考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。例：活動安排問題活動安排問題要在所給的活動集合中選出最大的相容活動子集合，該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單的方法使得盡可能多的活動能兼容地使用公共資源。設有n個活動的集合E={1,2,…,n}，每個活動都要求使用同一資源，如演講會場等，同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結束時間fi,且si<fi。如果選擇了活動i，則它在半開時間區(qū)間[si,fi)內占用資源。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動i與活動j是相容的。即當si≥fj或sj≥fi時，活動i與活動j相容。貪心算法描述下面所給出活動安排問題的貪心算法greedySelector: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;}各活動的起始時間和結束時間存儲于數組s和f中且按結束時間的非減序排列由于輸入的活動以其完成時間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。算法greedySelector的效率極高。當輸入的活動已按結束時間的非減序排列，算法只需O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用min堆重排。算法復雜度為(nlogn)例：機器調度

現有n個任務和足夠多臺機器,假定任何時間一臺機器只能執(zhí)行一個任務.設任務i的開始時間為si,完成時間為fi,si<fi.[si,fi]為處理任務i的時間區(qū)間.稱兩個任務i,j

重疊是指兩個任務的時間區(qū)間有重疊.例如：區(qū)間[1,4]與區(qū)間[2,5]重疊,而與區(qū)間[4,7]不重疊.可行的任務分配是指該分配中沒有將重疊的任務分配給同一臺機器.最優(yōu)分配指占用機器數最少的可行分配.圖13-17個任務及使用三臺機器的調度a)7個任務b)調度例13.5(續(xù))按任務起始時間對任務排序并按此順序安排任務.貪心準則:盡可能使用舊(old)的機器.定義每臺用過的機器的可用時間為這臺機器上最近執(zhí)行的任務的完成時間.如果一個新任務的起始時間≥這些機器的最小可用時間則安排該任務在這臺機器上執(zhí)行;否則使用一臺新機器.使用min-堆存放每臺機器的可用時間,即此時間以后可安排新任務.算法的時間復雜度為Θ(nlogn)(排序和堆操作).貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題、機器調度問題，上述貪心算法卻總能求得整體最優(yōu)解.以機器調度問題為例進行證明證明:任何可行解使用的機器數≥最大重迭任務數;所以優(yōu)化調度使用的機器數≥最大重迭任務數.貪心解使用的機器數不超過最大重迭任務數：任何時候當算法使用一臺新機器時,當前這些機器上的任務一定是彼此重疊的.貪心算法性能例：最短路算法給定一個有向圖G,一個源節(jié)點s,目的節(jié)點d;找從s到d的一條最短路徑.從s開始選離s“最近”的下一個節(jié)點q;再從q開始找和q相鄰的且不在前面已選擇的路徑上的下一節(jié)點;重復這一過程直到遇到d節(jié)點或該路徑無法繼續(xù)延伸.貪心解不是優(yōu)化解:按貪心法找到的1到5的路徑為(1,3,4,2,5).13.3貪心算法的應用（1）貨箱裝船（ContainerLoading)問題（2）背包問題（3）拓撲排序問題

(4)哈夫曼編碼問題（5）最短路徑問題（6）最小代價生成樹

(7)偶圖覆蓋問題13.3.1Containerloading目標函數：裝載的集裝箱數目.極大化目標函數.貪心標準：在還沒裝船的集裝箱中選擇重量最小的集裝箱.按上述策略,重量最小的集裝箱先裝,依此類推.算法：首先按重量從小到大對集裝箱排序并依次裝入直到超過船的載重量.定理13.1上述貪心法產生的解是最優(yōu)解,證明如下:設貨箱裝船問題的最優(yōu)解為(y1,…,yn).如最優(yōu)解不含箱子1(y1=0),將箱子1替換優(yōu)化解中某一個箱子得到一個新的解.替換是必須的:因為如果箱子1還能裝入船中,則(y1,…,yn)不是優(yōu)化的.因為箱子1是最輕的,替換后的解仍是可行的.替換后的解裝入的箱子數等于優(yōu)化的裝箱數,所以它仍是優(yōu)化解.替換后新的優(yōu)化解和貪心解都包含箱子1.反復替換將得到一個優(yōu)化解,它等于貪心解.替換次數是有窮的.13.2.20/1背包問題0/1背包問題：設有容量c的背包和n件物品,物品i的重量為wi;假定裝入物品i獲得的效益值為pi,試給出一裝入物品的方法,使獲得的總效益值最大.集裝箱裝載問題是0/1背包問題的特例：

pi=10/1背包問題是NP－難度問題,所以任何有多項式復雜度的算法產生的解都是近似解.13.2.20/1背包問題背包問題可形式化描述如下:使用0/1數組(x1,…,xn)表示一個裝法:

xi=1表示裝物品i,

否則不裝.約束條件：目標函數：,等于裝入物品的總效益值極大化目標函數0/1背包問題0/1背包問題有多種貪心策略（1）從未裝入的物品中,選出效益值最大的物品裝入.利用這種規(guī)則，效益值最大的物品首先被裝入(假設有足夠容量),然后是下一個效益值最大的物品,如此進行下去.

注：這種策略不一定能保證得到最優(yōu)解n=3,c=105,w=[100,10,10],p=[20,15,15]

貪心解為：[1,0,0]，效益值為：20但優(yōu)化解為：[0,1,1]，效益值為30(續(xù))(2)從尚未裝入的物品中選擇重量最小的物品.雖然這一貪心法對于貨箱裝船問題能產生最優(yōu)解,但在一般情況下不一定能得到最優(yōu)解例：n=2,c=25,w=[10,20],p=[5,100](3)按密度pi/wi,從未裝的物品中選擇可裝入背包(裝入后不超過背包容量),且密度值最大的物品.

貪心解為[1,0,0],但優(yōu)化解為[0,1,1]例：c=11,w=(2,4,6,5),p=(6,10,12,9)優(yōu)化解為：x=(1,1,0,1).注：這種策略也不能保證得到最優(yōu)解例：n=3,c=30,w=[20,15,15],p=[40,25,25](續(xù))密度貪心法的偽代碼:(1)將物品按密度從大到小排序

(2)for(i=1;i<n;i++)if(物品i可裝入到背包內)xi=1(裝入)

elsexi=0(舍棄);算法的時間復雜度為O(nlogn)

(續(xù))貪心法往往不能得到精確解，貪心解與最優(yōu)解的誤差用以下比值的百分比來度量:

|優(yōu)化值-貪心解值|/優(yōu)化值*100%例：n=2,c=y,w=[1,y],p=[10,9y]

對所有y>1,貪心解的效益值＝10；當y>10/9時,優(yōu)化效益值＝9y.不管優(yōu)化值多大,貪心解的值總是10.誤差為(9y-10)/9y=1-(10/9y).對足夠大的y,誤差可達到百分之百.例13.9k-優(yōu)化算法k-優(yōu)化算法是上述密度貪心算法的改進，改進后其誤差可控制在1/(k+1)*100％之內.例如3-優(yōu)化算法的誤差為25％.k-優(yōu)化算法也要先對物品按密度從大到小排序;先將一些物品裝入背包,然后對其余物品用貪心法;預先裝入的物品數不超過k.對所有物品數不超過k的物品子集執(zhí)行上述過程,并從中找到有最大效益值的解作為k-優(yōu)化算法的解.考慮n=4,w=[2,4,6,7],p=[6,10,12,13],c=11.使用2-優(yōu)化算法如下：

當k=0時,同于前述的密度貪心法.因此解為x=[1,1,0,0],效益值為16.例13.9(續(xù)1）k

=1時,最初的子集為{1},{2},{3},{4}.子集{1},{2}產生與k=0時相同的結果考慮子集{3},置x3為1,此時背包剩余容量為5，未裝的物品為1,2,4.使用貪心法,得到的解為x=[1,0,1,0]，效益值為18.從子集{4}開始,產生的解為x=[1,0,0,1]，效益值為19.因此，k=0,1時獲得的最優(yōu)解為[1,0,0,1].

例13.9（續(xù)2）若k=2,除了考慮k<2的子集,還必需考慮子集{1,2},{1,3},{1,4},{2,3},{2,4}和{3,4}.子集{3,4}是不可行的,將其舍棄對剩下的子集求解分別得到如下結果：[1,1,0,0],[1,0,1,0],[1,0,0,1],[0,1,1,0]和[0,1,0,1]，最后一個的效益值為23。K-優(yōu)化解為[0,1,0,1],值為23例13.9結論k-優(yōu)化方法(k>0)得到的解誤差不超過

(1/(k+1))*100％當k=1時,為50%以內,即如優(yōu)化值為100,貪心法算出的值不低于50;當k=2時,為33.33%以內.算法的時間復雜度隨k

的增大而增加:需要測試的子集數目為O(nk

);每一個子集做貪心法需時間O(n);因此當k>0時總的時間開銷為O(nk+1

).600種隨機測試的統(tǒng)計結果13.3.1哈夫曼編碼問題哈夫曼編碼是廣泛地用于數據文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。哈夫曼編碼算法用字符在文件中出現的頻率表來建立一個用0，1串表示各字符的最優(yōu)表示方式。給出現頻率高的字符較短的編碼，出現頻率較低的字符以較長的編碼，可以大大縮短總碼長。例如一個包含100,000個字符的文件，各字符出現頻率不同，如下表所示。定長編碼需要300,000位，而按表中變長編碼方案，文件的總碼長為：（45×1+13×3+12×3+16×3+9×4+5×4）×1000=224,000。abcdef頻率(千次)4513121695定長碼000001010011100101變長碼010110011111011100前綴碼對每一個字符規(guī)定一個0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴，這種編碼稱為前綴碼。編碼的前綴性質可以使譯碼方法非常簡單。平均碼長定義為：使平均碼長達到最小的前綴碼編碼方案稱為給定編碼字符集C的最優(yōu)前綴碼。構造哈夫曼編碼哈夫曼提出構造最優(yōu)前綴碼的貪心算法，由此產生的編碼方案稱為哈夫曼編碼。具體算法為：（1）根據n個權值{w1，w2，…，wn}構成n棵二叉樹的集合F={T1，T2，…，Tn}，其中每棵二叉樹Ti中只有一個帶權為wi的根結點，其左右子樹均為空（2）在F中選取兩棵根結點的權值最小的樹作為左右子樹來構造一棵新的二叉樹，且置新的二叉樹的根結點的權值為其左、右子樹結點的根結點的權值之和。（3）在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中。（4）重復（2）和（3），直到F中只含一棵樹時為止。稱這棵樹為最優(yōu)二叉樹（或哈夫曼樹）。

如果約定將每個結點的左分支表示字符“0”，右分支表示字符“1”，則可以把從根結點到某葉子結點的路徑上分支字符組成的字符串作為該葉子結點的編碼。哈夫曼算法以自底向上的方式構造表示最優(yōu)前綴碼的二叉樹T。算法以|C|個葉結點開始，執(zhí)行|C|－1次的“合并”運算后產生最終所要求的樹T。算法說明統(tǒng)計編碼字符集中每一字符c的頻率f(c)。以f為鍵值的優(yōu)先隊列Q用在貪心選擇時有效地確定算法當前要合并的2棵具有最小頻率的樹。一旦2棵具有最小頻率的樹合并后，產生一棵新的樹，其頻率為合并的2棵樹的頻率之和，并將新樹插入優(yōu)先隊列Q。經過n－1次的合并后，優(yōu)先隊列中只剩下一棵樹，即所要求的樹T。算法可以用最小堆實現優(yōu)先隊列Q。初始化優(yōu)先隊列需要O(nlogn)計算時間，由于最小堆的插入和刪除運算均需O(logn)時間，n－1次的合并總共需要O(nlogn)計算時間。因此，關于n個字符的哈夫曼算法的計算時間為O(nlogn)。圖論（Graph）相關的應用問題圖的基本知識定義：一個有向圖G=(V,E)是由包含頂點和邊的有序點對組成，其中V是頂點集合，E是邊的集合.在無向圖中，G=(V,E),邊集合E由無序點對組成.在有向圖和無向圖中，|E|=O(V2)若G是連通圖，則|E|>=|V|-1,即lg(E)=Θ(lgV)鄰接矩陣(adjacencymatrix)鄰接表(adjacencylist)鄰接表的存儲復雜度為Θ(V+E),

邊稀疏時適用。13.3.2拓撲排序拓撲排序定義：任務的先后順序可用有向圖表示,稱為AOV網絡(ActivityOnVertex).有向圖的頂點代表任務,有向邊(i,j)表示先后關系:任務i完成后才能開始任務j

.根據上述AOV網絡我們要對任務進行排序使得排序序列的先后關系與AOV網定義的先后關系一致.根據任務的有向圖建立拓撲序列的過程稱為拓撲排序.13.3.2拓撲排序對有向圖的所有頂點的所有排列逐個檢驗的方法是不足取的:O(n!)的時間復雜度.貪心法從空集開始，每步產生拓撲排序序列中的一個頂點w,怎樣選擇頂點w？greedy策略:從當前尚不在拓撲排序序列的頂點中選擇一頂點w,其所有先行節(jié)點v都在已產生的拓撲序列中(或無先行頂點)并將其加入到拓撲序列中.

用減節(jié)點入度的方法確定w:入度變成0的頂點為要加到拓撲序列中的頂點.使用棧的偽代碼(1)計算每個頂點的入度(2)將入度為0的頂點入棧(3)While(棧不空){任取一入度為0的頂點放入拓撲序列中;將與其相鄰的頂點的入度減1;如有新的入度為0的頂點出現,將其放入棧中;}(4)如有剩余的頂點則該圖有環(huán)路引理13.1如果上述偽代碼表示的算法失敗,則有向圖含有環(huán)路.設V為算法結束時算法輸出的節(jié)點構成的集合證明：當失敗時|V|<n,且剩下的頂點不能加入已排好的序列V中.至少有一節(jié)點q1不在V中,和一條邊(q2,q1)且q2不在V中,否則q1可加入V中.同理,有邊(q3,q2）且q3不在V中.若q3=q1

則q1q2q3

是有向圖中的一個環(huán)路,若q3≠q1，則必存在q4,（q4,q3）是有向圖的邊且q4不在V中.否則q3應在V中.若q4為q1,q2,q3

中的任何一個,則該有向圖含有環(huán).因為有向圖有有限個節(jié)點,重復上述步驟,一定能找到一個環(huán)路.

程序13.2拓撲排序程序13.2拓撲排序（續(xù)1）程序13.2拓撲排序（續(xù)2）算法13.2的時間復雜度Θ(n2):使用鄰接矩陣;Θ(n+e):使用鄰接表;第一個for循環(huán)，初始化入度數組需O(n)時間計算入度:若使用鄰接矩陣，所用時間為O(n^2),若使用鄰接表，所用時間為O(n+e);進出棧次數:O(n);使用鄰接矩陣每步修改入度時間為O(n);使用鄰接表每步修改入度時間為O(節(jié)點的出度);總的修改入度時間為O(n^2)或O(n+e):有向圖的所有節(jié)點出度之和等于圖的邊數.13.3.3單源最短路徑任給一有向圖G,它的每條邊都有一個非負的權值a[i][j],路徑的長度定義為路徑上邊的權值之和.單源最短路問題:給定源節(jié)點s,找出從s到圖中所有其他節(jié)點(稱為目的)的最短路徑(優(yōu)化解)及其長度(優(yōu)化值)例：網絡中傳輸數據流時,要耗費網絡的帶寬和存儲資源,使用跳數少的路徑節(jié)省網絡資源.IP路由使用最短路算法(OSPF),因為IP路由表按目的節(jié)點索引(查找),所以,OSPF協(xié)議使用該算法求出網絡中目的節(jié)點到任一節(jié)點的最短路.Dijkstra’s最短路算法如果鏈路權值非負,則最短路的子路徑也是最短路,其長度小于原來路徑的長度.所以,長度較小的最短路容易找到.貪心策略:按最短路長度從小到大依次求解.Dijkstra’s最短路算法使用上述貪心策略,是圖論算法中應用最為廣泛的算法,主要原因是其計算復雜度低且容易實現.1.維護一個集合S，該集合中源節(jié)點到其他節(jié)點的最短路已知，初始時該集合為空2.從V-S集合中找一節(jié)點v，滿足源節(jié)點到該節(jié)點距離最小3.更新v的鄰節(jié)點的到源節(jié)點的距離值Dijkstra’s最短路算法基本步驟Dijkstra’s算法Dijkstra’s算法分析每個Extract-min操作的平攤代價無權圖（Unweightedgraphs）假定，對所有點對(u,v)∈E,w(u,v)=1,Dijkstra算法能否進一步改進？可使用FIFO隊列代替優(yōu)先隊列廣度優(yōu)先算法如下：廣度優(yōu)先算法例題源節(jié)點到其它所有節(jié)點的最短路若圖G=(V,E)包含負權回路，則最短路徑可能不存在。例Bellman-Ford算法：找出源節(jié)點到其它任意節(jié)點的最短路，或確定圖中包含負值環(huán)路負權環(huán)圖(Negative-weightcycles)單源最短路徑非負權重Dijkstra算法復雜度：O(E+VlgV)一般情況下：Bellman-Ford算法復雜度O(VE)多源最短路徑非負權值，Dijkstra算法復雜度O(VE+V2lgV)一般情況（權值可能為負）Bellman-Ford算法為O(V2E)或O(V4)最短路徑問題小結13.3.6最小生成樹具有n個頂點的連通的無向圖G,圖的每條邊e有一非負權值c(e),也稱為成本,求有最小成本的生成樹.每個生成樹剛好具有n-1條邊，所以問題是用某種方法選擇n-1條邊使它們形成G的最小生成樹。我們采用以下二種不同的貪心策略來選擇這n-1條邊。這二種貪心策略對應求解最小生成樹的二個算法：Kruskal’s算法，Prim’s算法。Kruskal’s算法貪心策略:每次選擇權值c(e)最小且與以前選擇的邊不構成cycle的邊e.上述策略要求按權值從小到大對邊排序.圖13.12構造最小生成樹圖13.12構造最小生成樹（續(xù)1）圖13.12構造最小生成樹（續(xù)2）圖13.13Kruskal’s算法的偽代碼算法正確性證明定理:Kruskal’s算法產生一棵最小生成樹.設T是貪心法產生的解，U是優(yōu)化解設e是屬于T但不屬于U的成本最小的邊;換言之,T中成本小于c(e)的邊都在U中.設f是{e}+U產生的環(huán)路上不在T中的一條邊,這樣的f一定存在,否則T將包含一個環(huán)路.下面用反證法證明c(f)≥c(e):T中成本小于c(e)的邊都在U中,所以f與這些邊不構成環(huán)路(這些邊都在U里);如果f的成本小于e的成本,貪心法會先于e將f加入到T中,矛盾.

（說明c(f)不小于c(e)）從U中刪除f并加入e,得到的樹U’仍是優(yōu)化的.算法實現－數據結構算法執(zhí)行過程中動態(tài)產生的子樹,反復進行union和find操作,使用下面的數據結構很有效.UNIN－FIND數據結構初始為單個頂點的集合對每條邊做2次FIND找到邊的端點所在的集合;如果在同一集合中則舍棄該條邊,否則將2個集合合并(UNION)算法可在O(n+eloge)找出最小生成樹:

邊排序:O(eloge)initializing:O(n)union-find:O(e)

Prim’s算法設A為算法執(zhí)行過程中產生的生成樹中的節(jié)點集合.初始化A包含圖中任一節(jié)點;定義V-A中節(jié)點u到A的距離key(u)為

min{c(u,v)|v∈A,(u,v)∈E}取V-A中key(u)最小的節(jié)點u,并將其加入到A;更新V-A中的節(jié)點到A的距離(key值).重復執(zhí)行上述步驟.算法實現時將V-A中的節(jié)點按key值做成一個優(yōu)先級隊列(堆)Q.每次從V-A中抽取距離最小的節(jié)點u,并修改Q中與u相鄰的節(jié)點的key值(decreasekey).該算法不要求對邊排序.算法的偽代碼如下:Prim’s算法圖13.5圖13.15Prim’s算法舉例Prim’s算法舉例（續(xù)）Prim’s算法復雜度分析復雜度分析

13.3.7偶圖覆蓋問題（二分覆蓋）偶圖是一個無向圖，它的n個頂點分為集合A和集合B，且同一集合中的任意兩個頂點無邊相連。A的一個子集A’覆蓋集合BiffB中每一頂點至少和A’中一頂點相連。覆蓋A’的大小指A’中的頂點數目。在偶圖中尋找最小覆蓋的問題稱為偶圖覆蓋(bipartite-cover)問題。

例13.10考察如圖13.6所示的具有17個頂點的二分圖，A={1,2,3,16,17}和B={4,5,6,7,8,9,10,11,12,13,14,15}，子集A’={1,16,17}是B的最小覆蓋：1覆蓋{4,6,7,8,9,13};16覆蓋{5,6,8,12,14,15};17覆蓋{4,9,10,11}圖13.6例13.10所使用的圖集合覆蓋問題偶圖覆蓋等價于集合覆蓋問題。集合覆蓋問題是NP－難度問題。集合覆蓋問題：n個集合的族F＝滿足，設為F的子族且則稱其為U的一個覆蓋集合覆蓋問題是指找包含的集合數目最小的覆蓋。

例13.11

令F={S1,

…,S5

}，U={4,5,...,15}，S1={4,6,7,8,9,13}，S2={4,5,6,8}，

S3={8,10,12,14,15}，S4={5,6,8,12,14,15}，S5={4,9,10,11}。S’={S1,S4,S5}是一個大小為3的覆蓋，沒有更小的覆蓋，S’即為最小覆蓋。這個集合覆蓋問題可變換為圖13.6的偶圖，即用頂點1，2，3，16和17分別表示集合S1，S2，S3，S4和S5，頂點j

表示集合U中的元素j，4≤j≤15。兩個問題等價，都是NP－難度問題偶圖覆蓋問題的貪心解貪心策略：選擇覆蓋B中那些尚未被覆蓋的頂點數最多的A的節(jié)點對圖13.6應用上述貪心法，得到

A'＝{1,16,17}，算法描述見圖13.7圖13.7貪心啟發(fā)式算法的偽代碼實現問題設,為i覆蓋的B中尚未被覆蓋的頂點數。為動態(tài)變化的量。需設計數據結構對其進行維護。要求：取最大的頂點i

相應修改余下頂點的New值

(見13.8的偽代碼)

圖13.8圖13.7的細化例13.13以圖13.6為例，初始：

New=[6,4,5,6,4]，選頂點16，c={16}16覆蓋B中(5,6,8,12,14,15);5,6,8與A中2相連所以New(2)修改為4-3=1;New(16)為0;

New(1)為6-2=4;New(3)為1;New(17)為4選頂點1,頂點4被覆蓋,4與2有邊相連所以New(2)值減1；6已被覆蓋;7被覆蓋,New(7)減1使用二維數組存儲New的值更新New的時間為O(e)，其中e為二分圖中邊的數目。若使用鄰接矩陣，則需要花O(n2)的時間來尋找圖中的邊若用鄰接鏈表，則需要O(n+e)的時間

逐步選擇頂點所需時間為O(SizeofA),其中SizeofA=|A|。A的所有頂點都有可能被選擇，因此，所需步驟書為O