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首先計(jì)算出集合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 加入到覆蓋中，這種策略即為選擇具有最大New 值的頂點(diǎn)。將所選擇的頂點(diǎn)加入覆蓋數(shù)組C并檢查B中所有與它鄰接的頂點(diǎn)。若頂點(diǎn)j 與v 鄰接且還未被覆蓋，則將C o v [ j ]置為t r u e，表示頂點(diǎn)j 現(xiàn)在已被覆蓋，同時將已被覆蓋的B中的頂點(diǎn)數(shù)目加1。由于j 是最近被覆蓋的，所有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

}