雖然設(shè)計一個好的求解算法更像是一門藝術(shù)，而不像是技術(shù)，但仍然存在一些行之有效的能夠用于解決許多問題的算法設(shè)計方法，你可以使用這些方法來設(shè)計算法，并觀察這些算法是如何工作的。一般情況下，為了獲得較好的性能，必須對算法進(jìn)行細(xì)致的調(diào)整。但是在某些情況下，算法經(jīng)過調(diào)整之后性能仍無法達(dá)到要求，這時就必須尋求另外的方法來求解該問題。
本章首先引入最優(yōu)化的概念，然后介紹一種直觀的問題求解方法：貪婪算法。最后，應(yīng)用該算法給出貨箱裝船問題、背包問題、拓?fù)渑判騿栴}、二分覆蓋問題、最短路徑問題、最小代價生成樹等問題的求解方案。
1.1 最優(yōu)化問題
本章及后續(xù)章節(jié)中的許多例子都是最優(yōu)化問題（ optimization problem），每個最優(yōu)化問題都包含一組限制條件（ c o n s t r a i n t）和一個優(yōu)化函數(shù)（ optimization function），符合限制條件的問題求解方案稱為可行解（ feasible solution），使優(yōu)化函數(shù)取得最佳值的可行解稱為最優(yōu)解（optimal solution）。
例1-1 [ 渴嬰問題] 有一個非?？实摹⒙斆鞯男雰海赡艿玫降臇|西包括一杯水、一桶牛奶、多罐不同種類的果汁、許多不同的裝在瓶子或罐子中的蘇打水，即嬰兒可得到n 種不同的飲料。根據(jù)以前關(guān)于這n 種飲料的不同體驗(yàn)，此嬰兒知道這其中某些飲料更合自己的胃口，因此，嬰兒采取如下方法為每一種飲料賦予一個滿意度值：飲用1盎司第i 種飲料，對它作出相對評價，將一個數(shù)值si 作為滿意度賦予第i 種飲料。
通常，這個嬰兒都會盡量飲用具有最大滿意度值的飲料來最大限度地滿足她解渴的需要，但是不幸的是：具有最大滿意度值的飲料有時并沒有足夠的量來滿足此嬰兒解渴的需要。設(shè)ai是第i 種飲料的總量（以盎司為單位），而此嬰兒需要t 盎司的飲料來解渴，那么，需要飲用n種不同的飲料各多少量才能滿足嬰兒解渴的需求呢？
設(shè)各種飲料的滿意度已知。令xi 為嬰兒將要飲用的第i 種飲料的量，則需要解決的問題是：
找到一組實(shí)數(shù)xi（1≤i≤n），使n ?i = 1si xi 最大，并滿足：n ?i=1xi =t 及0≤xi≤ai 。
需要指出的是：如果n ?i = 1ai < t，則不可能找到問題的求解方案，因?yàn)榧词购裙馑械娘嬃弦膊荒苁箣雰航饪省?/P>
對上述問題精確的數(shù)學(xué)描述明確地指出了程序必須完成的工作，根據(jù)這些數(shù)學(xué)公式，可以對輸入/ 輸出作如下形式的描述：
輸入：n，t，si ，ai（其中1≤i≤n，n 為整數(shù)，t、si 、ai 為正實(shí)數(shù)）。
輸出：實(shí)數(shù)xi（1≤i≤n），使n ?i= 1si xi 最大且n ?i=1xi =t（0≤xi≤ai）。如果n ?i = 1ai <t，則輸出適當(dāng)?shù)腻e誤信息。
在這個問題中，限制條件是n ?i= 1xi =t 且0≤xi≤ai，1≤i≤n。而優(yōu)化函數(shù)是n ?i= 1si xi 。任何滿足限制條件的一組實(shí)數(shù)xi 都是可行解，而使n ?i= 1si xi 最大的可行解是最優(yōu)解。
例1-2 [裝載問題] 有一艘大船準(zhǔn)備用來裝載貨物。所有待裝貨物都裝在貨箱中且所有貨箱的大小都一樣，但貨箱的重量都各不相同。設(shè)第i 個貨箱的重量為wi（1≤i≤n），而貨船的最大載重量為c，我們的目的是在貨船上裝入最多的貨物。
這個問題可以作為最優(yōu)化問題進(jìn)行描述：設(shè)存在一組變量xi ，其可能取值為0或1。如xi 為0，則貨箱i 將不被裝上船；如xi 為1，則貨箱i 將被裝上船。我們的目的是找到一組xi ，使它滿足限制條件n ?i = 1wi xi ≤c 且x i ? {0, 1}, 1 ≤i≤n。相應(yīng)的優(yōu)化函數(shù)是n ?i= 1xi 。
滿足限制條件的每一組xi 都是一個可行解，能使n ?i= 1xi 取得最大值的方案是最優(yōu)解。
例1-3 [最小代價通訊網(wǎng)絡(luò)] 城市及城市之間所有可能的通信連接可被視作一個無向圖，圖的每條邊都被賦予一個權(quán)值，權(quán)值表示建成由這條邊所表示的通信連接所要付出的代價。包含圖中所有頂點(diǎn)（城市）的連通子圖都是一個可行解。設(shè)所有的權(quán)值都非負(fù)，則所有可能的可行解都可表示成無向圖的一組生成樹，而最優(yōu)解是其中具有最小代價的生成樹。
在這個問題中，需要選擇一個無向圖中的邊集合的子集，這個子集必須滿足如下限制條件：所有的邊構(gòu)成一個生成樹。而優(yōu)化函數(shù)是子集中所有邊的權(quán)值之和。
1.2 算法思想
在貪婪算法（greedy method）中采用逐步構(gòu)造最優(yōu)解的方法。在每個階段，都作出一個看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。決策一旦作出，就不可再更改。作出貪婪決策的依據(jù)稱為貪婪準(zhǔn)則（greedy criterion）。
例1-4 [找零錢] 一個小孩買了價值少于1美元的糖，并將1美元的錢交給售貨員。售貨員希望用數(shù)目最少的硬幣找給小孩。假設(shè)提供了數(shù)目不限的面值為2 5美分、1 0美分、5美分、及1美分的硬幣。售貨員分步驟組成要找的零錢數(shù)，每次加入一個硬幣。選擇硬幣時所采用的貪婪準(zhǔn)則如下：每一次選擇應(yīng)使零錢數(shù)盡量增大。為保證解法的可行性（即：所給的零錢等于要找的零錢數(shù)），所選擇的硬幣不應(yīng)使零錢總數(shù)超過最終所需的數(shù)目。
假設(shè)需要找給小孩6 7美分，首先入選的是兩枚2 5美分的硬幣，第三枚入選的不能是2 5美分的硬幣，否則硬幣的選擇將不可行（零錢總數(shù)超過6 7美分），第三枚應(yīng)選擇1 0美分的硬幣，然后是5美分的，最后加入兩個1美分的硬幣。
貪婪算法有種直覺的傾向，在找零錢時，直覺告訴我們應(yīng)使找出的硬幣數(shù)目最少（至少是接近最少的數(shù)目）?？梢宰C明采用上述貪婪算法找零錢時所用的硬幣數(shù)目的確最少（見練習(xí)1）。
例1-5 [機(jī)器調(diào)度] 現(xiàn)有n 件任務(wù)和無限多臺的機(jī)器，任務(wù)可以在機(jī)器上得到處理。每件任務(wù)的開始時間為si，完成時間為fi ，si < fi 。[si , fi ] 為處理任務(wù)i 的時間范圍。兩個任務(wù)i，j 重指兩個任務(wù)的時間范圍區(qū)間有重疊，而并非是指i，j 的起點(diǎn)或終點(diǎn)重合。例如：區(qū)間[ 1，4 ]與區(qū)間[ 2，4 ]重疊，而與區(qū)間[ 4，7 ]不重疊。一個可行的任務(wù)分配是指在分配中沒有兩件重疊的任務(wù)分配給同一臺機(jī)器。因此，在可行的分配中每臺機(jī)器在任何時刻最多只處理一個任務(wù)。最優(yōu)分配是指使用的機(jī)器最少的可行分配方案。
假設(shè)有n= 7件任務(wù)，標(biāo)號為a 到g。它們的開始與完成時間如圖13-1a 所示。若將任務(wù)a分給機(jī)器M1，任務(wù)b 分給機(jī)器M2，. . .，任務(wù)g 分給機(jī)器M7，這種分配是可行的分配，共使用了七臺機(jī)器。但它不是最優(yōu)分配，因?yàn)橛衅渌峙浞桨缚墒估玫臋C(jī)器數(shù)目更少，例如：可以將任務(wù)a、b、d分配給同一臺機(jī)器，則機(jī)器的數(shù)目降為五臺。
一種獲得最優(yōu)分配的貪婪方法是逐步分配任務(wù)。每步分配一件任務(wù)，且按任務(wù)開始時間的非遞減次序進(jìn)行分配。若已經(jīng)至少有一件任務(wù)分配給某臺機(jī)器，則稱這臺機(jī)器是舊的；若機(jī)器非舊，則它是新的。在選擇機(jī)器時，采用以下貪婪準(zhǔn)則：根據(jù)欲分配任務(wù)的開始時間，若此時有舊的機(jī)器可用，則將任務(wù)分給舊的機(jī)器。否則，將任務(wù)分配給一臺新的機(jī)器。 根據(jù)例子中的數(shù)據(jù)，貪婪算法共分為n = 7步，任務(wù)分配的順序?yàn)閍、f、b、c、g、e、d。第一步?jīng)]有舊機(jī)器，因此將a 分配給一臺新機(jī)器（比如M1）。這臺機(jī)器在0到2時刻處于忙狀態(tài)。在第二步，考慮任務(wù)f。由于當(dāng)f 啟動時舊機(jī)器仍處于忙狀態(tài)，因此將f 分配給一臺新機(jī)器(設(shè)為M2 )。第三步考慮任務(wù)b, 由于舊機(jī)器M1在Sb = 3時刻已處于閑狀態(tài)，因此將b分配給M1執(zhí)行，M1下一次可用時刻變成fb = 7，M2的可用時刻變成ff = 5。第四步，考慮任務(wù)c。由于沒有舊機(jī)器在Sc = 4時刻可用，因此將c 分配給一臺新機(jī)器（M3），這臺機(jī)器下一次可用時間為fc = 7。第五步考慮任務(wù)g，將其分配給機(jī)器M2，第六步將任務(wù)e 分配給機(jī)器M1, 最后在第七步，任務(wù)2分配給機(jī)器M3。（注意：任務(wù)d 也可分配給機(jī)器M2）。
上述貪婪算法能導(dǎo)致最優(yōu)機(jī)器分配的證明留作練習(xí)（練習(xí)7）?？砂慈缦路绞綄?shí)現(xiàn)一個復(fù)雜性為O (nl o gn)的貪婪算法：首先采用一個復(fù)雜性為O (nl o gn)的排序算法（如堆排序）按Si 的遞增次序排列各個任務(wù)，然后使用一個關(guān)于舊機(jī)器可用時間的最小堆。
例1-6 [最短路徑] 給出一個有向網(wǎng)絡(luò)，路徑的長度定義為路徑所經(jīng)過的各邊的耗費(fèi)之和。要求找一條從初始頂點(diǎn)s 到達(dá)目的頂點(diǎn)d 的最短路徑。
貪婪算法分步構(gòu)造這條路徑，每一步在路徑中加入一個頂點(diǎn)。假設(shè)當(dāng)前路徑已到達(dá)頂點(diǎn)q，
且頂點(diǎn)q 并不是目的頂點(diǎn)d。加入下一個頂點(diǎn)所采用的貪婪準(zhǔn)則為：選擇離q 最近且目前不在路徑中的頂點(diǎn)。
這種貪婪算法并不一定能獲得最短路徑。例如，假設(shè)在圖1 3 - 2中希望構(gòu)造從頂點(diǎn)1到頂點(diǎn)5的最短路徑，利用上述貪婪算法，從頂點(diǎn)1開始并尋找目前不在路徑中的離頂點(diǎn)1最近的頂點(diǎn)。到達(dá)頂點(diǎn)3，長度僅為2個單位，從頂點(diǎn)3可以到達(dá)的最近頂點(diǎn)為4，從頂點(diǎn)4到達(dá)頂點(diǎn)2，最后到達(dá)目的頂點(diǎn)5。所建立的路徑為1 , 3 , 4 , 2 , 5，其長度為1 0。這條路徑并不是有向圖中從1到5的最短路徑。事實(shí)上，有幾條更短的路徑存在，例如路徑1，4，5的長度為6。
根據(jù)上面三個例子，回想一下前幾章所考察的一些應(yīng)用，其中有幾種算法也是貪婪算法。例如，霍夫曼樹算法，利用n- 1步來建立最小加權(quán)外部路徑的二叉樹，每一步都將兩棵二叉樹合并為一棵，算法中所使用的貪婪準(zhǔn)則為：從可用的二叉樹中選出權(quán)重最小的兩棵。L P T調(diào)度規(guī)則也是一種貪婪算法，它用n 步來調(diào)度n 個作業(yè)。首先將作業(yè)按時間長短排序，然后在每一步中為一個任務(wù)分配一臺機(jī)器。選擇機(jī)器所利用的貪婪準(zhǔn)則為：使目前的調(diào)度時間最短。將新作業(yè)調(diào)度到最先完成的機(jī)器上（即最先空閑的機(jī)器）。
注意到在機(jī)器調(diào)度問題中，貪婪算法并不能保證最優(yōu)，然而，那是一種直覺的傾向且一般情況下結(jié)果總是非常接近最優(yōu)值。它利用的規(guī)則就是在實(shí)際環(huán)境中希望人工機(jī)器調(diào)度所采用的規(guī)則。算法并不保證得到最優(yōu)結(jié)果，但通常所得結(jié)果與最優(yōu)解相差無幾，這種算法也稱為啟發(fā)式方法（ h e u r i s t i c s )。因此L P T方法是一種啟發(fā)式機(jī)器調(diào)度方法。定理9 - 2陳述了L P T調(diào)度的完成時間與最佳調(diào)度的完成時間之間的關(guān)系，因此L P T啟發(fā)式方法具有限定性
能（ bounded performance ）。具有限定性能的啟發(fā)式方法稱為近似算法（ a p p r o x i m a t i o na l g o r i t h m）。
本章的其余部分將介紹幾種貪婪算法的應(yīng)用。在有些應(yīng)用中，貪婪算法所產(chǎn)生的結(jié)果總是最優(yōu)的解決方案。但對其他一些應(yīng)用，生成的算法只是一種啟發(fā)式方法，可能是也可能不是近似算法。
1.3.1 貨箱裝船
這個問題來自例1 - 2。船可以分步裝載，每步裝一個貨箱，且需要考慮裝載哪一個貨箱。根據(jù)這種思想可利用如下貪婪準(zhǔn)則：從剩下的貨箱中，選擇重量最小的貨箱。這種選擇次序可以保證所選的貨箱總重量最小，從而可以裝載更多的貨箱。根據(jù)這種貪婪策略，首先選擇最輕的貨箱，然后選次輕的貨箱，如此下去直到所有貨箱均裝上船或船上不能再容納其他任何一個貨箱。
例1-7 假設(shè)n =8, [w1 , ... w8 ]=[100,200,50,90,150,50,20,80], c= 4 0 0。利用貪婪算法時，所考察貨箱的順序?yàn)? , 3 , 6 , 8 , 4 , 1 , 5 , 2。貨箱7 , 3 , 6 , 8 , 4 , 1的總重量為3 9 0個單位且已被裝載，剩下的裝載能力為1 0個單位，小于剩下的任何一個貨箱。在這種貪婪解決算法中得到[x1 , ..., x8 ] = [ 1 , 0 , 1 , 1 , 0 , 1 , 1 , 1 ]且?xi = 6。
定理1-1 利用貪婪算法能產(chǎn)生最佳裝載。
證明可以采用如下方式來證明貪婪算法的最優(yōu)性：令x = [x1 , ..., xn ]為用貪婪算法獲得的解，令y =[ y1 , ..., yn ]為任意一個可行解，只需證明n ?i= 1xi ≥n ?i= 1yi 。不失一般性，可以假設(shè)貨箱都排好了序：即wi≤wi + 1（1≤i≤n）。然后分幾步將y 轉(zhuǎn)化為x，轉(zhuǎn)換過程中每一步都產(chǎn)生一個可行的新y，且n ?i = 1yi 大于等于未轉(zhuǎn)化前的值，最后便可證明n ?i = 1xi ≥n ?j = 1yi 。
根據(jù)貪婪算法的工作過程，可知在[0, n] 的范圍內(nèi)有一個k，使得xi =1, i≤k且xi =0, i>k。尋找[ 1 ,n]范圍內(nèi)最小的整數(shù)j，使得xj≠yj 。若沒有這樣的j 存在，則n ?i= 1xi =n ?i = 1yi 。如果有這樣的j 存在，則j≤k，否則y 就不是一個可行解，因?yàn)閤j≠yj ，xj = 1且yj = 0。令yj = 1，若結(jié)果得到的y 不是可行解，則在[ j+ 1 ,n]范圍內(nèi)必有一個l 使得yl = 1。令yl = 0，由于wj≤wl ，則得到的y 是可行的。而且，得到的新y 至少與原來的y 具有相同數(shù)目的1。
經(jīng)過數(shù)次這種轉(zhuǎn)化，可將y 轉(zhuǎn)化為x。由于每次轉(zhuǎn)化產(chǎn)生的新y 至少與前一個y 具有相同數(shù)目的1，因此x 至少與初始的y 具有相同的數(shù)目1。貨箱裝載算法的C + +代碼實(shí)現(xiàn)見程序1 3 - 1。由于貪婪算法按貨箱重量遞增的順序裝載，程序1 3 - 1首先利用間接尋址排序函數(shù)I n d i r e c t S o r t對貨箱重量進(jìn)行排序（見3 . 5節(jié)間接尋址的定義），隨后貨箱便可按重量遞增的順序裝載。由于間接尋址排序所需的時間為O (nl o gn)（也可利用9 . 5 . 1節(jié)的堆排序及第2章的歸并排序），算法其余部分所需時間為O (n)，因此程序1 3 - 1的總的復(fù)雜性為O (nl o gn)。
程序13-1 貨箱裝船
template<class T>
void ContainerLoading(int x[], T w[], T c, int n)
{// 貨箱裝船問題的貪婪算法
// x[i] = 1 當(dāng)且僅當(dāng)貨箱i被裝載， 1<=i<=n
// c是船的容量, w 是貨箱的重量
// 對重量按間接尋址方式排序
// t 是間接尋址表
int *t = new int [n+1];
I n d i r e c t S o r t ( w, t, n);
// 此時, w[t[i]] <= w[t[i+1]], 1<=i<n
// 初始化x
for (int i = 1; i <= n; i++)
x[i] = 0;
// 按重量次序選擇物品
for (i = 1; i <= n && w[t[i]] <= c; i++) {
x[t[i]] = 1;
c -= w[t[i]];} // 剩余容量
delete [] t;
}
1.3.2 0/1背包問題
在0 / 1背包問題中，需對容量為c 的背包進(jìn)行裝載。從n 個物品中選取裝入背包的物品，每件物品i 的重量為wi ，價值為pi 。對于可行的背包裝載，背包中物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價值最高，即n ?i=1pi xi 取得最大值。約束條件為n ?i =1wi xi≤c 和xi?[ 0 , 1 ] ( 1≤i≤n)。
在這個表達(dá)式中，需求出xt 的值。xi = 1表示物品i 裝入背包中，xi =0 表示物品i 不裝入背包。0 / 1背包問題是一個一般化的貨箱裝載問題，即每個貨箱所獲得的價值不同。貨箱裝載問題轉(zhuǎn)化為背包問題的形式為：船作為背包，貨箱作為可裝入背包的物品。 例1-8 在雜貨店比賽中你獲得了第一名，獎品是一車免費(fèi)雜貨。店中有n 種不同的貨物。規(guī)則規(guī)定從每種貨物中最多只能拿一件，車子的容量為c，物品i 需占用wi 的空間，價值為pi 。你的目標(biāo)是使車中裝載的物品價值最大。當(dāng)然，所裝貨物不能超過車的容量，且同一種物品不得拿走多件。這個問題可仿照0 / 1背包問題進(jìn)行建模，其中車對應(yīng)于背包，貨物對應(yīng)于物品。
0 / 1背包問題有好幾種貪婪策略，每個貪婪策略都采用多步過程來完成背包的裝入。在每一步過程中利用貪婪準(zhǔn)則選擇一個物品裝入背包。一種貪婪準(zhǔn)則為：從剩余的物品中，選出可以裝入背包的價值最大的物品，利用這種規(guī)則，價值最大的物品首先被裝入（假設(shè)有足夠容量），然后是下一個價值最大的物品，如此繼續(xù)下去。這種策略不能保證得到最優(yōu)解。例如，考慮n=2, w=[100,10,10], p =[20,15,15], c = 1 0 5。當(dāng)利用價值貪婪準(zhǔn)則時，獲得的解為x= [ 1 , 0 , 0 ]，這種方案的總價值為2 0。而最優(yōu)解為[ 0 , 1 , 1 ]，其總價值為3 0。
另一種方案是重量貪婪準(zhǔn)則是：從剩下的物品中選擇可裝入背包的重量最小的物品。雖然這種規(guī)則對于前面的例子能產(chǎn)生最優(yōu)解，但在一般情況下則不一定能得到最優(yōu)解。考慮n= 2 ,w=[10,20], p=[5,100], c= 2 5。當(dāng)利用重量貪婪策略時，獲得的解為x =[1,0], 比最優(yōu)解[ 0 , 1 ]要差。
還可以利用另一方案，價值密度pi /wi 貪婪算法，這種選擇準(zhǔn)則為：從剩余物品中選擇可
裝入包的pi /wi 值最大的物品，這種策略也不能保證得到最優(yōu)解。利用此策略試解n= 3 ,w=[20,15,15], p=[40,25,25], c=30 時的最優(yōu)解。
我們不必因所考察的幾個貪婪算法都不能保證得到最優(yōu)解而沮喪， 0 / 1背包問題是一個N P-復(fù)雜問題。對于這類問題，也許根本就不可能找到具有多項(xiàng)式時間的算法。雖然按pi /wi 非遞（增）減的次序裝入物品不能保證得到最優(yōu)解，但它是一個直覺上近似的解。我們希望它是一個好的啟發(fā)式算法，且大多數(shù)時候能很好地接近最后算法。在6 0 0個隨機(jī)產(chǎn)生的背包問題中，用這種啟發(fā)式貪婪算法來解有2 3 9題為最優(yōu)解。有5 8 3個例子與最優(yōu)解相差1 0 %，所有6 0 0個答案與最優(yōu)解之差全在2 5 %以內(nèi)。該算法能在O (nl o gn)時間內(nèi)獲得如此好的性能。我們也許會問，是否存在一個x (x<1 0 0 )，使得貪婪啟發(fā)法的結(jié)果與最優(yōu)值相差在x%以內(nèi)。答案是否定的。為說明這一點(diǎn)，考慮例子n =2, w = [ 1 ,y], p= [ 1 0 , 9y], 和c= y。貪婪算法結(jié)果為x=[1,0], 這種方案的值為1 0。對于y≥1 0 / 9，最優(yōu)解的值為9 y。因此，貪婪算法的值與最優(yōu)解的差對最優(yōu)解的比例為( ( 9y - 1 0)/9y* 1 0 0 ) %，對于大的y，這個值趨近于1 0 0 %。但是可以建立貪婪啟發(fā)式方法來提供解，使解的結(jié)果與最優(yōu)解的值之差在最優(yōu)值的x% (x<100) 之內(nèi)。首先將最多k 件物品放入背包，如果這k 件物品重量大于c，則放棄它。否則，剩余的容量用來考慮將剩余物品按pi /wi 遞減的順序裝入。通過考慮由啟發(fā)法產(chǎn)生的解法中最多為k 件物品的所有可能的子集來得到最優(yōu)解。
例13-9 考慮n =4, w=[2,4,6,7], p=[6,10,12,13], c = 11。當(dāng)k= 0時，背包按物品價值密度非遞減順序裝入，首先將物品1放入背包，然后是物品2，背包剩下的容量為5個單元，剩下的物品沒有一個合適的，因此解為x = [ 1 , 1 , 0 , 0 ]。此解獲得的價值為1 6。
現(xiàn)在考慮k = 1時的貪婪啟發(fā)法。最初的子集為{ 1 } , { 2 } , { 3 } , { 4 }。子集{ 1 } , { 2 }產(chǎn)生與k= 0時相同的結(jié)果，考慮子集{ 3 }，置x3 為1。此時還剩5個單位的容量，按價值密度非遞增順序來考慮如何利用這5個單位的容量。首先考慮物品1，它適合，因此取x1 為1，這時僅剩下3個單位容量了，且剩余物品沒有能夠加入背包中的物品。通過子集{ 3 }開始求解得結(jié)果為x = [ 1 , 0 , 1 , 0 ]，獲得的價值為1 8。若從子集{ 4 }開始，產(chǎn)生的解為x = [ 1 , 0 , 0 , 1 ]，獲得的價值為1 9?？紤]子集大小為0和1時獲得的最優(yōu)解為[ 1 , 0 , 0 , 1 ]。這個解是通過k= 1的貪婪啟發(fā)式算法得到的。
若k= 2，除了考慮k< 2的子集，還必需考慮子集{ 1 , 2 } , { 1 , 3 } , { 1 , 4 } , { 2 , 3 } , { 2 , 4 }和{ 3 , 4 }。首先從最后一個子集開始，它是不可行的，故將其拋棄，剩下的子集經(jīng)求解分別得到如下結(jié)果：[ 1 , 1 , 0 , 0 ] , [ 1 , 0 , 1 , 0 ] , [ 1 , 0 , 0 , 1 ] , [ 0 , 1 , 1 , 0 ]和[ 0 , 1 , 0 , 1 ]，這些結(jié)果中最后一個價值為2 3，它的值比k= 0和k= 1時獲得的解要高，這個答案即為啟發(fā)式方法產(chǎn)生的結(jié)果。 這種修改后的貪婪啟發(fā)方法稱為k階優(yōu)化方法（k - o p t i m a l）。也就是，若從答案中取出k 件物品，并放入另外k 件，獲得的結(jié)果不會比原來的好，而且用這種方式獲得的值在最優(yōu)值的( 1 0 0 / (k + 1 ) ) %以內(nèi)。當(dāng)k= 1時，保證最終結(jié)果在最佳值的5 0 %以內(nèi)；當(dāng)k= 2時，則在3 3 . 3 3 %以內(nèi)等等，這種啟發(fā)式方法的執(zhí)行時間隨k 的增大而增加，需要測試的子集數(shù)目為O (nk )，每一個子集所需時間為O (n)，因此當(dāng)k >0時總的時間開銷為O (nk+1 )。實(shí)際觀察到的性能要好得多。
1.3.3 拓?fù)渑判?BR>一個復(fù)雜的工程通常可以分解成一組小任務(wù)的集合，完成這些小任務(wù)意味著整個工程的完成。例如，汽車裝配工程可分解為以下任務(wù)：將底盤放上裝配線，裝軸，將座位裝在底盤上，上漆，裝剎車，裝門等等。任務(wù)之間具有先后關(guān)系，例如在裝軸之前必須先將底板放上裝配線。任務(wù)的先后順序可用有向圖表示——稱為頂點(diǎn)活動（ Activity On Vertex, AOV）網(wǎng)絡(luò)。有向圖的頂點(diǎn)代表任務(wù)，有向邊(i, j) 表示先后關(guān)系：任務(wù)j 開始前任務(wù)i 必須完成。圖1 - 4顯示了六個任務(wù)的工程，邊（ 1 , 4）表示任務(wù)1在任務(wù)4開始前完成，同樣邊（ 4 , 6）表示任務(wù)4在任務(wù)6開始前完成，邊（1 , 4）與（4 , 6）合起來可知任務(wù)1在任務(wù)6開始前完成，即前后關(guān)系是傳遞的。由此可知，邊（1 , 4）是多余的，因?yàn)檫叄? , 3）和（3 , 4）已暗示了這種關(guān)系。
在很多條件下，任務(wù)的執(zhí)行是連續(xù)進(jìn)行的，例如汽車裝配問題或平時購買的標(biāo)有“需要裝配”的消費(fèi)品（自行車、小孩的秋千裝置，割草機(jī)等等）。我們可根據(jù)所建議的順序來裝配。在由任務(wù)建立的有向圖中，邊（ i, j）表示在裝配序列中任務(wù)i 在任務(wù)j 的前面，具有這種性質(zhì)的序列稱為拓?fù)湫蛄校╰opological orders或topological sequences)。根據(jù)任務(wù)的有向圖建立拓?fù)湫蛄械倪^程稱為拓?fù)渑判颍╰opological sorting）。圖1 - 4的任務(wù)有向圖有多種拓?fù)湫蛄?，其中的三種為1 2 3 4 5 6，1 3 2 4 5 6和2 1 5 3 4 6，序列1 4 2 3 5 6就不是拓?fù)湫蛄?，因?yàn)樵谶@個序列中任務(wù)4在3的前面，而任務(wù)有向圖中的邊為（ 3 , 4），這種序列與邊（ 3 , 4）及其他邊所指示的序列相矛盾。可用貪婪算法來建立拓?fù)湫蛄小Ｋ惴ò磸淖蟮接业牟襟E構(gòu)造拓?fù)湫蛄校恳徊皆谂藕玫男蛄兄屑尤胍粋€頂點(diǎn)。利用如下貪婪準(zhǔn)則來選擇頂點(diǎn)：從剩下的頂點(diǎn)中，選擇頂點(diǎn)w，使得w 不存在這樣的入邊（ v,w），其中頂點(diǎn)v 不在已排好的序列結(jié)構(gòu)中出現(xiàn)。注意到如果加入的頂點(diǎn)w違背了這個準(zhǔn)則（即有向圖中存在邊（ v,w）且v 不在已構(gòu)造的序列中），則無法完成拓?fù)渑判?，因?yàn)轫旤c(diǎn)v 必須跟隨在頂點(diǎn)w 之后。貪婪算法的偽代碼如圖1 3 - 5所示。while 循環(huán)的每次迭代代表貪婪算法的一個步驟。
現(xiàn)在用貪婪算法來求解圖1 - 4的有向圖。首先從一個空序列V開始，第一步選擇V的第一個頂點(diǎn)。此時，在有向圖中有兩個候選頂點(diǎn)1和2，若選擇頂點(diǎn)2，則序列V = 2，第一步完成。第二步選擇V的第二個頂點(diǎn)，根據(jù)貪婪準(zhǔn)則可知候選頂點(diǎn)為1和5，若選擇5，則V = 2 5。下一步，頂點(diǎn)1是唯一的候選，因此V = 2 5 1。第四步，頂點(diǎn)3是唯一的候選，因此把頂點(diǎn)3加入V
得到V = 2 5 1 3。在最后兩步分別加入頂點(diǎn)4和6 ，得V = 2 5 1 3 4 6。
1. 貪婪算法的正確性
為保證貪婪算法算的正確性，需要證明： 1) 當(dāng)算法失敗時，有向圖沒有拓?fù)湫蛄校?2) 若
算法沒有失敗，V即是拓?fù)湫蛄小?) 即是用貪婪準(zhǔn)則來選取下一個頂點(diǎn)的直接結(jié)果， 1) 的證明見定理1 3 - 2，它證明了若算法失敗，則有向圖中有環(huán)路。若有向圖中包含環(huán)qj qj + 1.qk qj , 則它沒有拓?fù)湫蛄?，因?yàn)樵撔蛄邪凳玖藂j 一定要在qj 開始前完成。
定理1-2 如果圖1 3 - 5算法失敗，則有向圖含有環(huán)路。
證明注意到當(dāng)失敗時| V |<n, 且沒有候選頂點(diǎn)能加入V中，因此至少有一個頂點(diǎn)q1 不在V中，有向圖中必包含邊（ q2 , q1）且q2 不在V中，否則， q1 是可加入V的候選頂點(diǎn)。同樣，必有邊（q3 , q2）使得q3 不在V中，若q3 = q1 則q1 q2 q3 是有向圖中的一個環(huán)路；若q3 ≠q1，則必存在q4 使（q4 , q3）是有向圖的邊且q4 不在V中，否則，q3 便是V的一個候選頂點(diǎn)。若q4 為q1 , q2 , q3 中的任何一個，則又可知有向圖含有環(huán)，因?yàn)橛邢驁D具有有限個頂點(diǎn)數(shù)n，繼續(xù)利用上述方法，最后總能找到一個環(huán)路。
2. 數(shù)據(jù)結(jié)構(gòu)的選擇
為將圖1 - 5用C + +代碼來實(shí)現(xiàn)，必須考慮序列V的描述方法，以及如何找出可加入V的候選頂點(diǎn)。一種高效的實(shí)現(xiàn)方法是將序列V用一維數(shù)組v 來描述的，用一個棧來保存可加入V的候選頂點(diǎn)。另有一個一維數(shù)組I n D e g r e e，I n D e g r e e[ j ]表示與頂點(diǎn)j相連的節(jié)點(diǎn)i 的數(shù)目，其中頂點(diǎn)i不是V中的成員，它們之間的有向圖的邊表示為（ i, j）。當(dāng)I n D e g r e e[ j ]變?yōu)?時表示j 成為一個候選節(jié)點(diǎn)。序列V初始時為空。I n D e g r e e[ j ]為頂點(diǎn)j 的入度。每次向V中加入一個頂點(diǎn)時，所有與新加入頂點(diǎn)鄰接的頂點(diǎn)j，其I n D e g r e e[ j ]減1。對于有向圖1 - 4，開始時I n D e g r e e [ 1 : 6 ] = [ 0 , 0 , 1 , 3 , 1 , 3 ]。由于頂點(diǎn)1和2的I n D e g r e e值為0，因此它們是可加入V的候選頂點(diǎn)，由此，頂點(diǎn)1和2首先入棧。每一步，從棧中取出一個頂點(diǎn)將其加入V，同時減去與其鄰接的頂點(diǎn)的I n D e g r e e值。若在第一步時從棧中取出頂點(diǎn)2并將其加入V，便得到了v [ 0 ] = 2，和I n D e g r e e [ 1 : 6 ] = [ 0 , 0 , 1 , 2 , 0 , 3 ]。由于I n D e g r e e [ 5 ]剛剛變?yōu)?，因此將頂點(diǎn)5入棧。
程序1 3 - 2給出了相應(yīng)的C + +代碼，這個代碼被定義為N e t w o r k的一個成員函數(shù)。而且，它對于有無加權(quán)的有向圖均適用。但若用于無向圖（不論其有無加權(quán)）將會得到錯誤的結(jié)果，因?yàn)橥負(fù)渑判蚴轻槍τ邢驁D來定義的。為解決這個問題，利用同樣的模板來定義成員函數(shù)AdjacencyGraph, AdjacencyWGraph，L i n k e d G r a p h和L i n k e d W G r a p h。這些函數(shù)可重載N e t w o r k中的函數(shù)并可輸出錯誤信息。如果找到拓?fù)湫蛄?，則Topological 函數(shù)返回t r u e；若輸入的有向圖無拓?fù)湫蛄袆t返回f a l s e。當(dāng)找到拓?fù)湫蛄袝r，將其返回到v [ 0 :n- 1 ]中。
3. Network:Topological 的復(fù)雜性
第一和第三個f o r循環(huán)的時間開銷為(n )。若使用（耗費(fèi)）鄰接矩陣,則第二個for 循環(huán)所用的時間為(n2 )；若使用鄰接鏈表,則所用時間為(n+e)。在兩個嵌套的while 循環(huán)中，外層循環(huán)需執(zhí)行n次，每次將頂點(diǎn)w 加入到v 中，并初始化內(nèi)層while 循環(huán)。使用鄰接矩陣時，內(nèi)層w h i l e循環(huán)對于每個頂點(diǎn)w 需花費(fèi)(n)的時間；若利用鄰接鏈表，則這個循環(huán)需花費(fèi)dwout 的時間，因此，內(nèi)層while 循環(huán)的時間開銷為(n2 )或(n+e)。所以，若利用鄰接矩陣，程序1 3 - 2的時間復(fù)雜性為(n2 )，若利用鄰接鏈表則為(n+e)。
程序13-2 拓?fù)渑判?/P>
bool Network::Topological(int v[])
{// 計算有向圖中頂點(diǎn)的拓?fù)浯涡?/P>
// 如果找到了一個拓?fù)浯涡颍瑒t返回t r u e，此時，在v [ 0 : n - 1 ]中記錄拓?fù)浯涡?/P>
// 如果不存在拓?fù)浯涡?，則返回f a l s e
int n = Ve r t i c e s ( ) ;
// 計算入度
int *InDegree = new int [n+1];
InitializePos(); // 圖遍歷器數(shù)組
for (int i = 1; i <= n; i++) // 初始化
InDegree[i] = 0;
for (i = 1; i <= n; i++) {// 從i 出發(fā)的邊
int u = Begin(i);
while (u) {
I n D e g r e e [ u ] + + ;
u = NextVe r t e x ( i ) ; }
}
// 把入度為０的頂點(diǎn)壓入堆棧
LinkedStack<int> S;
for (i = 1; i <= n; i++)
if (!InDegree[i]) S.Add(i);
// 產(chǎn)生拓?fù)浯涡?/P>
i = 0; // 數(shù)組v 的游標(biāo)
while (!S.IsEmpty()) {// 從堆棧中選擇
int w; // 下一個頂點(diǎn)
S . D e l e t e ( w ) ;
v[i++] = w;
int u = Begin(w);
while (u) {// 修改入度
I n D e g r e e [ u ] - - ;
if (!InDegree[u]) S.Add(u);
u = NextVe r t e x ( w ) ; }
}
D e a c t i v a t e P o s ( ) ;
delete [] InDegree;
return (i == n);
}
1.3.4 二分覆蓋
二分圖是一個無向圖，它的n 個頂點(diǎn)可二分為集合A和集合B，且同一集合中的任意兩個頂點(diǎn)在圖中無邊相連（即任何一條邊都是一個頂點(diǎn)在集合A中，另一個在集合B中）。當(dāng)且僅當(dāng)B中的每個頂點(diǎn)至少與A中一個頂點(diǎn)相連時，A的一個子集A' 覆蓋集合B（或簡單地說，A' 是一個覆蓋）。覆蓋A' 的大小即為A' 中的頂點(diǎn)數(shù)目。當(dāng)且僅當(dāng)A' 是覆蓋B的子集中最小的時，A' 為最小覆蓋。
例1-10 考察如圖1 - 6所示的具有1 7個頂點(diǎn)的二分圖，A={1, 2, 3, 16, 17}和B={4, 5, 6, 7, 8, 9,10, 11, 12, 13, 14, 15}，子集A' = { 1 , 1 6 , 1 7 }是B的最小覆蓋。在二分圖中尋找最小覆蓋的問題為二分覆蓋（ b i p a r t i t e - c o v e r）問題。在例1 2 - 3中說明了最小覆蓋是很有用的，因?yàn)樗芙鉀Q“在會議中使用最少的翻譯人員進(jìn)行翻譯”這一類的問題。
二分覆蓋問題類似于集合覆蓋（ s e t - c o v e r）問題。在集合覆蓋問題中給出了k 個集合S= {S1 , S2 ,., Sk }，每個集合Si 中的元素均是全集U中的成員。當(dāng)且僅當(dāng)èi S'Si =U時，S的子集S' 覆蓋U，S '中的集合數(shù)目即為覆蓋的大小。當(dāng)且僅當(dāng)沒有能覆蓋U的更小的集合時，稱S' 為最小覆蓋。可以將集合覆蓋問題轉(zhuǎn)化為二分覆蓋問題（反之亦然），即用A的頂點(diǎn)來表示S1 , ., Sk ，B中的頂點(diǎn)代表U中的元素。當(dāng)且僅當(dāng)S的相應(yīng)集合中包含U中的對應(yīng)元素時，在A與B的頂點(diǎn)之間存在一條邊。
例1 - 11 令S= {S1，. . .，S5 }, U= { 4，5，. . .，15}, S1 = { 4，6，7，8，9，1 3 }，S2 = { 4，5，6，8 }，S3 = { 8，1 0，1 2，1 4，1 5 }，S4 = { 5，6，8，1 2，1 4，1 5 }，S5 = { 4，9，1 0，11 }。S ' = {S1，S4，S5 }是一個大小為3的覆蓋，沒有更小的覆蓋， S' 即為最小覆蓋。這個集合覆蓋問題可映射為圖1-6的二分圖，即用頂點(diǎn)1，2，3，1 6和1 7分別表示集合S1，S2，S3，S4 和S5，頂點(diǎn)j 表示集合中的元素j，4≤j≤1 5。
集合覆蓋問題為N P-復(fù)雜問題。由于集合覆蓋與二分覆蓋是同一類問題，二分覆蓋問題也是N P-復(fù)雜問題。因此可能無法找到一個快速的算法來解決它，但是可以利用貪婪算法尋找一種快速啟發(fā)式方法。一種可能是分步建立覆蓋A' ，每一步選擇A中的一個頂點(diǎn)加入覆蓋。頂點(diǎn)的選擇利用貪婪準(zhǔn)則：從A中選取能覆蓋B中還未被覆蓋的元素數(shù)目最多的頂點(diǎn)。
例1-12 考察圖1 - 6所示的二分圖，初始化A' = 且B中沒有頂點(diǎn)被覆蓋，頂點(diǎn)1和1 6均能覆蓋B中的六個頂點(diǎn)，頂點(diǎn)3覆蓋五個，頂點(diǎn)2和1 7分別覆蓋四個。因此，在第一步往A' 中加入頂點(diǎn)1或1 6，若加入頂點(diǎn)1 6，則它覆蓋的頂點(diǎn)為{ 5 , 6 , 8 , 1 2 , 1 4 , 1 5 }，未覆蓋的頂點(diǎn)為{ 4 , 7 , 9 , 1 0 , 11 , 1 3 }。頂點(diǎn)1能覆蓋其中四個頂點(diǎn)（ { 4 , 7 , 9 , 1 3 }），頂點(diǎn)2 覆蓋一個( { 4 } )，頂點(diǎn)3覆蓋一個（{ 1 0 }），頂點(diǎn)1 6覆蓋零個，頂點(diǎn)1 7覆蓋四個{ 4 , 9 , 1 0 , 11 }。下一步可選擇1或1 7加入A' 。若選擇頂點(diǎn)1，則頂點(diǎn){ 1 0 , 11} 仍然未被覆蓋，此時頂點(diǎn)1，2，1 6不覆蓋其中任意一個，頂點(diǎn)3覆蓋一個，頂點(diǎn)1 7覆蓋兩個，因此選擇頂點(diǎn)1 7，至此所有頂點(diǎn)已被覆蓋，得A' = { 1 6 , 1 , 1 7 }。
圖1 - 7給出了貪婪覆蓋啟發(fā)式方法的偽代碼，可以證明： 1) 當(dāng)且僅當(dāng)初始的二分圖沒有覆蓋時，算法找不到覆蓋；2) 啟發(fā)式方法可能找不到二分圖的最小覆蓋。
1. 數(shù)據(jù)結(jié)構(gòu)的選取及復(fù)雜性分析
為實(shí)現(xiàn)圖13 - 7的算法，需要選擇A' 的描述方法及考慮如何記錄A中節(jié)點(diǎn)所能覆蓋的B中未覆蓋節(jié)點(diǎn)的數(shù)目。由于對集合A' 僅使用加法運(yùn)算，則可用一維整型數(shù)組C來描述A '，用m 來記錄A' 中元素個數(shù)。將A' 中的成員記錄在C[ 0 :m-1] 中。對于A中頂點(diǎn)i，令N e wi 為i 所能覆蓋的B中未覆蓋的頂點(diǎn)數(shù)目。逐步選擇N e wi 值最大的頂點(diǎn)。由于一些原來未被覆蓋的頂點(diǎn)現(xiàn)在被覆蓋了，因此還要修改各N e wi 值。在這種更新中，檢查B中最近一次被V覆蓋的頂點(diǎn)，令j 為這樣的一個頂點(diǎn)，則A中所有覆蓋j 的頂點(diǎn)的N e wi 值均減1。
例1-13 考察圖1 - 6，初始時(N e w1 , N e w2 , N e w3 , N e w16 , N e w17 ) = ( 6 , 4 , 5 , 6 , 4 )。假設(shè)在例1 - 1 2中，第一步選擇頂點(diǎn)1 6，為更新N e wi 的值檢查B中所有最近被覆蓋的頂點(diǎn)，這些頂點(diǎn)為5 , 6 , 8 , 1 2 , 1 4和1 5。當(dāng)檢查頂點(diǎn)5時，將頂點(diǎn)2和1 6的N e wi 值分別減1，因?yàn)轫旤c(diǎn)5不再是被頂點(diǎn)2和1 6覆蓋的未覆蓋節(jié)點(diǎn)；當(dāng)檢查頂點(diǎn)6時，頂點(diǎn)1 , 2 ,和1 6的相應(yīng)值分別減1；同樣，檢查頂點(diǎn)8時，1，2，3和1 6的值分別減1；當(dāng)檢查完所有最近被覆蓋的頂點(diǎn)，得到的N e wi 值為（4，1，0，4）。下一步選擇頂點(diǎn)1，最新被覆蓋的頂點(diǎn)為4，7，9和1 3；檢查頂點(diǎn)4時，N e w1 , N e w2, 和N e w1 7 的值減1；檢查頂點(diǎn)7時，N e w1 的值減1，因?yàn)轫旤c(diǎn)1是覆蓋7的唯一頂點(diǎn)。
為了實(shí)現(xiàn)頂點(diǎn)選取的過程，需要知道N e wi 的值及已被覆蓋的頂點(diǎn)?？衫靡粋€二維數(shù)組來達(dá)到這個目的，N e w是一個整型數(shù)組，New[i] 即等于N e wi，且c o v為一個布爾數(shù)組。若頂點(diǎn)i未被覆蓋則c o v [ i ]等于f a l s e，否則c o v [ i ]為t r u e。現(xiàn)將圖1 - 7的偽代碼進(jìn)行細(xì)化得到圖1 - 8。
m=0; //當(dāng)前覆蓋的大小
對于A中的所有i，New[i]=Degree[i]
對于B中的所有i，C o v [ i ] = f a l s e
while (對于A中的某些i,New[i]>0) {
設(shè)v是具有最大的N e w [ i ]的頂點(diǎn)；
C [ m + + ] = v ;
for ( 所有鄰接于v的頂點(diǎn)j) {
if (!Cov[j]) {
Cov[j]= true;
對于所有鄰接于j的頂點(diǎn)，使其N e w [ k ]減1
} } }
if (有些頂點(diǎn)未被覆蓋) 失敗
else 找到一個覆蓋
圖1-8 圖1-7的細(xì)化
更新N e w的時間為O (e)，其中e 為二分圖中邊的數(shù)目。若使用鄰接矩陣，則需花(n2 ) 的時間來尋找圖中的邊，若用鄰接鏈表，則需(n+e) 的時間。實(shí)際更新時間根據(jù)描述方法的不同為O (n2 ) 或O (n+e)。逐步選擇頂點(diǎn)所需時間為(S i z e O f A)，其中S i z e O f A=| A |。因?yàn)锳的所有頂點(diǎn)都有可能被選擇，因此所需步驟數(shù)為O ( S i z e O f A )，覆蓋算法總的復(fù)雜性為O ( S i z e O f A 2+n2) = O ( n2)或O (S i z e Of A2+n + e)。
2. 降低復(fù)雜性
通過使用有序數(shù)組N e wi、最大堆或最大選擇樹（max selection tree）可將每步選取頂點(diǎn)v的復(fù)雜性降為( 1 )。但利用有序數(shù)組，在每步的最后需對N e wi 值進(jìn)行重新排序。若使用箱子排序，則這種排序所需時間為(S i z e O f B ) ( S i z e O fB =|B| ) （見3 . 8 . 1節(jié)箱子排序）。由于一般S i z e O f B比S i z e O f A大得多，因此有序數(shù)組并不總能提高性能。
如果利用最大堆，則每一步都需要重建堆來記錄N e w值的變化，可以在每次N e w值減1時進(jìn)行重建。這種減法操作可引起被減的N e w值最多在堆中向下移一層，因此這種重建對于每次N e w值減1需( 1 )的時間，總共的減操作數(shù)目為O (e)。因此在算法的所有步驟中，維持最大堆僅需O (e)的時間，因而利用最大堆時覆蓋算法的總復(fù)雜性為O (n2 )或O (n+e)。
若利用最大選擇樹，每次更新N e w值時需要重建選擇樹，所需時間為(log S i z e O f A)。重建的最好時機(jī)是在每步結(jié)束時，而不是在每次N e w值減1時，需要重建的次數(shù)為O (e)，因此總的重建時間為O (e log S i z e OfA)，這個時間比最大堆的重建時間長一些。然而，通過維持具有相同N e w值的頂點(diǎn)箱子，也可獲得和利用最大堆時相同的時間限制。由于N e w的取值范圍為0到S i z e O f B，需要S i z e O f B+ 1個箱子，箱子i 是一個雙向鏈表，鏈接所有N e w值為i 的頂點(diǎn)。在某一步結(jié)束時，假如N e w [ 6 ]從1 2變到4，則需要將它從第1 2個箱子移到第4個箱子。利用模擬指針及一個節(jié)點(diǎn)數(shù)組n o d e（其中n o d e [ i ]代表頂點(diǎn)i，n o d e [ i ] . l e f t和n o d e [ i ] . r i g h t為雙向鏈表指針），可將頂點(diǎn)6從第1 2個箱子移到第4個箱子，從第1 2個箱子中刪除n o d e [ 0 ]并將其插入第4個箱子。利用這種箱子模式，可得覆蓋啟發(fā)式算法的復(fù)雜性為O (n2 )或O(n+e)。（取決于利用鄰接矩陣還是線性表來描述圖）。
3. 雙向鏈接箱子的實(shí)現(xiàn)
為了實(shí)現(xiàn)上述雙向鏈接箱子，圖1 - 9定義了類U n d i r e c t e d的私有成員。N o d e Ty p e是一個具有私有整型成員l e f t和r i g h t的類，它的數(shù)據(jù)類型是雙向鏈表節(jié)點(diǎn)，程序1 3 - 3給出了U n d i r e c t e d的私有成員的代碼。
void CreateBins (int b, int n)
創(chuàng)建b個空箱子和n個節(jié)點(diǎn)
void DestroyBins() { delete [] node;
delete [] bin;}
void InsertBins(int b, int v)
在箱子b中添加頂點(diǎn)v
void MoveBins(int bMax, int ToBin, int v)
從當(dāng)前箱子中移動頂點(diǎn)v到箱子To B i n
int *bin;
b i n [ i ]指向代表該箱子的雙向鏈表的首節(jié)點(diǎn)
N o d e Type *node;
n o d e [ i ]代表存儲頂點(diǎn)i的節(jié)點(diǎn)
圖1-9 實(shí)現(xiàn)雙向鏈接箱子所需的U n d i r e c t e d私有成員
程序13-3 箱子函數(shù)的定義
void Undirected::CreateBins(int b, int n)
{// 創(chuàng)建b個空箱子和n個節(jié)點(diǎn)
node = new NodeType [n+1];
bin = new int [b+1];
// 將箱子置空
for (int i = 1; i <= b; i++)
bin[i] = 0;
}
void Undirected::InsertBins(int b, int v)
{// 若b不為０，則將v 插入箱子b
if (!b) return; // b為0，不插入
node[v].left = b; // 添加在左端
if (bin[b]) node[bin[b]].left = v;
node[v].right = bin[b];
bin[b] = v;
}
void Undirected::MoveBins(int bMax, int ToBin, int v)
{// 將頂點(diǎn)v 從其當(dāng)前所在箱子移動到To B i n .
// v的左、右節(jié)點(diǎn)
int l = node[v].left;
int r = node[v].right;
// 從當(dāng)前箱子中刪除
if (r) node[r].left = node[v].left;
if (l > bMax || bin[l] != v) // 不是最左節(jié)點(diǎn)
node[l].right = r;
else bin[l] = r; // 箱子l的最左邊
// 添加到箱子To B i n
I n s e r t B i n s ( ToBin, v);
}
函數(shù)C r e a t e B i n s動態(tài)分配兩個數(shù)組： n o d e和b i n，n o d e [i ]表示頂點(diǎn)i, bin[i ]指向其N e w值為i的雙向鏈表的頂點(diǎn), f o r循環(huán)將所有雙向鏈表置為空。如果b≠0，函數(shù)InsertBins 將頂點(diǎn)v 插入箱子b 中。因?yàn)閎 是頂點(diǎn)v 的New 值，b = 0意味著頂點(diǎn)v 不能覆蓋B中當(dāng)前還未被覆蓋的任何頂點(diǎn)，所以，在建立覆蓋時這個箱子沒有用處，故可以將其舍去。當(dāng)b≠0時，頂點(diǎn)n 加入New 值為b 的雙向鏈表箱子的最前面，這種加入方式需要將node[v] 加入bin[b] 中第一個節(jié)點(diǎn)的左邊。由于表的最左節(jié)點(diǎn)應(yīng)指向它所屬的箱子，因此將它的node[v].left 置為b。若箱子不空，則當(dāng)前第一個節(jié)點(diǎn)的left 指針被置為指向新節(jié)點(diǎn)。node[v] 的右指針被置為b i n [ b ]，其值可能為0或指向上一個首節(jié)點(diǎn)的指針。最后， b i n [ b ]被更新為指向表中新的第一個節(jié)點(diǎn)。MoveBins 將頂點(diǎn)v 從它在雙向鏈表中的當(dāng)前位置移到New 值為ToBin 的位置上。其中存在bMa x，使得對所有的箱子b i n[ j ]都有：如j>bMa x，則b i n [ j ]為空。代碼首先確定n o d e [ v ]在當(dāng)前雙向鏈表中的左右節(jié)點(diǎn)，接著從雙鏈表中取出n o d e [ v ]，并利用I n s e r t B i n s函數(shù)將其重新插入到b i n [ To B i n ]中。
4. Undirected::BipartiteCover的實(shí)現(xiàn)
函數(shù)的輸入?yún)?shù)L用于分配圖中的頂點(diǎn)（分配到集合A或B）。L [i ] = 1表示頂點(diǎn)i在集合A中，L[ i ] = 2則表示頂點(diǎn)在B中。函數(shù)有兩個輸出參數(shù)： C和m，m為所建立的覆蓋的大小， C [ 0 , m - 1 ]是A中形成覆蓋的頂點(diǎn)。若二分圖沒有覆蓋，函數(shù)返回f a l s e；否則返回t r u e。完整的代碼見程序1 3 - 4。
程序13-4 構(gòu)造貪婪覆蓋
bool Undirected::BipartiteCover(int L[], int C[], int& m)
{// 尋找一個二分圖覆蓋
// L 是輸入頂點(diǎn)的標(biāo)號, L[i] = 1 當(dāng)且僅當(dāng)i 在Ａ中
// C 是一個記錄覆蓋的輸出數(shù)組
// 如果圖中不存在覆蓋，則返回f a l s e
// 如果圖中有一個覆蓋，則返回t r u e ;
// 在m中返回覆蓋的大小; 在C [ 0 : m - 1 ]中返回覆蓋
int n = Ve r t i c e s ( ) ;
// 插件結(jié)構(gòu)
int SizeOfA = 0;
for (int i = 1; i <= n; i++) // 確定集合A的大小
if (L[i] == 1) SizeOfA++;
int SizeOfB = n - SizeOfA;
CreateBins(SizeOfB, n);
int *New = new int [n+1]; / /頂點(diǎn)i覆蓋了Ｂ中N e w [ i ]個未被覆蓋的頂點(diǎn)
bool *Change = new bool [n+1]; // Change[i]為t r u e當(dāng)且僅當(dāng)New[i] 已改變
bool *Cov = new bool [n+1]; // Cov[i] 為true 當(dāng)且僅當(dāng)頂點(diǎn)i 被覆蓋
I n i t i a l i z e P o s ( ) ;
LinkedStack<int> S;
// 初始化
for (i = 1; i <= n; i++) {
Cov[i] = Change[i] = false;
if (L[i] == 1) {// i 在A中
New[i] = Degree(i); // i 覆蓋了這么多
InsertBins(New[i], i);}}
// 構(gòu)造覆蓋
int covered = 0, // 被覆蓋的頂點(diǎn)
MaxBin = SizeOfB; // 可能非空的最大箱子
m = 0; // C的游標(biāo)
while (MaxBin > 0) { // 搜索所有箱子
// 選擇一個頂點(diǎn)
if (bin[MaxBin]) { // 箱子不空
int v = bin[MaxBin]; // 第一個頂點(diǎn)
C[m++] = v; // 把v 加入覆蓋
// 標(biāo)記新覆蓋的頂點(diǎn)
int j = Begin(v), k;
while (j) {
if (!Cov[j]) {// j尚未被覆蓋
Cov[j] = true;
c o v e r e d + + ;
// 修改N e w
k = Begin(j);
while (k) {
New[k]--; // j 不計入在內(nèi)
if (!Change[k]) {
S.Add(k); // 僅入棧一次
Change[k] = true;}
k = NextVe r t e x ( j ) ; }
}
j = NextVe r t e x ( v ) ; }
// 更新箱子
while (!S.IsEmpty()) {
S . D e l e t e ( k ) ;
Change[k] = false;
MoveBins(SizeOfB, New[k], k);}
}
else MaxBin--;
}
D e a c t i v a t e P o s ( ) ;
D e s t r o y B i n s ( ) ;
delete [] New;
delete [] Change;
delete [] Cov;
return (covered == SizeOfB);
}
程序1 3 - 4首先計算出集合A和B的大小、初始化必要的雙向鏈表結(jié)構(gòu)、創(chuàng)建三個數(shù)組、初始化圖遍歷器、并創(chuàng)建一個棧。然后將數(shù)組C o v和C h a n g e初始化為f a l s e，并將A中的頂點(diǎn)根據(jù)它們覆蓋B中頂點(diǎn)的數(shù)目插入到相應(yīng)的雙向鏈表中。
為了構(gòu)造覆蓋，首先按SizeOfB 遞減至1的順序檢查雙向鏈表。當(dāng)發(fā)現(xiàn)一個非空的表時，就將其第一個頂點(diǎn)v 加入到覆蓋中，這種策略即為選擇具有最大Ne o v [ j ]置為t r u e，表示頂點(diǎn)j 現(xiàn)在已被覆蓋，同時將已被覆蓋的B中的頂點(diǎn)數(shù)目加1。由于j 是最近被覆w 值的頂點(diǎn)。將所選擇的頂點(diǎn)加入覆蓋數(shù)組C并檢查B中所有與它鄰接的頂點(diǎn)。若頂點(diǎn)j 與v 鄰接且還未被覆蓋，則將C蓋的，所有A中與j 鄰接的頂點(diǎn)的New 值減1。下一個while 循環(huán)降低這些New 值并將New 值被降低的頂點(diǎn)保存在一個棧中。當(dāng)所有與頂點(diǎn)v鄰接的頂點(diǎn)的Cov 值更新完畢后，N e w值反映了A中每個頂點(diǎn)所能覆蓋的新的頂點(diǎn)數(shù)，然而A中的頂點(diǎn)由于New 值被更新，處于錯誤的雙向鏈表中，下一個while 循環(huán)則將這些頂點(diǎn)移到正確的表中。
1.3.5 單源最短路徑
在這個問題中，給出有向圖G，它的每條邊都有一個非負(fù)的長度（耗費(fèi)） a [i ][ j ]，路徑的長度即為此路徑所經(jīng)過的邊的長度之和。對于給定的源頂點(diǎn)s，需找出從它到圖中其他任意頂點(diǎn)（稱為目的）的最短路徑。圖13-10a 給出了一個具有五個頂點(diǎn)的有向圖，各邊上的數(shù)即為長度。假設(shè)源頂點(diǎn)s 為1，從頂點(diǎn)1出發(fā)的最短路徑按路徑長度順序列在圖13-10b 中，每條路徑前面的數(shù)字為路徑的長度。
利用E. Dijkstra發(fā)明的貪婪算法可以解決最短路徑問題，它通過分步方法求出最短路徑。每一步產(chǎn)生一個到達(dá)新的目的頂點(diǎn)的最短路徑。下一步所能達(dá)到的目的頂點(diǎn)通過如下貪婪準(zhǔn)則選?。涸谶€未產(chǎn)生最短路徑的頂點(diǎn)中，選擇路徑長度最短的目的頂點(diǎn)。也就是說， D i j k s t r a的方法按路徑長度順序產(chǎn)生最短路徑。
首先最初產(chǎn)生從s 到它自身的路徑，這條路徑?jīng)]有邊，其長度為0。在貪婪算法的每一步中，產(chǎn)生下一個最短路徑。一種方法是在目前已產(chǎn)生的最短路徑中加入一條可行的最短的邊，結(jié)果產(chǎn)生的新路徑是原先產(chǎn)生的最短路徑加上一條邊。這種策略并不總是起作用。另一種方法是在目前產(chǎn)生的每一條最短路徑中，考慮加入一條最短的邊，再從所有這些邊中先選擇最短的，這種策略即是D i j k s t r a算法。
可以驗(yàn)證按長度順序產(chǎn)生最短路徑時，下一條最短路徑總是由一條已產(chǎn)生的最短路徑加上一條邊形成。實(shí)際上，下一條最短路徑總是由已產(chǎn)生的最短路徑再擴(kuò)充一條最短的邊得到的，且這條路徑所到達(dá)的頂點(diǎn)其最短路徑還未產(chǎn)生。例如在圖1 3 - 1 0中，b 中第二條路徑是第一條路徑擴(kuò)充一條邊形成的；第三條路徑則是第二條路徑擴(kuò)充一條邊；第四條路徑是第一條路徑擴(kuò)充一條邊；第五條路徑是第三條路徑擴(kuò)充一條邊。
通過上述觀察可用一種簡便的方法來存儲最短路徑?？梢岳脭?shù)組p，p [ i ]給出從s 到達(dá)i的路徑中頂點(diǎn)i 前面的那個頂點(diǎn)。在本例中p [ 1 : 5 ] = [ 0 , 1 , 1 , 3 , 4 ]。從s 到頂點(diǎn)i 的路徑可反向創(chuàng)建。從i 出發(fā)按p[i],p[p[i]],p[p[p[i]]], .的順序，直到到達(dá)頂點(diǎn)s 或0。在本例中，如果從i = 5開始，則頂點(diǎn)序列為p[i]=4, p[4]=3, p[3]=1=s，因此路徑為1 , 3 , 4 , 5。
為能方便地按長度遞增的順序產(chǎn)生最短路徑，定義d [ i ]為在已產(chǎn)生的最短路徑中加入一條最短邊的長度，從而使得擴(kuò)充的路徑到達(dá)頂點(diǎn)i。最初，僅有從s 到s 的一條長度為0的路徑，這時對于每個頂點(diǎn)i，d [ i ]等于a [ s ] [ i ]（a 是有向圖的長度鄰接矩陣）。為產(chǎn)生下一條路徑，需要選擇還未產(chǎn)生最短路徑的下一個節(jié)點(diǎn)，在這些節(jié)點(diǎn)中d值最小的即為下一條路徑的終點(diǎn)。當(dāng)獲得一條新的最短路徑后，由于新的最短路徑可能會產(chǎn)生更小的d值，因此有些頂點(diǎn)的d值可能會發(fā)生變化。
綜上所述，可以得到圖1 3 - 11所示的偽代碼， 1) 將與s 鄰接的所有頂點(diǎn)的p 初始化為s，這個初始化用于記錄當(dāng)前可用的最好信息。也就是說，從s 到i 的最短路徑，即是由s到它自身那條路徑再擴(kuò)充一條邊得到。當(dāng)找到更短的路徑時， p [ i ]值將被更新。若產(chǎn)生了下一條最短路徑，需要根據(jù)路徑的擴(kuò)充邊來更新d 的值。
1) 初始化d[i ] =a[s] [i ]（1≤i≤n），
對于鄰接于s的所有頂點(diǎn)i，置p[i ] =s, 對于其余的頂點(diǎn)置p[i ] = 0；
對于p[i]≠0的所有頂點(diǎn)建立L表。
2) 若L為空，終止，否則轉(zhuǎn)至3 )。
3) 從L中刪除d值最小的頂點(diǎn)。
4) 對于與i 鄰接的所有還未到達(dá)的頂點(diǎn)j，更新d[ j ]值為m i n{d[ j ], d[i ] +a[i ][ j ] }；若d[ j ]發(fā)生了變化且j 還未
在L中，則置p[ j ] = 1，并將j 加入L，轉(zhuǎn)至2。
圖1 - 11 最短路徑算法的描述
1. 數(shù)據(jù)結(jié)構(gòu)的選擇
我們需要為未到達(dá)的頂點(diǎn)列表L選擇一個數(shù)據(jù)結(jié)構(gòu)。從L中可以選出d 值最小的頂點(diǎn)。如果L用最小堆（見9 . 3節(jié)）來維護(hù)，則這種選取可在對數(shù)時間內(nèi)完成。由于3) 的執(zhí)行次數(shù)為O ( n )，所以所需時間為O ( n l o g n )。由于擴(kuò)充一條邊產(chǎn)生新的最短路徑時，可能使未到達(dá)的頂點(diǎn)產(chǎn)生更小的d 值，所以在4) 中可能需要改變一些d 值。雖然算法中的減操作并不是標(biāo)準(zhǔn)的最小堆操作，但它能在對數(shù)時間內(nèi)完成。由于執(zhí)行減操作的總次數(shù)為： O(有向圖中的邊數(shù))= O ( n2 )，因此執(zhí)行減操作的總時間為O ( n2 l o g n )。
若L用無序的鏈表來維護(hù)，則3) 與4) 花費(fèi)的時間為O ( n2 )，3) 的每次執(zhí)行需O(|L | ) =O( n )的時間，每次減操作需( 1 )的時間（需要減去d[j] 的值，但鏈表不用改變）。利用無序鏈表將圖1 - 11的偽代碼細(xì)化為程序1 3 - 5，其中使用了C h a i n (見程序3 - 8 )和C h a i n I t e r a t o r類（見程序3 - 1 8）。
程序13-5 最短路徑程序
template<class T>
void AdjacencyWDigraph<T>::ShortestPaths(int s, T d[], int p[])
{// 尋找從頂點(diǎn)s出發(fā)的最短路徑, 在d中返回最短距離
// 在p中返回前繼頂點(diǎn)
if (s < 1 || s > n) throw OutOfBounds();
Chain<int> L; // 路徑可到達(dá)頂點(diǎn)的列表
ChainIterator<int> I;
// 初始化d, p, L
for (int i = 1; i <= n; i++){
d[i] = a[s][i];
if (d[i] == NoEdge) p[i] = 0;
else {p[i] = s;
L . I n s e r t ( 0 , i ) ; }
}
// 更新d, p
while (!L.IsEmpty()) {// 尋找具有最小d的頂點(diǎn)v
int *v = I.Initialize(L);
int *w = I.Next();
while (w) {
if (d[*w] < d[*v]) v = w;
w = I.Next();}
// 從L中刪除通向頂點(diǎn)v的下一最短路徑并更新d
int i = *v;
L . D e l e t e ( * v ) ;
for (int j = 1; j <= n; j++) {
if (a[i][j] != NoEdge && (!p[j] ||
d[j] > d[i] + a[i][j])) {
// 減小d [ j ]
d[j] = d[i] + a[i][j];
// 將j加入L
if (!p[j]) L.Insert(0,j);
p[j] = i;}
}
}
}
若N o E d g e足夠大，使得沒有最短路徑的長度大于或等于N o E d g e，則最后一個for 循環(huán)的i f條件可簡化為：if (d[j] > d[i] + a[i][j])) NoEdge 的值應(yīng)在能使d[j]+a[i][j] 不會產(chǎn)生溢出的范圍內(nèi)。
2. 復(fù)雜性分析
程序1 3 - 5的復(fù)雜性是O ( n2 )，任何最短路徑算法必須至少對每條邊檢查一次，因?yàn)槿魏我粭l邊都有可能在最短路徑中。因此這種算法的最小可能時間為O ( e )。由于使用耗費(fèi)鄰接矩陣來描述圖，僅決定哪條邊在有向圖中就需O ( n2 )的時間。因此，采用這種描述方法的算法需花費(fèi)O ( n2 )的時間。不過程序1 3 - 5作了優(yōu)化（常數(shù)因子級）。即使改變鄰接表，也只會使最后一個f o r循環(huán)的總時間降為O ( e )（因?yàn)橹挥信ci 鄰接的頂點(diǎn)的d 值改變）。從L中選擇及刪除最小距離的頂點(diǎn)所需總時間仍然是O( n2 )。
1.3.6 最小耗費(fèi)生成樹
在例1 - 2及1 - 3中已考察過這個問題。因?yàn)榫哂衝 個頂點(diǎn)的無向網(wǎng)絡(luò)G的每個生成樹剛好具有n-1條邊，所以問題是用某種方法選擇n-1條邊使它們形成G的最小生成樹。至少可以采用三種不同的貪婪策略來選擇這n-1條邊。這三種求解最小生成樹的貪婪算法策略是： K r u s k a l算法，P r i m算法和S o l l i n算法。
1. Kruskal算法
(1) 算法思想
K r u s k a l算法每次選擇n- 1條邊，所使用的貪婪準(zhǔn)則是：從剩下的邊中選擇一條不會產(chǎn)生環(huán)路的具有最小耗費(fèi)的邊加入已選擇的邊的集合中。注意到所選取的邊若產(chǎn)生環(huán)路則不可能形成一棵生成樹。K r u s k a l算法分e 步，其中e 是網(wǎng)絡(luò)中邊的數(shù)目。按耗費(fèi)遞增的順序來考慮這e 條邊，每次考慮一條邊。當(dāng)考慮某條邊時，若將其加入到已選邊的集合中會出現(xiàn)環(huán)路，則將其拋棄，否則，將它選入。
考察圖1-12a 中的網(wǎng)絡(luò)。初始時沒有任何邊被選擇。圖13-12b 顯示了各節(jié)點(diǎn)的當(dāng)前狀態(tài)。邊（ 1 , 6）是最先選入的邊，它被加入到欲構(gòu)建的生成樹中，得到圖1 3 - 1 2 c。下一步選擇邊（ 3，4）并將其加入樹中（如圖1 3 - 1 2 d所示）。然后考慮邊( 2，7 )，將它加入樹中并不會產(chǎn)生環(huán)路，于是便得到圖1 3 - 1 2 e。下一步考慮邊（ 2，3）并將其加入樹中（如圖1 3 - 1 2 f所示）。在其余還未考慮的邊中，（7，4）具有最小耗費(fèi)，因此先考慮它，將它加入正在創(chuàng)建的樹中會產(chǎn)生環(huán)路，所以將其丟棄。此后將邊（ 5，4）加入樹中，得到的樹如圖13-12g 所示。下一步考慮邊（ 7，5），由于會產(chǎn)生環(huán)路，將其丟棄。最后考慮邊（ 6，5）并將其加入樹中，產(chǎn)生了一棵生成樹，其耗費(fèi)為9 9。圖1 - 1 3給出了K r u s k a l算法的偽代碼。
/ /在一個具有n 個頂點(diǎn)的網(wǎng)絡(luò)中找到一棵最小生成樹
令T為所選邊的集合，初始化T=
令E 為網(wǎng)絡(luò)中邊的集合
w h i l e(E≠ )&&(| T |≠n- 1 ) {
令(u,v)為E中代價最小的邊 E=E- { (u,v) } / /從E中刪除邊
i f( (u,v)加入T中不會產(chǎn)生環(huán)路)將（ u,v）加入T
}
i f(| T | = =n-1) T是最小耗費(fèi)生成樹
e l s e 網(wǎng)絡(luò)不是互連的，不能找到生成樹
圖13-13 Kruskao算法的偽代碼
(2) 正確性證明
利用前述裝載問題所用的轉(zhuǎn)化技術(shù)可以證明圖1 3 - 1 3的貪婪算法總能建立一棵最小耗費(fèi)生成樹。需要證明以下兩點(diǎn)： 1) 只要存在生成樹，K r u s k a l算法總能產(chǎn)生一棵生成樹； 2) 產(chǎn)生的生成樹具有最小耗費(fèi)。令G為任意加權(quán)無向圖（即G是一個無向網(wǎng)絡(luò)）。從1 2 . 11 . 3節(jié)可知當(dāng)且僅當(dāng)一個無向圖連通時它有生成樹。而且在Kruskal 算法中被拒絕（丟棄）的邊是那些會產(chǎn)生環(huán)路的邊。刪除連通圖環(huán)路中的一條邊所形成的圖仍是連通圖，因此如果G在開始時是連通的，則T與E中的邊總能形成一個連通圖。也就是若G開始時是連通的，算法不會終止于E= 和| T |< n- 1。
現(xiàn)在來證明所建立的生成樹T具有最小耗費(fèi)。由于G具有有限棵生成樹，所以它至少具有一棵最小生成樹。令U為這樣的一棵最小生成樹， T與U都剛好有n- 1條邊。如果T=U, 則T就具有最小耗費(fèi)，那么不必再證明下去。因此假設(shè)T≠U，令k(k >0) 為在T中而不在U中的邊的個數(shù)，當(dāng)然k 也是在U中而不在T中的邊的數(shù)目。 通過把U變換為T來證明U與T具有相同的耗費(fèi)，這種轉(zhuǎn)化可在k 步內(nèi)完成。每一步使在T而不在U中的邊的數(shù)目剛好減1。而且U的耗費(fèi)不會因?yàn)檗D(zhuǎn)化而改變。經(jīng)過k 步的轉(zhuǎn)化得到的U將與原來的U具有相同的耗費(fèi)，且轉(zhuǎn)化后U中的邊就是T中的邊。由此可知， T具有最小耗費(fèi)。每步轉(zhuǎn)化包括從T中移一條邊e 到U中，并從U中移出一條邊f(xié)。邊e 與f 的選取按如下方式進(jìn)行：
1) 令e 是在T中而不在U中的具有最小耗費(fèi)的邊。由于k >0，這條邊肯定存在。
2) 當(dāng)把e 加入U時，則會形成唯一的一條環(huán)路。令f 為這條環(huán)路上不在T中的任意一條邊。
由于T中不含環(huán)路，因此所形成的環(huán)路中至少有一條邊不在T中。
從e 與f 的選擇方法中可以看出， V=U+ -{ f } 是一棵生成樹，且T中恰有k- 1條邊不在V中出現(xiàn)?，F(xiàn)在來證明V的耗費(fèi)與U的相同。顯然，V的耗費(fèi)等于U的耗費(fèi)加上邊e 的耗費(fèi)再減去邊f(xié) 的耗費(fèi)。若e 的耗費(fèi)比f 的小，則生成樹V的耗費(fèi)比U的耗費(fèi)小，這是不可能的。如果e 的耗費(fèi)高于f，在K r u s k a l算法中f 會在e 之前被考慮。由于f 不在T中，Kruskal 算法在考慮f 能否加入T時已將f 丟棄，因此f 和T中耗費(fèi)小于或等于f 的邊共同形成環(huán)路。通過選擇e，所有這些邊均在U中，因此U肯定含有環(huán)路，但是實(shí)際上這不可能，因?yàn)閁是一棵生成樹。e 的代價高于f 的假設(shè)將會導(dǎo)致矛盾。剩下的唯一的可能是e 與f 具有相同的耗費(fèi)，由此可知V與U的耗費(fèi)相同。
(3) 數(shù)據(jù)結(jié)構(gòu)的選擇及復(fù)雜性分析
為了按耗費(fèi)非遞減的順序選擇邊，可以建立最小堆并根據(jù)需要從堆中一條一條地取出各邊。當(dāng)圖中有e 條邊時，需花(e) 的時間初始化堆及O ( l o ge) 的時間來選取每一條邊。邊的集合T與G中的頂點(diǎn)一起定義了一個由至多n 個連通子圖構(gòu)成的圖。用頂點(diǎn)集合來描述每個子圖，這些頂點(diǎn)集合沒有公共頂點(diǎn)。為了確定邊（ u,v）是否會產(chǎn)生環(huán)路，僅需檢查u,v 是否在同一個頂點(diǎn)集中（即處于同一子圖）。如果是，則會形成一個環(huán)路；如果不是，則不會產(chǎn)生環(huán)路。因此對于頂點(diǎn)集使用兩個F i n d操作就足夠了。當(dāng)一條邊包含在T中時，2個子圖將被合并成一個子圖，即對兩個集合執(zhí)行U n i o n操作。集合的F i n d和U n i o n操作可利用8 . 1 0 . 2節(jié)的樹（以及加權(quán)規(guī)則和路徑壓縮）來高效地執(zhí)行。F i n d操作的次數(shù)最多為2e，Un i o n操作的次數(shù)最多為n- 1（若網(wǎng)絡(luò)是連通的，則剛好是n- 1次）。加上樹的初始化時間，算法中這部分的復(fù)雜性只比O (n+e) 稍大一點(diǎn)。
對集合T所執(zhí)行的唯一操作是向T中添加一條新邊。T可用數(shù)組t 來實(shí)現(xiàn)。添加操作在數(shù)組
的一端進(jìn)行，因?yàn)樽疃嗫稍赥中加入n- 1條邊，因此對T的操作總時間為O (n)。
總結(jié)上述各個部分的執(zhí)行時間，可得圖1 3 - 1 3算法的漸進(jìn)復(fù)雜性為O (n+el o ge)。
(4) 實(shí)現(xiàn)
利用上述數(shù)據(jù)結(jié)構(gòu)，圖1 - 1 3可用C + +代碼來實(shí)現(xiàn)。首先定義E d g e N o d e類（見程序1 3 - 6 )，它是最小堆的元素及生成樹數(shù)組t 的數(shù)據(jù)類型。
程序13-6 Kruskal算法所需要的數(shù)據(jù)類型
template
class EdgeNode {
p u b l i c :
operator T() const {return weight;}
p r i v a t e :
T weight;//邊的高度
int u, v;//邊的端點(diǎn)
} ;
為了更簡單地使用8 . 1 0 . 2節(jié)的查找和合并策略，定義了U n i o n F i n d類，它的構(gòu)造函數(shù)是程序8 - 1 6的初始化函數(shù)，U n i o n是程序8 - 1 6的加權(quán)合并函數(shù)，F(xiàn) i n d是程序8 - 1 7的路徑壓縮搜索函數(shù)。
為了編寫與網(wǎng)絡(luò)描述無關(guān)的代碼，還定義了一個新的類U N e t Wo r k，它包含了應(yīng)用于無向網(wǎng)絡(luò)的所有函數(shù)。這個類與U n d i r e c t e d類的差別在于U n d i r e c t e d類中的函數(shù)不要求加權(quán)邊，而U N e t Wo r k要求邊必須帶有權(quán)值。U N e t Wo r k中的成員需要利用N e t w o r k類中定義的諸如B e g i n和N e x t Ve r t e x的遍歷函數(shù)。不過，新的遍歷函數(shù)不僅需要返回下一個鄰接的頂點(diǎn)，而且要返回到達(dá)這個頂點(diǎn)的邊的權(quán)值。這些遍歷函數(shù)以及有向和無向加權(quán)網(wǎng)絡(luò)的其他函數(shù)一起構(gòu)成了W N e t w o r k類（見程序1 3 - 7）。
程序13-7 WNetwork類
template
class WNetwork : virtual public Network
{
public :
virtual void First(int i, int& j, T& c)=0;
virtual void Next(int i, int& j, T& c)=0;
} ;
象B e g i n和N e x t Ve r t e x一樣，可在A d j a c e n c y W D i g r a p h及L i n k e d W D i g r a p h類中加入函數(shù)F i r s t與N e x t。現(xiàn)在A d j a c e n c y W D i g r a p h及L i n k e d W D i g r a p h類都需要從W N e t Wo r k中派生而來。由于A d j a c e n c y W G r a p h類和L i n k e d W G r a p h類需要訪問U N e t w o r k的成員，所以這兩個類還必須從U N e t Wo r k中派生而來。U N e t Wo r k : : K r u s k a l的代碼見程序1 3 - 8，它要求將Edges() 定義為N e t Work 類的虛成員，并且把U N e t Wo r k定義為E d g e N o d e的友元）。如果沒有生成樹，函數(shù)返回f a l s e，否則返回t r u e。注意當(dāng)返回true 時，在數(shù)組t 中返回最小耗費(fèi)生成樹。
程序13-8 Kr u s k a l算法的C + +代碼
template
bool UNetwork::Kruskal(EdgeNode t[])
{// 使用K r u s k a l算法尋找最小耗費(fèi)生成樹
// 如果不連通則返回false
// 如果連通，則在t [ 0 : n - 2 ]中返回最小生成樹
int n = Ve r t i c e s ( ) ;
int e = Edges();
/ /設(shè)置網(wǎng)絡(luò)邊的數(shù)組
InitializePos(); // 圖遍歷器
EdgeNode *E = new EdgeNode [e+1];
int k = 0; // E的游標(biāo)
for (int i = 1; i <= n; i++) { // 使所有邊附屬于i
int j;
T c;
First(i, j, c);
while (j) { // j 鄰接自i
if (i < j) {// 添加到達(dá)E的邊
E[++k].weight = c;
E[k].u = i;
E[k].v = j;}
Next(i, j, c);
}
}
// 把邊放入最小堆
MinHeap > H(1);
H.Initialize(E, e, e);
UnionFind U(n); // 合并/搜索結(jié)構(gòu)
// 根據(jù)耗費(fèi)的次序來抽取邊
k = 0; // 此時作為t的游標(biāo)
while (e && k < n - 1) {
// 生成樹未完成，尚有剩余邊
EdgeNode x;
H.DeleteMin(x); // 最小耗費(fèi)邊
e - - ;
int a = U.Find(x.u);
int b = U.Find(x.v);
if (a != b) {// 選擇邊
t[k++] = x;
U . U n i o n ( a , b ) ; }
}
D e a c t i v a t e P o s ( ) ;
H . D e a c t i v a t e ( ) ;
return (k == n - 1);
}
2. Prim算法
與Kr u s k a l算法類似，P r i m算法通過每次選擇多條邊來創(chuàng)建最小生成樹。選擇下一條邊的貪婪準(zhǔn)則是：從剩余的邊中，選擇一條耗費(fèi)最小的邊，并且它的加入應(yīng)使所有入選的邊仍是一棵樹。最終，在所有步驟中選擇的邊形成一棵樹。相反，在Kruskal 算法中所有入選的邊集合最終形成一個森林。
P r i m算法從具有一個單一頂點(diǎn)的樹T開始，這個頂點(diǎn)可以是原圖中任意一個頂點(diǎn)。然后往T中加入一條代價最小的邊（ u , v）使Tè{ (u , v) }仍是一棵樹，這種加邊的步驟反復(fù)循環(huán)直到T中包含n- 1條邊。注意對于邊（ u , v），u、v 中正好有一個頂點(diǎn)位于T中。P r i m算法的偽代碼如圖1 -1 4所示。在偽代碼中也包含了所輸入的圖不是連通圖的可能，在這種情況下沒有生成樹。圖1 - 1 5顯示了對圖1-12a 使用P r i m算法的過程。把圖1 - 1 4的偽代碼細(xì)化為C + +程序及其正確性的證明留作練習(xí)（練習(xí)3 1）。
/ /假設(shè)網(wǎng)絡(luò)中至少具有一個頂點(diǎn)
設(shè)T為所選擇的邊的集合，初始化T=
設(shè)T V為已在樹中的頂點(diǎn)的集合，置T V= { 1 }
令E為網(wǎng)絡(luò)中邊的集合
w h i l e(E< > ) & & (| T | < > n-1) {
令（u , v）為最小代價邊，其中u T V, v T V
i f（沒有這種邊） b re a k
E=E- { (u,v) } / /從E中刪除此邊
在T中加入邊（ u , v）
}
if (| T | = =n- 1 ) T是一棵最小生成樹
else 網(wǎng)絡(luò)是不連通的，沒有最小生成樹
圖13-14 Prim最小生成樹算法
如果根據(jù)每個不在T V中的頂點(diǎn)v 選擇一個頂點(diǎn)n e ar (v)，使得n e ar (v) ? TV 且c o st (v, n e ar (v) )的值是所有這樣的n e ar (v) 節(jié)點(diǎn)中最小的，則實(shí)現(xiàn)P r i m算法的時間復(fù)雜性為O (n2 )。下一條添加到T中的邊是這樣的邊：其cost (v, near (v)) 最小，且v T V。
3. Sollin算法
S o l l i n算法每步選擇若干條邊。在每步開始時，所選擇的邊及圖中的n個頂點(diǎn)形成一個生成樹的森林。在每一步中為森林中的每棵樹選擇一條邊，這條邊剛好有一個頂點(diǎn)在樹中且邊的代價最小。將所選擇的邊加入要創(chuàng)建的生成樹中。注意一個森林中的兩棵樹可選擇同一條邊，因此必須多次復(fù)制同一條邊。當(dāng)有多條邊具有相同的耗費(fèi)時，兩棵樹可選擇與它們相連的不同的邊，在這種情況下，必須丟棄其中的一條邊。開始時，所選擇的邊的集合為空。若某一步結(jié)束時僅剩下一棵樹或沒有剩余的邊可供選擇時算法終止。
圖1 - 6給出了初始狀態(tài)為圖1-12a 時，使用S o l l i n算法的步驟。初始入選邊數(shù)為0時的情形如圖13-12a 時,森林中的每棵樹均是單個頂點(diǎn)。頂點(diǎn)1，2，.，7所選擇的邊分別是(1.6), (2,7),(3,4), (4,3), (5,4), (6,1), (7,2)，其中不同的邊是( 1 , 6 )，( 2 , 7 )，(3,4) 和( 5 , 4 )，將這些邊加入入選邊的集合后所得到的結(jié)果如圖1 3 - 1 6 a所示。下一步具有頂點(diǎn)集{ 1 , 6 }的樹選擇邊( 6 , 5 )，剩下的兩棵樹選擇邊( 2 , 3 )，加入這兩條邊后已形成一棵生成樹，構(gòu)建好的生成樹見圖1 3 - 6 b。S o l l i n算法的C + +程序?qū)崿F(xiàn)及其正確性證明留作練習(xí)（練習(xí)3 2 )。