數據結構算法與應用語言描述13貪婪

第三部第三部 算法設計方第13章貪婪算法而不像是技術，但仍然存在一些行之有效的能夠用于解決許多問題的算法設計方法，你可以使用這些方法來設計算法，并觀察這些算法是如何工作的。一般情況下，為了獲得較好的性能，必須對算法進行細致的調整。但是在某些情況下，算法經過調整之后性能仍無法達到要求，這時就必須尋求另外的方法來求解該問題。本書的第13~17章提供了五種基本的算法設計方法：貪婪算法、分而治之算法、動態(tài)規(guī)劃、回溯和分枝定界。而其他的常用高級方法如：線性規(guī)劃、整數規(guī)劃、遺傳算法、模擬退火等則沒有提及。有關這些方法的詳細描述請參見相關書籍。本章首先引入最優(yōu)化的概念，然后介紹一種直觀的問題求解方法：貪婪算法。最后，應用該算法給出貨箱裝船問題、背包問題、拓撲排序問題、二分覆蓋問題、最短路徑問題、最小代本章及后續(xù)章節(jié)中的許多例子都是最優(yōu)化問題（optimizationproblem，每個最優(yōu)化問題都包含一組限制條件（constraint）和一個優(yōu)化函數（optimizationfunction，符合限制條件的問題求解方案稱為可行解（feasiblesolution），使優(yōu)化函數取得最佳值的可行解稱為最優(yōu)解solutioni例13-1[渴嬰問題]有一個非?？实?、聰明的小嬰兒，她可能得到的東西包括一杯水、一桶牛奶、多罐不同種類的果汁、許多不同的裝在瓶子或罐子中的蘇打水，即嬰兒可得到n種不同的飲料。根據以前關于這n種飲料的不同體驗，此嬰兒知道這其中某些飲料更合自己的胃口，因1盎司第i種飲料，對它作出相對評價，將一個數值s作為滿意度賦予第i種飲料。iaai是第i種飲料的總量（以盎司為單位），而此嬰兒需要t盎司的飲料來解渴，那么，需要飲用

n找到一組實數x（1≤i≤n，使sx最大，并滿足：x=t及0≤x≤a i=1i

i=1 需要的是：如果a<t，則不可能找到問題的求解方案，因為即使喝光所有的飲料i=1對上述問題精確的數學描述明確地了程序必須完成的工作，根據這些數學，可以對輸入/輸出作如下形式的描述：輸入：n，t，s，a（其中1≤i≤n，n為整數，t、s、a為正實數 輸出：實數x（1≤i≤n，使sx最大且x=t（0≤x≤a。如果ati

i=1in

i=1 i=1n在這個問題中，限制條件是x=t且0≤x≤a，1≤i≤nsxi=1

i=1i制條件的一組實數x都是可行解，而使sx i=1ii例13-2[裝載問題]有一艘大船準備用來裝載貨物。所有待裝貨物都裝在貨箱中且所有貨箱的大小都一樣，但貨箱的重量都各不相同。設第i個貨箱的重量為w（1≤i≤n，而貨船的最大載i 這個問題可以作為最優(yōu)化問題進行描述：設存在一組變量x，其可能取值為0或1。如x為0，則貨箱i將不被裝上船；如x為1，則貨箱i nwx≤c且n

{i=1i i=1n滿足限制條件的每一組x都是一個可行解，能使x i=1 [最小代價通訊網絡]這個問題曾在例12-2介紹過。城市及城市之間所有可能的通信連接（greedymethod）中采用逐步構造最優(yōu)解的方法。在每個階段，都作出一個看上去最優(yōu)的決策（在一定的標準下。決策一旦作出，就不可再更改。作出貪婪決策的依據稱（greedycriterion。例13-4[找零錢]一個小孩買了價值少于1的糖，并將1的錢交給售貨員。售貨員希25美分、10美分、5美分、及1美分的硬幣。售貨員分步驟組成要找的零錢數，每次加入一個硬幣。選擇硬幣時所采用的貪婪準則如下：每一次選擇應使零錢數盡量增大。為保證解法的可行性（即：所給的零錢等于要找的零錢數，所選擇的硬幣不應使零錢總數超過最終所需的數目。假設需要找給小孩67美分，首先入選的是兩枚25美分的硬幣，第三枚入選的不能是25美分6美分，第三枚應選擇1后是1貪婪算法有種的傾向，在找零錢時告訴們應使找出的硬幣數目最少（至少是接近最少的數目（1。例13-5[機器調度]現有n的開始時間為s，完成時間為f，s<f。[s,f]為處理任務i的時間范圍。兩個任務i，j 指個務時范間，并指i，j的起點或終點重合。例如：區(qū)間[1，4]與區(qū)間[2，4]，而與區(qū)間[4，7]不。一個可行任務分配是指在分配中沒有兩件的任務分配給同一臺機器。因此，在可行的分配中每臺機器在任何時刻最多只處理一個任務。最優(yōu)分配是指使用的機器最少的可行分配方案。假設有n=7件任務，標號為a到g。它們的開始與完成時間如圖13-1a所示。若將任務a機器M1，任務b分給機器M2...，任務g分給機器M7，這種分配是可行的分配，共使用了七臺機器。但它不是最優(yōu)分配，因為有其他分配方案可使利用的機器數目更少，例如：可以將任務a、b、d分配給同一臺機器，則機器的數目降為五臺。一種獲得最優(yōu)分配的貪婪方法是逐步分配任務。每步分配一件任務，且按任務開始時間的非遞減次序進行分配。若已經至少有一件任務分配給某臺機器，則稱這臺機器是舊的；若機器非舊，則它是新的。在選擇機器時，采用以下貪婪準則：根據欲分配任務的開始時間，若此時有舊的機器可用，則將任務分給舊的機器。否則，將任務分配給一臺新的機器。任任完時 圖13-1任務及三臺機器a7個任務b)調根據例子中的數據，貪婪算法共分為n=7步，任務分配的順序為a、f、b、c、g、e、d。第（如圖13-1b所示。在第二步，考慮任務f。由于當f啟動時舊機器仍處于忙狀態(tài)，因此將fb給一臺新機器(設為M2)。第三步考慮任務b,由于舊機器M1在S=3時刻已處于閑狀態(tài)，因此將b分配給M1M1下一次可用時刻變成fb=7，M2的可用時刻變成ff=5。第四步，考慮任務c。由于沒有舊機器在Sc=4時刻可用，因此將c分配給一臺新機器（M3），這臺機器下一次可用時間為fc=7。第五步考慮任務g，將其分配給機器M2，第六步將任務e分配給機器M1,最后在第七步，任務2分配給機器M3（注意：任務d也可分配給機器M2。性為O(nlogn)的貪婪算法：首先采用一個復雜性為O(nlogn)的排序算法（如堆排序）按Si的遞 [最短路徑]給出一個如圖13-2所示的有向網絡，路徑的長度定義為路徑所經過的各邊的耗費之和。要求找一條從初始頂點s到達目的頂點d的最短路徑。圖13-2q，且頂點q并不是目的頂點d。加入下一個頂點所采用的貪婪準則為：選擇離q最近且目前不在路132中希望構造從頂點1到頂點511到達頂點，長度僅為2個單位，從頂點34，從頂點4到達頂點2達目的頂點5,3,,,，其長度為101到1，4，5的長度為6。根據上面三個例子，回想一下前幾所的一些用，其中有幾種算法也是貪婪算法。，9.5.3節(jié)中的樹算法，用n-1步來建立最小外部路徑的二叉樹，每一步都將兩棵二叉樹合并為一棵，算法中所使用的貪婪準則為：從可用的二叉樹中選出權重最小的兩棵。9.5.2節(jié)的LPTn步來調度n個作業(yè)。首先將作業(yè)按時間長短排序，然后在每一步中為一個任務分配一臺機器。選擇機器所利用的貪婪準則為：使目前的調度時間最短。將新作業(yè)調度到最先完成的機器上（即最先空閑的機器。注意到在9.5.2節(jié)中的機器調度問題中，貪婪算法并不能保證最優(yōu)，然而，那是一種的傾向且一般情況下結果總是非常接近最優(yōu)值。它利用的規(guī)則就是在實際環(huán)境中希望人工機器調度所采用的規(guī)則。算法并不保證得到最優(yōu)結果，但通常所得結果與最優(yōu)解相差無幾，這種算法也稱為啟發(fā)式方法（heuristics)。因此LPT9-2陳述了LPTLPT啟發(fā)式方法具有限定性能（boundedperformance。具有限定性能的啟發(fā)式方法稱為近似算法（approximationalgorithm。種啟發(fā)式方法都是貪婪啟發(fā)法，9.5.2節(jié)的LPT法也是一種貪婪啟發(fā)法。所有這些啟發(fā)式方法都具有傾向，并且在實際應用中，這些方法所得到的結果比使用9.5.2節(jié)中限定方法所得到的本章的其余部分將介紹幾種貪婪算法的應用。在有些應用中，貪婪算法所產生的結果總是最優(yōu)的解決方案。但對其他一些應用，生成的算法只是一種啟發(fā)式方法，可能是也可能不是近似算法?？紤]例13-4的找零錢問題，假設售貨員只有有限的25105美分和1美分的擴充例13-4的算法，假定售貨員除硬幣外還有50,20,10,5,和1的，顧客買價格為x和y美分的商品時所付的款為u和v美分。算法總能找出具有最少與硬幣數目編寫一個C++程序實現例13-4的找零錢算法。假設售貨員具有面值為100，20，10，51的和各種硬幣。程序可括輸入模塊（即入所買商品的價格及顧客所付的錢數，輸出模塊（輸出零錢的數目及要找的各種貨幣的數目）和計算模塊（計算怎樣給出零錢。) 實現這種算法，使其復雜性為O(nlogn)（提示：根據完成時間建立最小堆*7.例13-5的機器調度問題。假定僅有一臺機器可用，那么將選擇最大數量的任務在這臺機器上執(zhí)行。例如，所選擇的最大任務集合為{a,be}。解決這種任務選擇問題的貪婪算法可按步驟選擇任務，每步選擇一個任務，其貪婪準則如下：從剩下的任務中選擇具有最小的完成時間且不會與現有任的任務。實現該算法，其復雜性應為O(nlogn)（提示：采用一個完成時間的最小堆 例13-7假設n=8,[w,...w]=[100,200,50,90,150,50,20,80],c=400。利用貪婪算法時，所 i 箱的順序為7,3,6,8,4,1,5,2。貨箱7,3,6,8,4,1的總重量為390個單位且已被裝載，剩下的裝載能力為1[x,...,x]=[1,0,1,1,0,1,1,1]且x=i 定理13-1證明x=[x,...,x] 令yy,...,y]x≥y i=1 i=1i序：即wi

（1≤i≤n且y大于等于未轉化前的值，最后便可證明x≥yi=1 i=1ij=1根據貪婪算法的工作過程，可知在[0,n]的范圍內有一個k，使得xi=1,i≤k且xi=0,i>k 找[1,n]范圍內最小的整數j，使得x≠y。若沒有這樣的j存在，則xy。如果有這樣的j i=1ii=1 在，則j≤k，否則y就不是一個可行解，因為x≠y，x=1且y=0。令y=1，若結果得到的y不是可行解，則在[j+1,n]范圍內必有一個l使得y=1。令y=0，由于w 而且，得到的新y至少與原來的y具有相同數目的1經過數次這種轉化，可將y轉化為x。由于每次轉化產生的新y至少與前一個y具有相同數目的1，因此x至少與初始的y具有相同的數目1。貨箱裝載算法的C++代碼實現見程序13-1。由于貪婪算法按貨箱重量遞增的順序裝載，程序13-1首先利用間接尋址排序函數IndirectSort（見3.節(jié)間接尋址的定義，O(nlogn)（也可利用9.5.1節(jié)的堆排序及第14章的歸并排序，算法其余部分所需時間為O(n)，因此程序13-1的總的復雜性為O(nlogn)。程序13-1temte<classvoidContainerLoading(intx[],Tw[],Tc,int{//貨箱裝船問題的貪婪算//x[i]=1當且僅當貨箱i被裝載c是船的容量,w是貨箱的重//對重量按間接尋址方式排t是間接尋址int*t=newint[n+1];IndirectSort(w,t,n);//此時,w[t[i]]<=w[t[i+1]],//初始化for(inti=1;i<=n;i++)x[i]=0;按重量次序選擇物for(i=1;i<=n&&w[t[i]]<=c;{x[t[i]]=c-=w[t[i]];}//delete[]}在0/1背包問題中，需對容量為c的背包進行裝載。從ni件物品i的重量為i

pip

pxwx≤ci=1i i=1iix0,1](1≤i≤n)i在這個表達式中，需求出xt的值。xi=1表示物品i裝入背包中，xi=0表示物品i0/1背包問題是一個一般化的貨箱裝載問題，即每個貨箱所獲得的價值不同。貨箱裝載問題轉化為背包問題的形式為：船作為背包，貨箱作為可裝入背包的物品。例13- ii

的空間，價值為pip的目標是使車中裝載的物品價值最大。當然，所裝貨物過車的容量，且同一種物品不得0/1背包問題有好幾種貪婪策略，每個貪婪策略都采用多步過程來完成背包的裝入。在每一步過程中利用貪婪準則選擇一個物品裝入背包。一種貪婪準則為：從剩余的物品中，選出可（假設有足夠容量，然后是下一個價值最大的物品，如此繼續(xù)下去。這種策略不能保證得到最優(yōu)解。例如，考慮n=2,w=[100,10,10],p=[20,15,15],c=105。當利用價值貪婪準則時，獲得的解為x=[1,0,0]20。而最優(yōu)解為[0,1,1]，其總價值為3。 另案是重量貪婪準則是：從剩下的物品中選擇可裝入背包的重量最小的物品。雖然這種規(guī)則對于前面的例子能產生最優(yōu)解，但在一般情況下則不一定能得到最優(yōu)解?？紤]n=2,w=[10,20],p=[5,100],c=25。當利用重量貪婪策略時，獲得的解為x=[1,0],比最優(yōu)解[0,1]要差。還可以利用另一方案，價值密度p/w 裝入包的p/w值最大的物品，這種策略也不能保證得到最優(yōu)解。利用此策略試 n=3 w=[20,15,15],p=[40,25,25],c=30 我們不必因所的幾個貪婪算法都不能保證得到最優(yōu)解而沮喪，0/1背包問題是一個NP-復雜問題（見9.5.2節(jié)對NP-復雜問題的討論。對于這類問題，也許根本就不可能找到具p/w非遞（增）減的次序裝入物品不能保證得到最優(yōu)解，但它是一個上近似的解。我們希望它是一個好的啟發(fā)式算法，且大多數時候能很好地接近最后算法。在600個隨機產生的背包問題中，用這種啟發(fā)式貪婪算法來解有239題為最優(yōu)解。有583個例子與最優(yōu)解相差1%，所有60個答案與最優(yōu)解之差全在2%以內。該算法能在(nogn)時 我們也許會問，是否存在一個x(x100)，使得貪婪啟發(fā)法的結果與最優(yōu)值相差在x%以內。答案是否定的。為說明這一點，考慮例子n=2,w=[1,y],p=[10,9y],和c=y。貪婪算法結果為x=[1,0],這種方案的值為10。對于y≥10/9，最優(yōu)解的值為9y。因此，貪婪算法的值與最優(yōu)解的差對最優(yōu)解的比例為((9y-10)/9y*100)%，對于大的y，這個值趨近于100%。x%(x<100之內。首先將最多k件物品放入背包，如果這k件物品重量大于cpii pii

例13-9考慮n=4,w=[2,4,6,7],p=[6,10,12,13],c=11。當k=0時，背包按物品價值密度非遞減順序裝入，首先將物品1放入背包，然后是物品2，背包剩下的容量為5個單元，剩下的物品沒有一個合適的，因此解為x=[1,1,0,0]。此解獲得的價值為16?，F在考慮k=1時的貪婪啟發(fā)法。最初的子集為{1},{2},{3},{4}。子集{1},{2}產生與k=0時相同的結果，考慮子集{3}，置x3為1。此時還剩5個單位的容量，按價值密度非遞增順序來考慮如何利用這5個單位的容量。首先考慮物品1，它適合，因此取x1為1，這時僅剩下3個單位容量{3}x=[1,0,1,0]，獲得的價值為18。若從子集{4}開始，產生的解為x=[1,0,0,1]，獲得的價值為19?？紤]子集大小為0和1時獲得的最優(yōu)解為[1,0,0,1]。這個解是通過=1若k=2，除了考慮k<的子集，還必需考慮子集{1,2},{1,3},{1,4},{2,3},{2,4}和{3,4}從最后一個子集開始，它是不可行的，故將其拋棄，剩下的子集經求解分別得到如下結果：[1,1,0,0],[1,0,1,0],[1,0,0,1],[0,1,1,0][0,1,0,1]23，它的值比=0和這種修改后的貪婪啟發(fā)方法稱為k階優(yōu)化方法（k-optimalk件物品，并放入另外k件，獲得的結果不會比原來的好，而且用這種方式獲得的值在最優(yōu)值的(100/(k+1))%以內。當k=1時，保證最終結果在最佳值的50%以內；當k=2時，則在33.33%以內等等，這種啟發(fā)式方法的執(zhí)行時間隨k的增大而增加，需要測試的子集數目為O(nk)，每一個子集所需時間為O(n)，因此當k>0時總的時間開銷為O(nk+1)。偏差百分k0012圖13- 一個復雜的工程通?？梢苑纸獬梢唤M小任務的集合，完成這些小任務意味著整個工程的完成。例如，汽車裝配工程可分解為以下任務：將底盤放上裝配線，裝軸，將座位裝在底盤上，（ctivityOnVertex,AOV）網絡。有向圖的頂點代表任務，有向邊(i,j)表示先后關系：任務j開始前任務i必須完成。圖13-41,4）表示任務1在任務4（4,6）表示任務4在任務6開始前完成，邊（1,4）與（4,6）合起來可知任務1在任務6開始前完成，即前后關系是傳遞的。由（1,4）（1,3和（3,4）已暗示了這種關系。在很多條件下，任務的執(zhí)行是連續(xù)進行的，例如汽車裝配問題或平時的標有“需要裝配”的消費品（自行車、小孩的秋千裝置，割草機等等。我們可根據所建議的順序來裝配。在由任務建立的有向圖中，邊（i,j）i在任務j的前面，具有這種性質（topologicalorder或topologicalequences)。根據任務的有向圖建立拓撲（topologicalorting。圖13-4的任務有向圖有多種拓撲序列，其中的三種為123456，132456和215346，序列這種序列與邊（3,4）及其他邊所指示的序列相。列中加入一個頂點。利用如下貪婪準則來選擇頂點：從剩下的頂點中，選擇頂點w，使得w不存在這樣的入邊（v,w），其中頂點v不在已排好的序列結構中出現。注意到如果加入的頂點w因為頂點v必須跟隨在頂點w之后。貪婪算法的偽代碼如圖13-5所示。while循環(huán)的每次迭代代圖13-4任務有向現在用貪婪算法來求解圖13-4的有向圖。首先從一個空序列V開始，第一步選擇V的第一個頂點。此時，在有向圖中有1和22，則序列V=2，第一步完成。第二步選擇V的第圖13-4任務有向，1是唯一的候選，因此V251。第四步頂點33加入V得到V=25134和6，得V=251346。，while(true設w不存在入邊（v,w），其中頂點v不在V中把w添加到V}if(V中的頂點數少于n)算法elseV是一個拓撲序圖13-5拓撲排1)2)算法沒有失敗，V即是拓撲序列。2)即是用貪婪準則來選取下一個頂點的直接結果，1)的證 ?qq,則它沒jj k 1證 注意到當失敗時|V|<n,且沒有候選頂點能加入V中，因此至少有一個頂點q不在V中1有向圖中必包含邊（q,q）且q不在Vq是可加入V （q,q）使得

不在V中，若qq則qq

是有向圖中的一個環(huán)路；若

≠q，則必存在q

12

（q,q）是有向圖的邊且q不在V中，否則，q便是V的一個候選頂點。若q為q,q,q 何一個，則又可知有向圖含有環(huán)，因為有向圖具有有限個頂點數n，繼續(xù)利用上述方法，最后為將圖13-5用代碼來實現，必須考慮序列的描述方法，以及如何找出可加入的候選用一維數組v的候選頂點。另有一個一維數組InegreeInege[j]表示與頂點j相連的節(jié)點i的數目，其中頂點i不是（,j。當Inere[j變?yōu)?時表示j候選節(jié)點。序列V初始時為空。Inege[j]為頂點j的入度。每次向VjInere[j減1。對于有向圖13-4，開始時InDegree[1:6]=[0,0,1,3,1,3]。由于頂點1和2的InDegree值為0此它們是可加入V的候選頂點，由此，頂點1和2首先入棧。每一步，從棧中取出一個頂點將其加入VInDegree2并將其加入V，便得到了v[0]=2，和InDegree[1:6]=[0,0,1,2,0,3]。由于InDegree[5]剛剛變?yōu)?，因此將頂點5入棧。程序13-2給出了相應的C++Network的一個成員函數。而且，它對于有無的有向圖均適用。但若用于無向圖（不論其有無）將會得到錯誤的結果，因為拓撲排序是針對有向圖來定義的。為解決這個問題，利用同樣的模板來定義成員函數AdjacencyGraph,AdjacencyWGraph，LinkedGrap和LinkedWGraph。這些函數可重載NetworkTpological函數返回true；若輸入的有向圖無拓撲序列則返回false。當找到拓撲序列時，將其返回到v[0:n-1中。Network:Topologicalw第一和第三個for循環(huán)的時間開銷為(n)。若使用（耗費）鄰接矩陣,則第二個for循環(huán)所用的時間為(n2)；若使用鄰接鏈表,則所用時間為(n+e)。在兩個嵌套的while循環(huán)中，外層循環(huán)需執(zhí)行n次，每次將頂點w加入到v中，并初始化內層while循環(huán)。使用鄰接矩陣時，內層while循環(huán)對于每個頂點w需花費(n)的時間；若利用鄰接鏈表，則這個循環(huán)需花費dout的時間，因此，內層while循環(huán)的時間開銷為(n2)或(n+e)。所以，若利用鄰接矩陣，程序13-2的時間復雜性為(n2)，若利用鄰接鏈表則為(n+e)。w程序13-2boolNetwork::Topological(int{//計算有向圖中頂點的拓撲次//如果找到了一個拓撲次序，則返回true，此時，在v[0:n-1]中記錄拓撲次//如果不存在拓撲次序，則返回falseintn=Vertices();int*InDegree=newint[n+1];InitializePos();//圖遍歷器數組forinti1ini初始化InDegree[i]=for(i=1;i<=n;i++){//從i出發(fā)的intu=Begin(i);while(u){u=}//把入度為０的頂點壓入堆LinkedStack<int>S;for(i=1;i<=n;if(!InDegree[i])//產生拓撲次i=0;//v的游while(!S.IsEmpty()){//從堆棧中選擇intw; //下一個頂點v[i++]=intu=Begin(w);whileu修改入度InDegree[u]--if(!InDegree[u])S.Add(u);u=NextVertex(w);}}delete[]InDegree;return(i==n);}二分圖（見例12-3）是一個無向圖，它的n個頂點可二分為集合A和集合B，且同一集合中當且僅當B中的每個頂點至少與AA的一個子集A覆蓋集合B（或簡單地說，A'是一個覆蓋。覆蓋A'的大小即為A'中的頂點數目。當且僅當A'是覆蓋B的子集中最小的時，A'為最小覆蓋。 如圖13-6所示的具有17個頂點的二分圖，A={1,2,3,16,17}和B={4,5,6,7,8,10,11,12,13,14,15}，子集A'={1,16,17}是B圖13-6例13-10所使用的在二分圖中尋找最小覆蓋的問題為二分覆蓋（bipartite-cover問題。在例12-3小覆蓋是很有用的，因為它能解決“在會議中使用最少的翻譯人員進行翻譯”這一類的問題。二分覆蓋問題類似于集合覆蓋（set-cover）問題。在集合覆蓋問題中給出了k個集合S={S,S覆蓋，?,S}，每個集合S中的元素均是全集U中的成員。當且僅當S=U時，S的子集 覆蓋， iS'

U 中的集合數目即為覆蓋的大小。當且僅當沒有能覆蓋U的更小的集合時，稱S'為最小覆蓋?？梢詫⒓细采w問題轉化為二分覆蓋問題（反之亦然），即用A的頂點來表示S,?,S，B中的頂點代表USUA與B 例13-11令S={S，...，S},U={4，5，...，15},S={4，6，7，8，9，13}，S S={8，10，12，14，15}，S={5，6，8，12，14，15}，S={4，9，10，11}。S'={S，S，S 是一個大小為3的覆蓋，沒有更小的覆蓋， 即為最小覆蓋。這個集合覆蓋問題可映射為圖13- 的二分圖，即用頂點1，2，3，16和17分別表示集合S，S，S，S 集合覆蓋問題為NP是NP-復雜問題。因此可能無法找到一個快速的算法來解決它，但是可以利用貪婪算法尋找一A'，每一步選擇A中的一個頂點加入覆蓋。頂點的選擇利用貪婪準則：從A中選取能覆蓋中還未被覆蓋的元素數目最多的頂點。 圖13-6所示的二分圖，初始化A'=且B中沒有頂點被覆蓋，頂點1和16均能覆蓋B中的六個頂點，頂點3覆蓋五個，頂點2和17分別覆蓋四個。因此，在第一步往A'中加入頂點1或16，若加入頂點16，則它覆蓋的頂點為{5,6,8,12,14,15}，未覆蓋的頂點為{4,7,9,10,11,13}。頂點1能覆蓋其中四個頂點（{4,7,9,13}，頂點2覆蓋一個({4})，頂點3覆蓋一個（{10}，頂點16覆蓋零個，頂點17覆蓋四個{4,9,10,11}。下一步可選擇1或17加入A'。若選擇頂點1，則頂點{10,11}仍然未被覆蓋，此時頂點1，2，16不覆蓋其中任意一個，頂點3覆蓋一個，頂點17覆蓋兩個，因此選擇頂點17，至此所有頂點已被覆蓋，得A'={16,1,17}。A'A' 的頂點可被覆蓋圖13-7貪婪覆蓋啟發(fā)式方法的偽代為實現圖13-7的算法，需要選擇A'的描述方法及考慮如何記錄A點所能覆蓋的B中未覆蓋節(jié)點的數目。由于對集合A'僅使用加法運算，則可用一維整型數組C來描述A'，用m來記錄A'中元素個數。將A'中的成員記錄在C[0:m-1]中。對于A中頂點i，令Newi為i所能覆蓋的BNewii點。由于一些原來未被覆蓋的頂點現在被覆蓋了，因此還要修改各Newi檢查B中最近一次被V覆蓋的頂點，令j為這樣的一個頂點，則A中所有覆蓋j的頂點的New值均 圖13-6，初始時(New,New,New,New,

iii第一步選擇頂點16，為更新Nw的值檢查,68,2,14和15。當檢查頂點5時，將頂點2和1的Nw值分別減，因為頂點5不再是被頂點2和6時，頂點1,2和1的相應值分別減1；同樣，檢查頂點時，，2，3和16的值分別減ew（4，1，0，4。下一iii步選擇頂點1，被覆蓋的頂點為4，7，9和13；檢查頂點4時，New,New,和New的值減 1檢查頂點7時，New的值減1，因為頂點1是覆蓋71i為了實現頂點選取的過程，需要知道New的值及已被覆蓋的頂點?？衫靡粋€二維數組來達到這個目的，New是一個整型數組，New[i]即等于Newi，且cov為一個布爾數組。若頂點iim=0m=0;//當前覆蓋的大對于A中的所有i，New[]=Degree[]對于中的所有，Cov[]=fasewhe(對于A中的某些iNew[]>0)for(所有鄰接于v的頂點{if(!Cov[j]){Cov[j]=對于所有鄰接于j的頂點，使其New[k]減if有些頂點未被覆蓋)失else找到一個覆圖13-8圖13-7更新New的時間為O(e)，其中e為二分圖中邊的數目。若使用鄰接矩陣，則需花(n2)的時間來尋找圖中的邊，若用鄰接鏈表，則需(n+e)的時間。實際更新時間根據描述方法的不同為O(n2)或O(n+e)。逐步選擇頂點所需時間為(SizeOfA)，其中SizeOfA=|A|。因為A的所有頂點都有可能被選擇，因此所需步驟數為OSizeOfA)算法總的復雜性為OSizeOfA2n2On2或O(SizeOfA2+n+e)。i通過使用有序數組New、最大堆或最大選擇樹（maxselectiontree）可將每步選取頂點viii

序，則這種排序所需時間為(SizeOfB)(SizeOfB=|B|)（見3.8.1節(jié)箱子排序。由于一SizeOfB比SizeOfA大得多，因此有序數組并不總能提高性能。New值的變化，可以在每次New值減1時進行重建。這種減法操作可引起被減的New值最多在堆中向下移一層，因此這種重建對于每次New值減1需(1)的時間，總共的減操作數目為O(e)。因此在算法的所有步驟中，維持最大堆僅需O(e)的時間，因而利用最大堆時覆蓋算法的總復雜性為O(n2)或O(n+e)。若利用最大選擇樹，每次更新New值時需要重建選擇樹，所需時間為(logSizeOfA)。重建的最好時機是在每步結束時，而不是在每次New值減1時，需要重建的次數為O(e)，因此總的重建時間為O(elogSizeOfA)，這個時間比最大堆的重建時間長一些。然而，通過維持具有相同New值的頂點箱子，也可獲得和利用最大堆時相同的時間限制。由于New的取值范圍為0到SieOfB，需要SieOfB+1個箱子，箱子i是一個雙向鏈表，所有New值為i的頂點。在某一步結束時，假如New[6]12變到4，則需要將它從第12個箱子。利用模擬指針及一個節(jié)點數組node（node[i]i，node[i].left和node[i].right為雙向鏈表指針，可將頂點6從第12個箱子移到第4個箱子，從第12node[0]并將其插入第4個箱子。利用這種箱子模式，可得覆蓋啟發(fā)式算法的復雜性為O(n2)或O(n+e)（取決于利用鄰接矩陣還是線性表來描述圖。為了實現上述雙向箱子，圖13-9定義了類Undirected的私有成員。NodeType是一個具有私有整型成員left和right的類，它的數據類型是雙向鏈表節(jié)點，程序13-3給出了Undirected的voidvoidCreateBins(intb,int創(chuàng)建b個空箱子和nvoidDestroyBins(){delete[]delete[]voidInsertBins(intb,int在箱子b中添加頂點voidMoveBins(intbMax,intToBin,int從當前箱子中移動頂點v到箱子intbin[i]指向代表該箱子的雙向鏈表的首節(jié)NodeTypenode[i]代 頂點i的節(jié)圖13- 實現雙向箱子所需的Undirected私有成程序13- voidUndirected::CreateBins(intb,int{//創(chuàng)建b個空箱子和n個節(jié)node=newNodeTypebin=newint//將箱子置for(inti=1;i<=b;i++)bin[i]=0;}voidUndirected::InsertBins(intb,int若b不為０，則將vbif(!b)return;//b0，不插入node[v].left=b;//添加在左端if(bin[b])node[bin[b]].left=v;node[v].right=bin[b];bin[b]=}voidUndirected::MoveBins(intbMax,intToBin,int{//將頂v從其當前所在箱子移//v的左、右節(jié)點intl=node[v].left;intrnode[v].right;//從當前箱子中刪if(r)node[r].left=if(l>bMax||bin[l]!=v)//不是最左節(jié)node[].right=elsebin[l]= l的最左添加到箱子ToBinInsertBins(ToBin,}函數CreateBinsnode和bin，node[i]表示頂點i,bin[i]指向其New值為如果b≠0，函數InsertBins將頂點v插入箱子b中。因為b是頂點v的New值，b=0意味著頂點v不能覆蓋B中當前還未被覆蓋的任何頂點，所以，在建立覆蓋時這個箱子沒有用處，故可以將其舍去。當b≠0時，頂點n加入New值為b的雙向鏈表箱子的最前面，這種加入方式需要將node[v]加入bin[b]中第一個節(jié)點的左邊。由于表的最左節(jié)點應指向它所屬的箱子，因此將它的node[v].left置為b。若箱子不空，則當前第一個節(jié)點的left指針被置為指向新節(jié)點。node[v]的右指針被置為bin[b]，其值可能為0或指向上一個首節(jié)點的指針。最后，bin[b]被更新MoveBins將頂點v從它在雙向鏈表中的當前位置移到New值為ToBin的位置上。其中存在bMax，使得對所有的箱子bin[j]都有：如j>bMax，則bin[j]為空。代碼首先確定node[v]在當node[v]，并利用InsertBins函數將其重新插入到函數的輸入參數L用于分配圖中的頂點（分配到集 A或B）。L[i]=1表示頂點i在集合A中是A中形成覆蓋的頂點。若二分圖沒有覆蓋，函數返回false；否則返回true。完整的代碼見程程序13-4構造貪婪覆boolUndirected::BipartiteCover(intL[],intC[],int&{//尋找一個二分圖覆L是輸入頂點的標號,L[i]=1當且僅當i在ＡC是一個記錄覆蓋的輸出數//如果圖中不存在覆蓋，則返回//如果圖中有一個覆蓋，則返回//m中返回覆蓋的大小;在C[0:m-1]中返回覆intn=插件結intSizeOfA=forinti1ini確定A的大小if(L[i]==1)SizeOfA++;intSizeOfB=n-CreateBins(SizeOfB,int*New=newint[n+1];//頂點i覆蓋了Ｂ中New[i]個未被覆蓋的頂點bool*Changenewbooln+1Change[i]為true當且New[i已改變bool*Cov=newbool[n+1];//Cov[i]為true當且僅當頂點i被覆蓋LinkedStack<int>初始for(i=1;i<=n;Cov[iChange[ifalse;if(L[i]==1){//i在A中New[i]=Degree(i);//i覆蓋了這么InsertBins(New[i],構造覆intcovered= //被覆蓋的頂MaxBin=SizeOfB;//可能非空的最大箱m= //Cwhile(MaxBin>0){//搜索所有箱//選擇一個頂if(bin[MaxBin 箱子不intv=bin[MaxBin];//第一個頂C[m++]= //把v加入覆intj=Begin(v),k;while(j){if(!Cov[j]){//j尚未被覆Cov[j]=true;修改NewkBegin(j);while(k){New[k]--;//j不計入在if{S.Add(k);//僅入棧一次Change[k]=true;}k=}j=while{S.Delete(k);Change[k]=false;MoveBins(SizeOfB,New[k],}elseMaxBin--}delete[]New;delete[]Change;delete[]Cov;return(covered==}程序3-4首先計算出集合A和B的大小、初始化必要的雙向鏈表結構、創(chuàng)建三個數組、初始化圖遍歷器、并創(chuàng)建一個棧。然后將數組Cv和Cane初始化為fle，并將A中的頂點根據它B為了構造覆蓋，首先按SizeOfB遞減至1的順序檢查雙向鏈表。當發(fā)現一個非空的表時，就將其第一個頂點v加入到覆蓋中，這種策略即為選擇具有最大New值的頂點。將所選擇的頂點加入覆蓋數組C并檢查B中所有與它鄰接的頂點。若頂點j與v鄰接且還未被覆蓋，則將Cov[j]置為true，表示頂點jB中的頂點數目加1。由于j是最近被覆蓋的，所有A中與j鄰接的頂點的New值減1。下一個while循環(huán)降低這些New值并將Newv鄰接的頂點的CovNew值反映了A中每個頂點所能覆蓋的新的頂點數，然而A中的頂點由于New值被更新，處于錯誤的雙向鏈表中，下一個while循環(huán)則將這些頂點移到正確的表中。在這個問題中，給出有向圖G，它的每條邊都有一個非負的長度（耗費）a[ij]，路徑的長度即為此路徑所經過的邊的長度之和。對于給定的源頂點s，需找出從它到圖中其他任意頂點（稱為目的）的最短路徑。圖13-10a給出了一個具有五個頂點的有向圖，各邊上的數即為長度。假設源頂點s為1，從頂點1出發(fā)的最短路徑按路徑長度順序列在圖13-10b中，每條路徑前圖13-10最短路徑舉a)圖b)最短路利用E.Dijkstra發(fā)明的貪婪算法可以解決最短路徑問題，它通過分步方法求出最短路徑。每一步產生一個到達新的目的頂點的最短路徑。下一步所能達到的目的頂點通過如下貪婪準則選?。涸谶€未產生最短路徑的頂點中，選擇路徑長度最短的目的頂點。也就是說，Dijkstra的方法按路徑長度順序產生最短路徑。首先最初產生從s產生下一個最短路徑。法是在目前已產生的最短路徑中加入一條可行的最短的邊，結果產生的新路徑是原先產生的最短路徑加上一條邊。這種策略并不總是起作用。另法是在目前產生的每一條最短路徑中，考慮加入一條最短的邊，再從所有這些邊中先選擇最短的，這種策略即是Dijkstra算法?？梢则炞C按長度順序產生最短路徑時，下一條最短路徑總是由一條已產生的最短路徑加上一條邊形成。實際上，下一條最短路徑總是由已產生的最短路徑再擴充一條最短的邊得到的，13-10中，b中第二條路徑是第一條路徑擴充一條邊形成的；第三條路徑則是第二條路徑擴充一條邊；第四條路徑是第一條路徑擴充一條邊；第五條路徑是第三條路徑擴充一條邊。通過上述觀察可用一種簡便的方法來最短路徑?？梢岳脭到Mp，p[i]給出從s到達i的路徑中頂點i前面的那個頂點。在本例中p[1:5]=[0,1,1,3,4]。從s到頂點i的路徑可反向創(chuàng)建。從i出發(fā)按p[i],p[p[i]],p[p[p[i]]],?的順序，直到到達頂點s或0。在本例中，如果從i=5開始，則頂點序列為p[i]=4,p[4]=3,p[3]=1=s，因此路徑為1,3,4,5。為能方便地按長度遞增的順序產生最短路徑，定義di]為在已產生的最短路徑中加入一條最短邊的長度，從而使得擴充的路徑到達頂點i。最初，僅有從s到s的一條長度為0的路徑，這時對于每個頂點，d[]等于a[][i（ad值最小的即為下一條路徑的終點。當獲得一條新的最短路徑后，由于新的最短路徑可能會產生更小的d值，因此有些頂點的值可能會發(fā)生綜上所述，可以得到圖13-11所示的偽代碼，1)將與s鄰接的所有頂點的p初始化為s，這s到i的最短路徑，即是由s需要根據路徑的擴充邊來更新d的值。初始化初始化d[i]=a[s][i對于鄰接于s的所有頂點，置p[i]=s,對于其余的頂點置p[i]=0；對于p[]≠0的所有頂點建立表。若L為空，終止，否則轉至3)從L中刪除d值最小的頂點對于與i鄰接的所有還未到達的j，更新dj]值為min{dj],d[i]+a[ij]}；若dj]發(fā)生了變化且j還未在L中，則置p[j]=1，并將j加入L，轉至2。圖13-11最短路徑算法的描我們需要為未到達的頂點列表L選擇一個數據結構。從L中可以選出dL用最小堆（見9.3節(jié)），種取在數間完。于)的執(zhí)行次數為O(n)，所以所需時間為O(nlogn)。由于擴充一條邊產生新的最短路徑時，可能使未到達的頂點產生更小的d值，所以在4)中可能需要改變一些d值。雖然算法中的減操作并不是標準的最小堆操作，但它能在對數時間內完成。由于執(zhí)行減操作的總次數為：O(有向圖中的邊數)=O(n2)，因此執(zhí)行減操作的總時間為O(n2logn)。若L用無序的鏈表來，則3)與4)花費的時間為O(n2)，3)的每次執(zhí)行需O(|L|)=O(n)的時間，每次減操作需(1)的時間（需要減去d[j]的值，但鏈表不用改變。利用無序鏈表將圖13-11的偽代碼細化為程序13-5，其中使用了Chain(見程序3-8)和 tor類（見程序3-18。程序13- temte<classvoidAdjacencyWDigraph<T>::ShortestPaths(ints,Td[],int{//尋找從頂點s出發(fā)的最短路徑,在d中返回最短距//在p中返回前繼頂if(s1||sn)throwOutOfBounds();Chain<intL路徑可到達頂點的列表ChainItor<int>I;//初始化d,p,for(inti=1;i<=n;i++){d[i]=if(d[i]==NoEdge)p[i]=0;else{p[i]=s;}//更新d,while(!L.IsEmpty()){//尋找具有最小d的頂點int*v=int*w=I.Next();while(w){if(d[*w]<d[*v])v=w=//從L中刪除通向頂點v的下一最短路徑并更新inti=*v;for(intj=1;j<=n;j++)if(a[i][j]!=NoEdge&&(!p[j]d[j]>d[i]+a[i][j]))//減小d[j]=d[i]+//將j加入if(!p[j])L.Insert(0,j);p[j]=i;}}}}若NoEdge足夠大，使得沒有最短路徑的長度大于或等于NoEdge，則最后一個for循環(huán)的ifif(d[j]>d[i]+NoEdge的值應在能使d[j]+a[i][j]程序13-5的復雜性是O(n2)，任何最短路徑算法必須至少對每條邊檢查一次，因為任何一條O(e)。由于使用耗費鄰接矩陣來描述圖，僅決定哪條邊在有向圖中就需O(n2)的時間。因此，采用這種描述方法的算法需花費O(n2)的時間。不過程序13-5作了優(yōu)化（常數因子級for循環(huán)的總時間降為O(e)（因為只有與i鄰接的頂點的d值改變。從L中選擇及刪除最小距離的頂點所需總時間仍然是O(n2)。在例12-2及13-3中已過這個問。因為具有n個頂點的無向網絡G的每個生成剛好具有n-1條邊，所以問題是用某種方法選擇n-1條邊使它們形成G的最小生成樹。至少可以采用三種不同的貪婪策略來選擇這n-1條邊。這三種求解最小生成樹的貪婪算法策略是：rukl算法，rmolin算法Kruskal算法每次選擇n-1條邊，所使用的貪婪準則是：從剩下的邊中選擇一條不會產生環(huán)路的具有最小耗費的邊加入已選擇的邊的集合中。注意到所選取的邊若產生環(huán)路則不可能形成一棵生成樹。Kruskal算法分e步，其中ee條邊，每次考慮一條邊。當考慮某條邊時，若將其加入到已選邊的集合中會出現環(huán)路，則將其拋棄，否則，將它選入。圖13-12構造最小耗費生成圖13-12a中的網絡。初始時沒有任何邊被選擇。圖13-12b顯示了各節(jié)點的當前狀態(tài)。邊（1,6）是最先選入的邊，它被加入到欲構建的生成樹中，得到圖13-12c。下一步選擇邊（3，4）并將其加入樹中（如圖13-12d所示。然后考慮邊(2，7)，將它加入樹中并不會產生環(huán)路，于是便得到圖13-12e。下一步考慮邊（2，3）并將其加入樹中（如圖13-12f所示。在其余還未考慮的邊中，（7，4）具有最小耗費，因此先考慮它，將它加入正在創(chuàng)建（5，4）13-12g示。下一步考慮邊（7，5（6，5）如圖13-12所示99。圖13-13給出了Kruskal算法的在一個具有n個頂點的網絡中找到一棵最小生成樹令T為所選邊的集合，初始化=令E為網絡中邊的集合while(E≠)&&(|T|≠n-E=E-{(u,v)}//從E中刪除if((u,v)加入T中不會產生環(huán)路）將 u,v）加入}if(|T|==n-1)T是最小耗費生成圖13-13Kruskao算法的偽代13-13的貪婪算法總能建立一棵最小耗費生成1)Kruskal2)產生的生令G為任意無向圖（即G是一個無向網絡。從12.11.3節(jié)可知當且僅當一個無向圖連通時它有生成樹。而且在Kruskal算法中被（丟棄）的邊是那些會產生環(huán)路的邊。刪除連通圖環(huán)路中的一條邊所形成的圖仍是連通圖，因此如果G在開始時是連通的，則T與E中的邊總能形成通圖。也就是若G開始時是連通的，算法不會終止于E=和|T|<n-1?，F在來證明所建立的生成樹T具有最小耗費。由于G具有有限棵生成樹，所以它至少具有一棵最小生成樹。令U為這樣的一棵最小生成樹，T與U都剛好有n-1條邊。如果T=U,則T就具有最小耗費，那么不必再證明下去。因此假設T≠U，令k(k>0)為在T中而不在U中的邊的個數，當然k也是在U中而不在T中的邊的數目。通過把U變換為T來證明U與T具有相同的耗費，這種轉化可在k步內完成。每一步使在T而不在U中的邊的數目剛好減1。而且U的耗費不會因為轉化而改變。經過k步的轉化得到的UU具有相同的耗費，且轉化后UT中的邊。由此可知，T具有最小每步轉化包括從T中移一條邊e到U中，并從U中移出一條邊f。邊e與f的選取按如下方式進令e是在T中而不在U中的具有最小耗費的邊。由于k>0當把e加入U時，則會形成唯一的一條環(huán)路。令f為這條環(huán)不在T中的任意一條邊。從e與fV=U+{ef}T中恰有k-1條邊不在中出現?，F在來證明V的耗費與UV的耗費等于U的耗費加上邊e邊f的耗費。若e的耗費比f的小，則生成樹V的耗費比U的耗費小，這是不可能的。如果e的耗費高于f，在Kruskal算法中f會在e之前被考慮。由于f不在T中，Kruskal算法在考慮f能否加入T時已將f丟棄，因此f和T中耗費小于或等于f的邊共同形成環(huán)路。通過選擇e，所有這些邊均在U中，因此U肯定含有環(huán)路，但是實際上這不可能，因為U是一棵生成樹。e的代價高于f的假設將會導致。剩下的唯一的可能是e與f具有相同的耗費，由此可知V與U的耗費圖中有e條邊時，需花(e)的時間初始化堆及O(loge)的時間來選取每一條邊。邊的集合T與G中的頂點一起定義了一個由至多n個連通子圖構成的圖。用頂點集合來描述每個子圖，這些頂點集合沒有公共頂點。為了確定邊（u,v是否會產生環(huán)路，僅需檢查u,v否在同一個頂點集中（即處于同一子圖。如果是，則會形成一個環(huán)路；如果不是，則不會產生環(huán)路。因此對于頂點集使用兩個Find操作就足夠了。當一條邊包含在T中時，2Union操作。集合的Find和Union操作可利用8.10.2節(jié)的樹（以及規(guī)則和路徑壓縮）來高效地執(zhí)行。Find操作的次數最多為2e，Union操作的次數最多為n-1（若網絡是連通的，則剛好是n-1次。加上樹的初始化時間，算法中這部分的復雜性只比O(n+e)稍大一點。對集合T所執(zhí)行的唯一操作是向T中添加一條新邊。T可用數組t來實現。添加操作在數組總結上述各個部分的執(zhí)行時間，可得圖13-13算法的漸進復雜性為O(n+eloge)實利用上述數據結構，圖13-13可用C++代碼來實現。首先定義EdgeNode類（見程序13-6)，它是最小堆的元素及生成樹數組t的數據類型。程序13- temte<classT>classEdgeNode{operatorT()const{returnweight;}Tweight;//邊的高度intu,v;//邊的端點為了編寫與網絡描述無關的代碼，還定義了一個新的類UNetWork，它包含了應用于無向絡函個與Undirected類的差別在于Undirected類中的函數不要求邊，而UNetWork要求邊必須帶值。UNetWork中的成員需要利用Network類中定義的諸如Begi和Nextertex的遍歷函數。不過，新的遍歷函數不僅需要返回下一個鄰接的頂點，而且要返回到達這個頂點的邊的權值。這些遍歷函數以及有向和無向網絡的其他函數一起構成了WNetwork類見程序13-。程序13- temte<classclassWNetwork:virtualpublic{publicvirtualvoidFirst(inti,int&j,T&c)=0;virtualvoidNext(inti,int&j,T&c)=0;象Begin和extVertex一樣，可在AdjacencyWDigraph及LinkedWDigraph類中加入函數First與Next。現在AdjacencyWDigraph及LinkedWDigraph類都需要從WNetork中派生而來。由于AdjacencyWGraph類和LinkedWGraph類需要UNetwork的成員，所以這兩個類還必須從UNetWorkUNetWork::Kruskal13-8Edges()定義為Netork類的虛成員，并且把UNetork定義為EdgeNode的友元。如果沒有生成樹，函數返回fals，否則返回true。注意當返回tre時，在數組t程序13- temte<classboolUNetwork<T>::Kruskal(EdgeNode<T>{//使用Kruskal算法尋找最小耗費生成//如果不連通則返回//如果連通，則在t[0:n-2]中返回最小生成intn=Vertices();inte=Edges();InitializePos圖遍歷器EdgeNode<T*EnewEdgeNode<Te+1];intk=0; E的游標for(inti=1;i<=n;i++){//使所有邊附屬于intTFirst(i,j,while(j){j鄰接自if(ijE的邊E[++k].weight=c;E[k].u=i;E[k].v=Next(i,j,}}把邊放入最小堆MinHeap<EdgeNode<TH(1);H.Initialize(E,e,e);UnionFindU(n);//合并/搜索k=0;//此時作為t的游標while(e&&k<n-1){生成樹未完成，尚有剩余邊EdgeNode<Tx;H.DeleteMin(x最小耗費邊inta=U.Find(x.u);intbU.Find(x.vif(a!=b){//選擇邊t[k++]=}return(k==n-1);}與KruskalPrim算法通過每次選擇多條邊來創(chuàng)建最小生成樹。選擇下一條邊的貪婪準則是：從剩余的邊中，選擇一條耗費最小的邊，并且它的加入應使所有入選的邊仍是一Kruskal算法中所有入選的邊集合最終形成一個森林。Prim算法從具有一個單一頂點的樹T開始，這個頂點可以是原圖中任意一個頂點。然后往T中加入一條代價最小的邊（u,v）使T{(u,v)}仍是一棵樹，這種加邊的步驟反復循環(huán)直到T中包含n-1條邊。注意對于邊（u,v，u、v中正好有一個頂點位于T中。Prim算法的偽代碼如圖13-14所示。在偽代碼中也包含了所輸入的圖不是連通圖的可能，在這種情況下沒有生成樹。圖13-15顯示了對圖13-12a使用Prim算法的過程。把圖13-14的偽代碼細化為C++程序及其正確性的證明留作練習（練習31。////假設網絡中至少具有一個頂設T為所選擇的邊的集合，初始化設TV為已在樹中的頂點的集合，置TV={1}while(E<>)&&(|T|<>n-1)令（u,v）為最小代價邊，其中uTV,vTV（沒有這種邊）在T中加入邊（u,v）}if(|T|==n-1)T是一棵最小生成else網絡是不連通的，沒有最小生成圖13- 圖13-15Prim算法的步如果根據每個不在TV中的頂點v選擇一個頂點near(v)，使得near(v)TV且cost(v,near(v))的值是所有這樣的near(v節(jié)點中最小的，則實現Prim算法的時間復雜性為O(n2)。下一條添加到T中的邊是這樣的邊：其cost(v,near(v))最小，且vTV。Sollinn個頂點形成一個生成樹的森林。在每一步中為森林中的每棵樹選擇一條邊，這條邊剛好有一個頂點在樹中且邊的代價最小。將所選擇的邊加入要創(chuàng)建的生成樹中。注意一個森林中的兩棵樹可選擇同一條邊，因此必須多次同一條邊。當有多條邊具有相同的耗費時，兩棵樹可選擇與它們相連的不同的邊，在這種情況下，必須丟棄其中的一條邊。開始時，所選擇的邊的集合為空。若某一步結束時僅剩下一棵樹或沒有剩余的邊可供選擇時算法終止。圖13- 圖13-6給出了初始狀態(tài)為圖13-12