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