第1 章 貪婪算法.doc

第 1 章 貪婪算法雖然設(shè)計(jì)一個(gè)好的求解算法更像是一門藝術(shù)，而不像是技術(shù)，但仍然存在一些行之有效的能夠用于解決許多問(wèn)題的算法設(shè)計(jì)方法，你可以使用這些方法來(lái)設(shè)計(jì)算法，并觀察這些算法是如何工作的。一般情況下，為了獲得較好的性能，必須對(duì)算法進(jìn)行細(xì)致的調(diào)整。但是在某些情況下，算法經(jīng)過(guò)調(diào)整之后性能仍無(wú)法達(dá)到要求，這時(shí)就必須尋求另外的方法來(lái)求解該問(wèn)題。本章首先引入最優(yōu)化的概念，然后介紹一種直觀的問(wèn)題求解方法：貪婪算法。最后，應(yīng)用該算法給出貨箱裝船問(wèn)題、背包問(wèn)題、拓?fù)渑判騿?wèn)題、二分覆蓋問(wèn)題、最短路徑問(wèn)題、最小代價(jià)生成樹等問(wèn)題的求解方案。1.1 最優(yōu)化問(wèn)題本章及后續(xù)章節(jié)中的許多例子都是最優(yōu)化問(wèn)題（ optimization problem），每個(gè)最優(yōu)化問(wèn)題都包含一組限制條件（ c o n s t r a i n t）和一個(gè)優(yōu)化函數(shù)（ optimization function），符合限制條件的問(wèn)題求解方案稱為可行解（ feasible solution），使優(yōu)化函數(shù)取得最佳值的可行解稱為最優(yōu)解（optimal solution）。例1-1 渴嬰問(wèn)題 有一個(gè)非?？实摹⒙斆鞯男雰?，她可能得到的東西包括一杯水、一桶牛奶、多罐不同種類的果汁、許多不同的裝在瓶子或罐子中的蘇打水，即嬰兒可得到n 種不同的飲料。根據(jù)以前關(guān)于這n 種飲料的不同體驗(yàn)，此嬰兒知道這其中某些飲料更合自己的胃口，因此，嬰兒采取如下方法為每一種飲料賦予一個(gè)滿意度值：飲用1盎司第i 種飲料，對(duì)它作出相對(duì)評(píng)價(jià)，將一個(gè)數(shù)值si 作為滿意度賦予第i 種飲料。通常，這個(gè)嬰兒都會(huì)盡量飲用具有最大滿意度值的飲料來(lái)最大限度地滿足她解渴的需要，但是不幸的是：具有最大滿意度值的飲料有時(shí)并沒(méi)有足夠的量來(lái)滿足此嬰兒解渴的需要。設(shè)ai是第i 種飲料的總量（以盎司為單位），而此嬰兒需要t 盎司的飲料來(lái)解渴，那么，需要飲用n種不同的飲料各多少量才能滿足嬰兒解渴的需求呢？設(shè)各種飲料的滿意度已知。令xi 為嬰兒將要飲用的第i 種飲料的量，則需要解決的問(wèn)題是：找到一組實(shí)數(shù)xi（1in），使n i = 1si xi 最大，并滿足：n i=1xi =t 及0xiai 。需要指出的是：如果n i = 1ai t，則不可能找到問(wèn)題的求解方案，因?yàn)榧词购裙馑械娘嬃弦膊荒苁箣雰航饪省?duì)上述問(wèn)題精確的數(shù)學(xué)描述明確地指出了程序必須完成的工作，根據(jù)這些數(shù)學(xué)公式，可以對(duì)輸入/ 輸出作如下形式的描述：輸入：n，t，si ，ai（其中1in，n 為整數(shù)，t、si 、ai 為正實(shí)數(shù)）。輸出：實(shí)數(shù)xi（1in），使n i= 1si xi 最大且n i=1xi =t（0xiai）。如果n i = 1ai t，則輸出適當(dāng)?shù)腻e(cuò)誤信息。在這個(gè)問(wèn)題中，限制條件是n i= 1xi =t 且0xiai，1in。而優(yōu)化函數(shù)是n i= 1si xi 。任何滿足限制條件的一組實(shí)數(shù)xi 都是可行解，而使n i= 1si xi 最大的可行解是最優(yōu)解。例1-2 裝載問(wèn)題 有一艘大船準(zhǔn)備用來(lái)裝載貨物。所有待裝貨物都裝在貨箱中且所有貨箱的大小都一樣，但貨箱的重量都各不相同。設(shè)第i 個(gè)貨箱的重量為wi（1in），而貨船的最大載重量為c，我們的目的是在貨船上裝入最多的貨物。這個(gè)問(wèn)題可以作為最優(yōu)化問(wèn)題進(jìn)行描述：設(shè)存在一組變量xi ，其可能取值為0或1。如xi 為0，則貨箱i 將不被裝上船；如xi 為1，則貨箱i 將被裝上船。我們的目的是找到一組xi ，使它滿足限制條件n i = 1wi xi c 且x i 0, 1, 1 in。相應(yīng)的優(yōu)化函數(shù)是n i= 1xi 。滿足限制條件的每一組xi 都是一個(gè)可行解，能使n i= 1xi 取得最大值的方案是最優(yōu)解。例1-3 最小代價(jià)通訊網(wǎng)絡(luò) 城市及城市之間所有可能的通信連接可被視作一個(gè)無(wú)向圖，圖的每條邊都被賦予一個(gè)權(quán)值，權(quán)值表示建成由這條邊所表示的通信連接所要付出的代價(jià)。包含圖中所有頂點(diǎn)（城市）的連通子圖都是一個(gè)可行解。設(shè)所有的權(quán)值都非負(fù)，則所有可能的可行解都可表示成無(wú)向圖的一組生成樹，而最優(yōu)解是其中具有最小代價(jià)的生成樹。在這個(gè)問(wèn)題中，需要選擇一個(gè)無(wú)向圖中的邊集合的子集，這個(gè)子集必須滿足如下限制條件：所有的邊構(gòu)成一個(gè)生成樹。而優(yōu)化函數(shù)是子集中所有邊的權(quán)值之和。1.2 算法思想在貪婪算法（greedy method）中采用逐步構(gòu)造最優(yōu)解的方法。在每個(gè)階段，都作出一個(gè)看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。決策一旦作出，就不可再更改。作出貪婪決策的依據(jù)稱為貪婪準(zhǔn)則（greedy criterion）。例1-4 找零錢 一個(gè)小孩買了價(jià)值少于1美元的糖，并將1美元的錢交給售貨員。售貨員希望用數(shù)目最少的硬幣找給小孩。假設(shè)提供了數(shù)目不限的面值為2 5美分、1 0美分、5美分、及1美分的硬幣。售貨員分步驟組成要找的零錢數(shù)，每次加入一個(gè)硬幣。選擇硬幣時(shí)所采用的貪婪準(zhǔn)則如下：每一次選擇應(yīng)使零錢數(shù)盡量增大。為保證解法的可行性（即：所給的零錢等于要找的零錢數(shù)），所選擇的硬幣不應(yīng)使零錢總數(shù)超過(guò)最終所需的數(shù)目。假設(shè)需要找給小孩6 7美分，首先入選的是兩枚2 5美分的硬幣，第三枚入選的不能是2 5美分的硬幣，否則硬幣的選擇將不可行（零錢總數(shù)超過(guò)6 7美分），第三枚應(yīng)選擇1 0美分的硬幣，然后是5美分的，最后加入兩個(gè)1美分的硬幣。貪婪算法有種直覺(jué)的傾向，在找零錢時(shí)，直覺(jué)告訴我們應(yīng)使找出的硬幣數(shù)目最少（至少是接近最少的數(shù)目）?？梢宰C明采用上述貪婪算法找零錢時(shí)所用的硬幣數(shù)目的確最少（見(jiàn)練習(xí)1）。例1-5 機(jī)器調(diào)度 現(xiàn)有n 件任務(wù)和無(wú)限多臺(tái)的機(jī)器，任務(wù)可以在機(jī)器上得到處理。每件任務(wù)的開(kāi)始時(shí)間為si，完成時(shí)間為fi ，si k。尋找 1 ,n范圍內(nèi)最小的整數(shù)j，使得xjyj 。若沒(méi)有這樣的j 存在，則n i= 1xi =n i = 1yi 。如果有這樣的j 存在，則jk，否則y 就不是一個(gè)可行解，因?yàn)閤jyj ，xj = 1且yj = 0。令yj = 1，若結(jié)果得到的y 不是可行解，則在 j+ 1 ,n范圍內(nèi)必有一個(gè)l 使得yl = 1。令yl = 0，由于wjwl ，則得到的y 是可行的。而且，得到的新y 至少與原來(lái)的y 具有相同數(shù)目的1。經(jīng)過(guò)數(shù)次這種轉(zhuǎn)化，可將y 轉(zhuǎn)化為x。由于每次轉(zhuǎn)化產(chǎn)生的新y 至少與前一個(gè)y 具有相同數(shù)目的1，因此x 至少與初始的y 具有相同的數(shù)目1。貨箱裝載算法的C + +代碼實(shí)現(xiàn)見(jiàn)程序1 3 - 1。由于貪婪算法按貨箱重量遞增的順序裝載，程序1 3 - 1首先利用間接尋址排序函數(shù)I n d i r e c t S o r t對(duì)貨箱重量進(jìn)行排序（見(jiàn)3 . 5節(jié)間接尋址的定義），隨后貨箱便可按重量遞增的順序裝載。由于間接尋址排序所需的時(shí)間為O (nl o gn)（也可利用9 . 5 . 1節(jié)的堆排序及第2章的歸并排序），算法其余部分所需時(shí)間為O (n)，因此程序1 3 - 1的總的復(fù)雜性為O (nl o gn)。程序13-1 貨箱裝船templatevoid ContainerLoading(int x, T w, T c, int n)/ 貨箱裝船問(wèn)題的貪婪算法/ xi = 1 當(dāng)且僅當(dāng)貨箱i被裝載， 1=i=n/ c是船的容量, w 是貨箱的重量/ 對(duì)重量按間接尋址方式排序/ t 是間接尋址表int *t = new int n+1;I n d i r e c t S o r t ( w, t, n);/ 此時(shí), wti = wti+1, 1=in/ 初始化xfor (int i = 1; i = n; i+)xi = 0;/ 按重量次序選擇物品for (i = 1; i = n & wti = c; i+) xti = 1;c -= wti; / 剩余容量delete t;1.3.2 0/1背包問(wèn)題在0 / 1背包問(wèn)題中，需對(duì)容量為c 的背包進(jìn)行裝載。從n 個(gè)物品中選取裝入背包的物品，每件物品i 的重量為wi ，價(jià)值為pi 。對(duì)于可行的背包裝載，背包中物品的總重量不能超過(guò)背包的容量，最佳裝載是指所裝入的物品價(jià)值最高，即n i=1pi xi 取得最大值。約束條件為n i =1wi xic 和xi 0 , 1 ( 1in)。在這個(gè)表達(dá)式中，需求出xt 的值。xi = 1表示物品i 裝入背包中，xi =0 表示物品i 不裝入背包。0 / 1背包問(wèn)題是一個(gè)一般化的貨箱裝載問(wèn)題，即每個(gè)貨箱所獲得的價(jià)值不同。貨箱裝載問(wèn)題轉(zhuǎn)化為背包問(wèn)題的形式為：船作為背包，貨箱作為可裝入背包的物品。例1-8 在雜貨店比賽中你獲得了第一名，獎(jiǎng)品是一車免費(fèi)雜貨。店中有n 種不同的貨物。規(guī)則規(guī)定從每種貨物中最多只能拿一件，車子的容量為c，物品i 需占用wi 的空間，價(jià)值為pi 。你的目標(biāo)是使車中裝載的物品價(jià)值最大。當(dāng)然，所裝貨物不能超過(guò)車的容量，且同一種物品不得拿走多件。這個(gè)問(wèn)題可仿照0 / 1背包問(wèn)題進(jìn)行建模，其中車對(duì)應(yīng)于背包，貨物對(duì)應(yīng)于物品。0 / 1背包問(wèn)題有好幾種貪婪策略，每個(gè)貪婪策略都采用多步過(guò)程來(lái)完成背包的裝入。在每一步過(guò)程中利用貪婪準(zhǔn)則選擇一個(gè)物品裝入背包。一種貪婪準(zhǔn)則為：從剩余的物品中，選出可以裝入背包的價(jià)值最大的物品，利用這種規(guī)則，價(jià)值最大的物品首先被裝入（假設(shè)有足夠容量），然后是下一個(gè)價(jià)值最大的物品，如此繼續(xù)下去。這種策略不能保證得到最優(yōu)解。例如，考慮n=2, w=100,10,10, p =20,15,15, c = 1 0 5。當(dāng)利用價(jià)值貪婪準(zhǔn)則時(shí)，獲得的解為x= 1 , 0 , 0 ，這種方案的總價(jià)值為2 0。而最優(yōu)解為 0 , 1 , 1 ，其總價(jià)值為3 0。另一種方案是重量貪婪準(zhǔn)則是：從剩下的物品中選擇可裝入背包的重量最小的物品。雖然這種規(guī)則對(duì)于前面的例子能產(chǎn)生最優(yōu)解，但在一般情況下則不一定能得到最優(yōu)解。考慮n= 2 ,w=10,20, p=5,100, c= 2 5。當(dāng)利用重量貪婪策略時(shí)，獲得的解為x =1,0, 比最優(yōu)解 0 , 1 要差。還可以利用另一方案，價(jià)值密度pi /wi 貪婪算法，這種選擇準(zhǔn)則為：從剩余物品中選擇可裝入包的pi /wi 值最大的物品，這種策略也不能保證得到最優(yōu)解。利用此策略試解n= 3 ,w=20,15,15, p=40,25,25, c=30 時(shí)的最優(yōu)解。我們不必因所考察的幾個(gè)貪婪算法都不能保證得到最優(yōu)解而沮喪， 0 / 1背包問(wèn)題是一個(gè)N P-復(fù)雜問(wèn)題。對(duì)于這類問(wèn)題，也許根本就不可能找到具有多項(xiàng)式時(shí)間的算法。雖然按pi /wi 非遞（增）減的次序裝入物品不能保證得到最優(yōu)解，但它是一個(gè)直覺(jué)上近似的解。我們希望它是一個(gè)好的啟發(fā)式算法，且大多數(shù)時(shí)候能很好地接近最后算法。在6 0 0個(gè)隨機(jī)產(chǎn)生的背包問(wèn)題中，用這種啟發(fā)式貪婪算法來(lái)解有2 3 9題為最優(yōu)解。有5 8 3個(gè)例子與最優(yōu)解相差1 0 %，所有6 0 0個(gè)答案與最優(yōu)解之差全在2 5 %以內(nèi)。該算法能在O (nl o gn)時(shí)間內(nèi)獲得如此好的性能。我們也許會(huì)問(wèn)，是否存在一個(gè)x (x1 0 0 )，使得貪婪啟發(fā)法的結(jié)果與最優(yōu)值相差在x%以內(nèi)。答案是否定的。為說(shuō)明這一點(diǎn)，考慮例子n =2, w = 1 ,y, p= 1 0 , 9y, 和c= y。貪婪算法結(jié)果為x=1,0, 這種方案的值為1 0。對(duì)于y1 0 / 9，最優(yōu)解的值為9 y。因此，貪婪算法的值與最優(yōu)解的差對(duì)最優(yōu)解的比例為( ( 9y - 1 0)/9y* 1 0 0 ) %，對(duì)于大的y，這個(gè)值趨近于1 0 0 %。但是可以建立貪婪啟發(fā)式方法來(lái)提供解，使解的結(jié)果與最優(yōu)解的值之差在最優(yōu)值的x% (x100) 之內(nèi)。首先將最多k 件物品放入背包，如果這k 件物品重量大于c，則放棄它。否則，剩余的容量用來(lái)考慮將剩余物品按pi /wi 遞減的順序裝入。通過(guò)考慮由啟發(fā)法產(chǎn)生的解法中最多為k 件物品的所有可能的子集來(lái)得到最優(yōu)解。例13-9 考慮n =4, w=2,4,6,7, p=6,10,12,13, c = 11。當(dāng)k= 0時(shí)，背包按物品價(jià)值密度非遞減順序裝入，首先將物品1放入背包，然后是物品2，背包剩下的容量為5個(gè)單元，剩下的物品沒(méi)有一個(gè)合適的，因此解為x = 1 , 1 , 0 , 0 。此解獲得的價(jià)值為1 6?，F(xiàn)在考慮k = 1時(shí)的貪婪啟發(fā)法。最初的子集為 1 , 2 , 3 , 4 。子集 1 , 2 產(chǎn)生與k= 0時(shí)相同的結(jié)果，考慮子集 3 ，置x3 為1。此時(shí)還剩5個(gè)單位的容量，按價(jià)值密度非遞增順序來(lái)考慮如何利用這5個(gè)單位的容量。首先考慮物品1，它適合，因此取x1 為1，這時(shí)僅剩下3個(gè)單位容量了，且剩余物品沒(méi)有能夠加入背包中的物品。通過(guò)子集 3 開(kāi)始求解得結(jié)果為x = 1 , 0 , 1 , 0 ，獲得的價(jià)值為1 8。若從子集 4 開(kāi)始，產(chǎn)生的解為x = 1 , 0 , 0 , 1 ，獲得的價(jià)值為1 9?？紤]子集大小為0和1時(shí)獲得的最優(yōu)解為 1 , 0 , 0 , 1 。這個(gè)解是通過(guò)k= 1的貪婪啟發(fā)式算法得到的。若k= 2，除了考慮k0時(shí)總的時(shí)間開(kāi)銷為O (nk+1 )。實(shí)際觀察到的性能要好得多。1.3.3 拓?fù)渑判蛞粋€(gè)復(fù)雜的工程通常可以分解成一組小任務(wù)的集合，完成這些小任務(wù)意味著整個(gè)工程的完成。例如，汽車裝配工程可分解為以下任務(wù)：將底盤放上裝配線，裝軸，將座位裝在底盤上，上漆，裝剎車，裝門等等。任務(wù)之間具有先后關(guān)系，例如在裝軸之前必須先將底板放上裝配線。任務(wù)的先后順序可用有向圖表示稱為頂點(diǎn)活動(dòng)（ Activity On Vertex, AOV）網(wǎng)絡(luò)。有向圖的頂點(diǎn)代表任務(wù)，有向邊(i, j) 表示先后關(guān)系：任務(wù)j 開(kāi)始前任務(wù)i 必須完成。圖1 - 4顯示了六個(gè)任務(wù)的工程，邊（ 1 , 4）表示任務(wù)1在任務(wù)4開(kāi)始前完成，同樣邊（ 4 , 6）表示任務(wù)4在任務(wù)6開(kāi)始前完成，邊（1 , 4）與（4 , 6）合起來(lái)可知任務(wù)1在任務(wù)6開(kāi)始前完成，即前后關(guān)系是傳遞的。由此可知，邊（1 , 4）是多余的，因?yàn)檫叄? , 3）和（3 , 4）已暗示了這種關(guān)系。在很多條件下，任務(wù)的執(zhí)行是連續(xù)進(jìn)行的，例如汽車裝配問(wèn)題或平時(shí)購(gòu)買的標(biāo)有“需要裝配”的消費(fèi)品（自行車、小孩的秋千裝置，割草機(jī)等等）。我們可根據(jù)所建議的順序來(lái)裝配。在由任務(wù)建立的有向圖中，邊（ i, j）表示在裝配序列中任務(wù)i 在任務(wù)j 的前面，具有這種性質(zhì)的序列稱為拓?fù)湫蛄校╰opological orders或topological sequences)。根據(jù)任務(wù)的有向圖建立拓?fù)湫蛄械倪^(guò)程稱為拓?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)樵谶@個(gè)序列中任務(wù)4在3的前面，而任務(wù)有向圖中的邊為（ 3 , 4），這種序列與邊（ 3 , 4）及其他邊所指示的序列相矛盾。可用貪婪算法來(lái)建立拓?fù)湫蛄?。算法按從左到右的步驟構(gòu)造拓?fù)湫蛄?，每一步在排好的序列中加入一個(gè)頂點(diǎn)。利用如下貪婪準(zhǔn)則來(lái)選擇頂點(diǎn)：從剩下的頂點(diǎn)中，選擇頂點(diǎn)w，使得w 不存在這樣的入邊（ v,w），其中頂點(diǎn)v 不在已排好的序列結(jié)構(gòu)中出現(xiàn)。注意到如果加入的頂點(diǎn)w違背了這個(gè)準(zhǔn)則（即有向圖中存在邊（ v,w）且v 不在已構(gòu)造的序列中），則無(wú)法完成拓?fù)渑判?，因?yàn)轫旤c(diǎn)v 必須跟隨在頂點(diǎn)w 之后。貪婪算法的偽代碼如圖1 3 - 5所示。while 循環(huán)的每次迭代代表貪婪算法的一個(gè)步驟?，F(xiàn)在用貪婪算法來(lái)求解圖1 - 4的有向圖。首先從一個(gè)空序列V開(kāi)始，第一步選擇V的第一個(gè)頂點(diǎn)。此時(shí)，在有向圖中有兩個(gè)候選頂點(diǎn)1和2，若選擇頂點(diǎn)2，則序列V = 2，第一步完成。第二步選擇V的第二個(gè)頂點(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)算法失敗時(shí)，有向圖沒(méi)有拓?fù)湫蛄校?2) 若算法沒(méi)有失敗，V即是拓?fù)湫蛄小?) 即是用貪婪準(zhǔn)則來(lái)選取下一個(gè)頂點(diǎn)的直接結(jié)果， 1) 的證明見(jiàn)定理1 3 - 2，它證明了若算法失敗，則有向圖中有環(huán)路。若有向圖中包含環(huán)qj qj + 1.qk qj , 則它沒(méi)有拓?fù)湫蛄校驗(yàn)樵撔蛄邪凳玖藂j 一定要在qj 開(kāi)始前完成。定理1-2 如果圖1 3 - 5算法失敗，則有向圖含有環(huán)路。證明注意到當(dāng)失敗時(shí)| V |n, 且沒(méi)有候選頂點(diǎn)能加入V中，因此至少有一個(gè)頂點(diǎn)q1 不在V中，有向圖中必包含邊（ q2 , q1）且q2 不在V中，否則， q1 是可加入V的候選頂點(diǎn)。同樣，必有邊（q3 , q2）使得q3 不在V中，若q3 = q1 則q1 q2 q3 是有向圖中的一個(gè)環(huán)路；若q3 q1，則必存在q4 使（q4 , q3）是有向圖的邊且q4 不在V中，否則，q3 便是V的一個(gè)候選頂點(diǎn)。若q4 為q1 , q2 , q3 中的任何一個(gè)，則又可知有向圖含有環(huán)，因?yàn)橛邢驁D具有有限個(gè)頂點(diǎn)數(shù)n，繼續(xù)利用上述方法，最后總能找到一個(gè)環(huán)路。2. 數(shù)據(jù)結(jié)構(gòu)的選擇為將圖1 - 5用C + +代碼來(lái)實(shí)現(xiàn)，必須考慮序列V的描述方法，以及如何找出可加入V的候選頂點(diǎn)。一種高效的實(shí)現(xiàn)方法是將序列V用一維數(shù)組v 來(lái)描述的，用一個(gè)棧來(lái)保存可加入V的候選頂點(diǎn)。另有一個(gè)一維數(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)?時(shí)表示j 成為一個(gè)候選節(jié)點(diǎn)。序列V初始時(shí)為空。I n D e g r e e j 為頂點(diǎn)j 的入度。每次向V中加入一個(gè)頂點(diǎn)時(shí)，所有與新加入頂點(diǎn)鄰接的頂點(diǎn)j，其I n D e g r e e j 減1。對(duì)于有向圖1 - 4，開(kāi)始時(shí)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首先入棧。每一步，從棧中取出一個(gè)頂點(diǎn)將其加入V，同時(shí)減去與其鄰接的頂點(diǎn)的I n D e g r e e值。若在第一步時(shí)從棧中取出頂點(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 + +代碼，這個(gè)代碼被定義為N e t w o r k的一個(gè)成員函數(shù)。而且，它對(duì)于有無(wú)加權(quán)的有向圖均適用。但若用于無(wú)向圖（不論其有無(wú)加權(quán)）將會(huì)得到錯(cuò)誤的結(jié)果，因?yàn)橥負(fù)渑判蚴轻槍?duì)有向圖來(lái)定義的。為解決這個(gè)問(wèn)題，利用同樣的模板來(lái)定義成員函數(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ù)并可輸出錯(cuò)誤信息。如果找到拓?fù)湫蛄?，則Topological 函數(shù)返回t r u e；若輸入的有向圖無(wú)拓?fù)湫蛄袆t返回f a l s e。當(dāng)找到拓?fù)湫蛄袝r(shí)，將其返回到v 0 :n- 1 中。3. Network:Topological 的復(fù)雜性第一和第三個(gè)f o r循環(huán)的時(shí)間開(kāi)銷為(n )。若使用（耗費(fèi)）鄰接矩陣,則第二個(gè)for 循環(huán)所用的時(shí)間為(n2 )；若使用鄰接鏈表,則所用時(shí)間為(n+e)。在兩個(gè)嵌套的while 循環(huán)中，外層循環(huán)需執(zhí)行n次，每次將頂點(diǎn)w 加入到v 中，并初始化內(nèi)層while 循環(huán)。使用鄰接矩陣時(shí)，內(nèi)層w h i l e循環(huán)對(duì)于每個(gè)頂點(diǎn)w 需花費(fèi)(n)的時(shí)間；若利用鄰接鏈表，則這個(gè)循環(huán)需花費(fèi)dwout 的時(shí)間，因此，內(nèi)層while 循環(huán)的時(shí)間開(kāi)銷為(n2 )或(n+e)。所以，若利用鄰接矩陣，程序1 3 - 2的時(shí)間復(fù)雜性為(n2 )，若利用鄰接鏈表則為(n+e)。程序13-2 拓?fù)渑判騜ool Network:Topological(int v)/ 計(jì)算有向圖中頂點(diǎn)的拓?fù)浯涡? 如果找到了一個(gè)拓?fù)浯涡?，則返回t r u e，此時(shí)，在v 0 : n - 1 中記錄拓?fù)浯涡? 如果不存在拓?fù)浯涡颍瑒t返回f a l s eint n = Ve r t i c e s ( ) ;/ 計(jì)算入度int *InDegree = new int n+1;InitializePos(); / 圖遍歷器數(shù)組for (int i = 1; i = n; i+) / 初始化InDegreei = 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 S;for (i = 1; i 0) 設(shè)v是具有最大的N e w i 的頂點(diǎn)；C m + + = v ;for ( 所有鄰接于v的頂點(diǎn)j) if (!Covj) Covj= true;對(duì)于所有鄰接于j的頂點(diǎn)，使其N e w k 減1 if (有些頂點(diǎn)未被覆蓋) 失敗else 找到一個(gè)覆蓋圖1-8 圖1-7的細(xì)化更新N e w的時(shí)間為O (e)，其中e 為二分圖中邊的數(shù)目。若使用鄰接矩陣，則需花(n2 ) 的時(shí)間來(lái)尋找圖中的邊，若用鄰接鏈表，則需(n+e) 的時(shí)間。實(shí)際更新時(shí)間根據(jù)描述方法的不同為O (n2 ) 或O (n+e)。逐步選擇頂點(diǎn)所需時(shí)間為(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ù)雜性通過(guò)使用有序數(shù)組N e wi、最大堆或最大選擇樹（max selection tree）可將每步選取頂點(diǎn)v的復(fù)雜性降為( 1 )。但利用有序數(shù)組，在每步的最后需對(duì)N e wi 值進(jìn)行重新排序。若使用箱子排序，則這種排序所需時(shí)間為(S i z e O f B ) ( S i z e O fB =|B| ) （見(jiàn)3 . 8 . 1節(jié)箱子排序）。由于一般S i z e O f B比S i z e O f A大得多，因此有序數(shù)組并不總能提高性能。如果利用最大堆，則每一步都需要重建堆來(lái)記錄N e w值的變化，可以在每次N e w值減1時(shí)進(jìn)行重建。這種減法操作可引起被減的N e w值最多在堆中向下移一層，因此這種重建對(duì)于每次N e w值減1需( 1 )的時(shí)間，總共的減操作數(shù)目為O (e)。因此在算法的所有步驟中，維持最大堆僅需O (e)的時(shí)間，因而利用最大堆時(shí)覆蓋算法的總復(fù)雜性為O (n2 )或O (n+e)。若利用最大選擇樹，每次更新N e w值時(shí)需要重建選擇樹，所需時(shí)間為(log S i z e O f A)。重建的最好時(shí)機(jī)是在每步結(jié)束時(shí)，而不是在每次N e w值減1時(shí)，需要重建的次數(shù)為O (e)，因此總的重建時(shí)間為O (e log S i z e OfA)，這個(gè)時(shí)間比最大堆的重建時(shí)間長(zhǎng)一些。然而，通過(guò)維持具有相同N e w值的頂點(diǎn)箱子，也可獲得和利用最大堆時(shí)相同的時(shí)間限制。由于N e w的取值范圍為0到S i z e O f B，需要S i z e O f B+ 1個(gè)箱子，箱子i 是一個(gè)雙向鏈表，鏈接所有N e w值為i 的頂點(diǎn)。在某一步結(jié)束時(shí)，假如N e w 6 從1 2變到4，則需要將它從第1 2個(gè)箱子移到第4個(gè)箱子。利用模擬指針及一個(gè)節(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個(gè)箱子移到第4個(gè)箱子，從第1 2個(gè)箱子中刪除n o d e 0 并將其插入第4個(gè)箱子。利用這種箱子模式，可得覆蓋啟發(fā)式算法的復(fù)雜性為O (n2 )或O(n+e)。（取決于利用鄰接矩陣還是線性表來(lái)描述圖）。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是一個(gè)具有私有整型成員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個(gè)空箱子和n個(gè)節(jié)點(diǎn)void DestroyBins() delete node;delete bin;void InsertBins(int b, int v)在箱子b中添加頂點(diǎn)vvoid MoveBins(int bMax, int ToBin, int v)從當(dāng)前箱子中移動(dòng)頂點(diǎn)v到箱子To B i nint *bin;b i n i 指向代表該箱子的雙向鏈表的首節(jié)點(diǎn)N o d e Type *node;n o d e i 代表存儲(chǔ)頂點(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)/