中國數(shù)學(xué)建模-編程交流-貪婪算法new

1、中國數(shù)學(xué)建模-編程交流-貪婪算法.txt“我羨慕內(nèi)些老人羨慕他們手牽手一直走到最后。交話費(fèi)的時(shí)候，才發(fā)現(xiàn)自己的話那么值錢。中國數(shù)學(xué)建模-編程交流-貪婪算法 第 1 章 貪婪算法 雖然設(shè)計(jì)一個(gè)好的求解算法更像是一門藝術(shù)，而不像是技術(shù)，但仍然存在一些行之有效的能夠用于解決許多問題的算法設(shè)計(jì)方法，你可以使用這些方法來設(shè)計(jì)算法，并觀察這些算法是如何工作的。一般情況下，為了獲得較好的性能，必須對算法進(jìn)行細(xì)致的調(diào)整。但是在某些情況下，算法經(jīng)過調(diào)整之后性能仍無法達(dá)到要求，這時(shí)就必須尋求另外的方法來求解該問題。 本章首先引入最優(yōu)化的概念，然后介紹一種直觀的問題求解方法：貪婪算法。最后，應(yīng)用該算法給出貨箱裝船問

2、題、背包問題、拓?fù)渑判騿栴}、二分覆蓋問題、最短路徑問題、最小代價(jià)生成樹等問題的求解方案。 1.1 最優(yōu)化問題 本章及后續(xù)章節(jié)中的許多例子都是最優(yōu)化問題（ optimization problem），每個(gè)最優(yōu)化問題都包含一組限制條件（ c on s t r a i n t）和一個(gè)優(yōu)化函數(shù)（ optimizationfunction），符合限制條件的問題求解方案稱為可行解（ feasible solution），使優(yōu)化函數(shù)取得最佳值的可行解稱為最優(yōu)解（optimal solution）。 例1-1 渴嬰問題 有一個(gè)非?？实?、聰明的小嬰兒，她可能得到的東西包括一杯水、一桶牛奶、多罐不同種類的果汁、許

3、多不同的裝在瓶子或罐子中的蘇打水，即嬰兒可得到n種不同的飲料。根據(jù)以前關(guān)于這n種飲料的不同體驗(yàn)，此嬰兒知道這其中某些飲料更合自己的胃口，因此，嬰兒采取如下方法為每一種飲料賦予一個(gè)滿意度值：飲用1盎司第i 種飲料，對它作出相對評價(jià)，將一個(gè)數(shù)值si 作為滿意度賦予第i 種飲料。 通常，這個(gè)嬰兒都會盡量飲用具有最大滿意度值的飲料來最大限度地滿足她解渴的需要，但是不幸的是：具有最大滿意度值的飲料有時(shí)并沒有足夠的量來滿足此嬰兒解渴的需要。設(shè)ai是第i種飲料的總量（以盎司為單位），而此嬰兒需要t 盎司的飲料來解渴，那么，需要飲用n種不同的飲料各多少量才能滿足嬰兒解渴的需求呢？ 設(shè)各種飲料的滿意度已知。令x

4、i 為嬰兒將要飲用的第i 種飲料的量，則需要解決的問題是： 找到一組實(shí)數(shù)xi（1in），使n åi = 1si xi 最大，并滿足：n åi=1xi =t 及0xiai 。 需要指出的是：如果n åi = 1ai t，則不可能找到問題的求解方案，因?yàn)榧词购裙馑械娘嬃弦膊荒苁箣雰航饪省?對上述問題精確的數(shù)學(xué)描述明確地指出了程序必須完成的工作，根據(jù)這些數(shù)學(xué)公式，可以對輸入/ 輸出作如下形式的描述： 輸入：n，t，si ，ai（其中1in，n 為整數(shù)，t、si 、ai 為正實(shí)數(shù)）。 輸出：實(shí)數(shù)xi（1in），使n åi= 1si xi 最大且n &a

5、ring;i=1xi =t（0xiai）。如果n åi = 1ai t，則輸出適當(dāng)?shù)腻e誤信息。 在這個(gè)問題中，限制條件是n åi= 1xi =t 且0xiai，1in。而優(yōu)化函數(shù)是n åi= 1si xi。任何滿足限制條件的一組實(shí)數(shù)xi 都是可行解，而使n åi= 1si xi 最大的可行解是最優(yōu)解。 例1-2 裝載問題 有一艘大船準(zhǔn)備用來裝載貨物。所有待裝貨物都裝在貨箱中且所有貨箱的大小都一樣，但貨箱的重量都各不相同。設(shè)第i 個(gè)貨箱的重量為wi（1in），而貨船的最大載重量為c，我們的目的是在貨船上裝入最多的貨物。 這個(gè)問題可以作為最優(yōu)化問題進(jìn)

6、行描述：設(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è)無向圖，圖的每條邊都被賦予一個(gè)權(quán)值，權(quán)值表示建成由這條邊所表示的通信連接所要付出的代價(jià)。包含圖中所有頂點(diǎn)（城市）的

7、連通子圖都是一個(gè)可行解。設(shè)所有的權(quán)值都非負(fù)，則所有可能的可行解都可表示成無向圖的一組生成樹，而最優(yōu)解是其中具有最小代價(jià)的生成樹。 在這個(gè)問題中，需要選擇一個(gè)無向圖中的邊集合的子集，這個(gè)子集必須滿足如下限制條件：所有的邊構(gòu)成一個(gè)生成樹。而優(yōu)化函數(shù)是子集中所有邊的權(quán)值之和。 - plot(100+t+15*cos(3.05*t),t=0.200,coords=polar,axes=none,scaling=constrained); 1.2 算法思想 在貪婪算法（greedy method）中采用逐步構(gòu)造最優(yōu)解的方法。在每個(gè)階段，都作出一個(gè)看上去最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。決策一旦作出，就不可再

8、更改。作出貪婪決策的依據(jù)稱為貪婪準(zhǔn)則（greedy criterion）。 例1-4 找零錢 一個(gè)小孩買了價(jià)值少于1美元的糖，并將1美元的錢交給售貨員。售貨員希望用數(shù)目最少的硬幣找給小孩。假設(shè)提供了數(shù)目不限的面值為25美分10美分、5美分、及1美分的硬幣。售貨員分步驟組成要找的零錢數(shù)，每次加入一個(gè)硬幣。選擇硬幣時(shí)所采用的貪婪準(zhǔn)則如下：每一次選擇應(yīng)使零錢數(shù)盡量增大。為保證解法的可行性（即：所給的零錢等于要找的零錢數(shù)），所選擇的硬幣不應(yīng)使零錢總數(shù)超過最終所需的數(shù)目。 假設(shè)需要找給小孩6 7美分，首先入選的是兩枚2 5美分的硬幣，第三枚入選的不能是25美分的硬幣，否則硬幣的選擇將不可行（零錢總數(shù)超過

9、6 7美分），第三枚應(yīng)選擇10美分的硬幣，然后是5美分的，最后加入兩個(gè)1美分的硬幣。 貪婪算法有種直覺的傾向，在找零錢時(shí)，直覺告訴我們應(yīng)使找出的硬幣數(shù)目最少（至少是接近最少的數(shù)目）?？梢宰C明采用上述貪婪算法找零錢時(shí)所用的硬幣數(shù)目的確最少（見練習(xí)1）。 例1-5 機(jī)器調(diào)度 現(xiàn)有n 件任務(wù)和無限多臺的機(jī)器，任務(wù)可以在機(jī)器上得到處理。每件任務(wù)的開始時(shí)間為si，完成時(shí)間為fi ，si k。尋找 1 ,n范圍內(nèi)最小的整數(shù)j，使得xjyj 。若沒有這樣的j 存在，則n åi= 1xi =n åi = 1yi 。如果有這樣的j 存在，則jk，否則y 就不是一個(gè)可行解，因?yàn)閤jyj ，

10、xj = 1且yj = 0。令yj = 1，若結(jié)果得到的y 不是可行解，則在 j+ 1 ,n范圍內(nèi)必有一個(gè)l 使得yl = 1。令yl = 0，由于wjwl ，則得到的y 是可行的。而且，得到的新y 至少與原來的y 具有相同數(shù)目的1。 經(jīng)過數(shù)次這種轉(zhuǎn)化，可將y 轉(zhuǎn)化為x。由于每次轉(zhuǎn)化產(chǎn)生的新y 至少與前一個(gè)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é)間接尋址的定義

11、），隨后貨箱便可按重量遞增的順序裝載。由于間接尋址排序所需的時(shí)間為O (nl o gn)（也可利用9 . 5 . 1節(jié)的堆排序及第2章的歸并排序），算法其余部分所需時(shí)間為O (n)，因此程序1 3 - 1的總的復(fù)雜性為O (nl o gn)。 程序13-1 貨箱裝船 template void ContainerLoading(int x, T w, T c, int n) / 貨箱裝船問題的貪婪算法 / xi = 1 當(dāng)且僅當(dāng)貨箱i被裝載， 1=i=n / c是船的容量, w 是貨箱的重量 / 對重量按間接尋址方式排序 / t 是間接尋址表 int *t = new int n+1; I n

12、 d i r e c t S o r t ( w, t, n); / 此時(shí), wti = wti+1, 1=in / 初始化x for (int i = 1; i = n; i+) xi = 0; / 按重量次序選擇物品 for (i = 1; i = n & wti = c; i+) xti = 1; c -= wti; / 剩余容量 delete t; - plot(100+t+15*cos(3.05*t),t=0.200,coords=polar,axes=none,scaling=constrained); 2004-5-27 19:39:39 b 等級：職業(yè)俠客 文章：472 積分：

13、951 門派：黑客帝國 注冊：2003-8-28 第 5 樓 1.3.2 0/1背包問題 在0 / 1背包問題中，需對容量為c 的背包進(jìn)行裝載。從n 個(gè)物品中選取裝入背包的物品，每件物品i 的重量為wi ，價(jià)值為pi 。對于可行的背包裝載，背包中物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價(jià)值最高，即n åi=1pi xi 取得最大值。約束條件為n åi =1wi xic 和xiÎ 0 , 1 ( 1in)。 在這個(gè)表達(dá)式中，需求出xt 的值。xi = 1表示物品i 裝入背包中，xi =0 表示物品i 不裝入背包。0 / 1背包問題是一個(gè)一般化的

14、貨箱裝載問題，即每個(gè)貨箱所獲得的價(jià)值不同。貨箱裝載問題轉(zhuǎn)化為背包問題的形式為：船作為背包，貨箱作為可裝入背包的物品。 例1-8 在雜貨店比賽中你獲得了第一名，獎品是一車免費(fèi)雜貨。店中有n 種不同的貨物。規(guī)則規(guī)定從每種貨物中最多只能拿一件，車子的容量為c，物品i 需占用wi 的空間，價(jià)值為pi 。你的目標(biāo)是使車中裝載的物品價(jià)值最大。當(dāng)然，所裝貨物不能超過車的容量，且同一種物品不得拿走多件。這個(gè)問題可仿照0 / 1背包問題進(jìn)行建模，其中車對應(yīng)于背包，貨物對應(yīng)于物品。 0 / 1背包問題有好幾種貪婪策略，每個(gè)貪婪策略都采用多步過程來完成背包的裝入。在每一步過程中利用貪婪準(zhǔn)則選擇一個(gè)物品裝入背包。一種

15、貪婪準(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ī)則對于前面的例子能產(chǎn)生最優(yōu)解，但在一般情況下則不一定能得到最優(yōu)解?？紤]n= 2 ,w=10,2

16、0, 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背包問題是一個(gè)N P-復(fù)雜問題。對于這類問題，也許根本就不可能找到具有多項(xiàng)式時(shí)間的算法。雖然按pi /wi 非遞（增）減的次序裝入物品不能保證得到最優(yōu)解，但它是一

17、個(gè)直覺上近似的解。我們希望它是一個(gè)好的啟發(fā)式算法，且大多數(shù)時(shí)候能很好地接近最后算法。在6 0 0個(gè)隨機(jī)產(chǎn)生的背包問題中，用這種啟發(fā)式貪婪算法來解有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)獲得如此好的性能。我們也許會問，是否存在一個(gè)x (x1 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。對于y1 0 / 9，最優(yōu)解的值

18、為9 y。因此，貪婪算法的值與最優(yōu)解的差對最優(yōu)解的比例為( ( 9y - 1 0)/9y* 1 0 0 ) %，對于大的y，這個(gè)值趨近于1 0 0 %。但是可以建立貪婪啟發(fā)式方法來提供解，使解的結(jié)果與最優(yōu)解的值之差在最優(yōu)值的x% (x100) 之內(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時(shí)，背包按物品價(jià)值密度非遞減順序裝入，

19、首先將物品1放入背包，然后是物品2，背包剩下的容量為5個(gè)單元，剩下的物品沒有一個(gè)合適的，因此解為x = 1 , 1 , 0 , 0 。此解獲得的價(jià)值為1 6。 現(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à)值密度非遞增順序來考慮如何利用這5個(gè)單位的容量。首先考慮物品1，它適合，因此取x1 為1，這時(shí)僅剩下3個(gè)單位容量了，且剩余物品沒有能夠加入背包中的物品。通過子集 3 開始求解得結(jié)果為x = 1 , 0 , 1 , 0 ，獲得的價(jià)值為1 8。若從子集 4 開始

20、，產(chǎn)生的解為x = 1 , 0 , 0 , 1 ，獲得的價(jià)值為1 9?？紤]子集大小為0和1時(shí)獲得的最優(yōu)解為 1 , 0 , 0 , 1 。這個(gè)解是通過k= 1的貪婪啟發(fā)式算法得到的。 若k= 2，除了考慮k0時(shí)總的時(shí)間開銷為O (nk+1 )。實(shí)際觀察到的性能要好得多。 - plot(100+t+15*cos(3.05*t),t=0.200,coords=polar,axes=none,scaling=constrained); 2004-5-27 19:39:53 b 等級：職業(yè)俠客 文章：472 積分：951 門派：黑客帝國 注冊：2003-8-28 第 6 樓 1.3.3 拓?fù)渑判?一個(gè)

21、復(fù)雜的工程通?？梢苑纸獬梢唤M小任務(wù)的集合，完成這些小任務(wù)意味著整個(gè)工程的完成。例如，汽車裝配工程可分解為以下任務(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顯示了六個(gè)任務(wù)的工程，邊（ 1 , 4）表示任務(wù)1在任務(wù)4開始前完成，同樣邊（ 4 , 6）表示任務(wù)4在任務(wù)6開始前完成，邊（1 , 4）與（4 , 6）合起來可

22、知任務(wù)1在任務(wù)6開始前完成，即前后關(guān)系是傳遞的。由此可知，邊（1 , 4）是多余的，因?yàn)檫叄? , 3）和（3 , 4）已暗示了這種關(guān)系。 在很多條件下，任務(wù)的執(zhí)行是連續(xù)進(jìn)行的，例如汽車裝配問題或平時(shí)購買的標(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

23、的任務(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）及其他邊所指示的序列相矛盾?？捎秘澙匪惴▉斫⑼?fù)湫蛄小Ｋ惴ò磸淖蟮接业牟襟E構(gòu)造拓?fù)湫蛄?，每一步在排好的序列中加入一個(gè)頂點(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違背了這個(gè)準(zhǔn)則（即有向圖中存在邊（ v,w）且v 不在已構(gòu)造的序列

24、中），則無法完成拓?fù)渑判?，因?yàn)轫旤c(diǎn)v 必須跟隨在頂點(diǎn)w 之后。貪婪算法的偽代碼如圖1 3 - 5所示。while 循環(huán)的每次迭代代表貪婪算法的一個(gè)步驟。 現(xiàn)在用貪婪算法來求解圖1 - 4的有向圖。首先從一個(gè)空序列V開始，第一步選擇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

25、 4 6。 1. 貪婪算法的正確性 為保證貪婪算法算的正確性，需要證明： 1) 當(dāng)算法失敗時(shí)，有向圖沒有拓?fù)湫蛄校?2) 若 算法沒有失敗，V即是拓?fù)湫蛄小?) 即是用貪婪準(zhǔn)則來選取下一個(gè)頂點(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)失敗時(shí)| V |n, 且沒有候選頂點(diǎn)能加入V中，因此至少有一個(gè)頂點(diǎn)q1 不在V中，有向圖中必包含邊（ q2 , q1）且q2 不

26、在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 + +代碼來實(shí)現(xiàn)，必須考慮序列V的描述方法，以及如何找出可加入V的候選頂點(diǎn)。一種高效的實(shí)現(xiàn)方法是將序列V用一維數(shù)組v 來描述的，用一個(gè)棧來保存可加

27、入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。對于有向圖1 - 4，開始時(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

28、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ù)。而且，它對于有無加權(quán)的有向圖均適用。但若用于無向圖（不論其有無加權(quán)）將會得到錯誤的結(jié)果，

29、因?yàn)橥負(fù)渑判蚴轻槍τ邢驁D來定義的。為解決這個(gè)問題，利用同樣的模板來定義成員函數(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(shí)，將其返回到v 0 :n- 1 中。 3. Network:Topological 的復(fù)雜性 第一和第三個(gè)f o r循環(huán)的時(shí)間開銷為(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)對于每個(gè)頂點(diǎn)w 需花費(fèi)(n)的時(shí)間；若利用鄰接鏈表，則這個(gè)循環(huán)需花費(fèi)dwout 的時(shí)間，因此，內(nèi)層while 循環(huán)的時(shí)間開銷為(n2 )或(n+e)。所以，若利用鄰接矩陣，程序1 3 - 2的時(shí)間復(fù)雜性為(n2 )，若利用鄰接鏈表則為(n+e)。 程序13-2 拓?fù)渑判?boo