圖的最短路徑、拓撲排序和關(guān)鍵路徑

1、數(shù)據(jù)結(jié)構(gòu)課程輔導-圖的最短路徑、拓撲排序和關(guān)鍵路徑一、最 短 路 徑由圖的概念可知，在一個圖中，若從一頂點到另一頂點存在著一條路徑(這里只討論無回路的簡單路徑)，則稱該路徑長度為該路徑上所經(jīng)過的邊的數(shù)目，它也等于該路徑上的頂點數(shù)減1。由于從一頂點到另一頂點可能存在著多條路徑，每條路徑上所經(jīng)過的邊數(shù)可能不同，即路徑長度不同，我們把路徑長度最短（即經(jīng)過的邊數(shù)最少）的那條路徑叫做最短路徑，其路徑長度叫做最短路徑長度或最短距離。 上面所述的圖的最短路徑問題只是對無權(quán)圖而言的，若圖是帶權(quán)圖，則把從一個頂點i到圖中其余任一個頂點j的一條路徑上所經(jīng)過邊的權(quán)值之和定義為該路徑的帶權(quán)路徑長度，從vi到vj可能不

2、止一條路徑，我們把帶權(quán)路徑長度最短（即其值最?。┑哪菞l路徑也稱作最短路徑，其權(quán)值也稱作最短路徑長度或最短距離。 例如，在圖3-1中，從v0到v4共有三條路徑：0,4,0,1,3,4和0,1,2,4，其帶權(quán)路徑長度分別為30,23和38，可知最短路徑為0,1,3,4，最短距離為23。圖3-1 帶權(quán)圖和對應的鄰接矩陣 實際上，這兩類最短路徑問題可合并為一類，這只要把無權(quán)圖上的每條邊標上數(shù)值為1的權(quán)就歸屬于有權(quán)圖了，所以在以后的討論中，若不特別指明，均認為是求帶權(quán)圖的最短路徑問題。 求圖的最短路徑問題用途很廣。例如，若用一個圖表示城市之間的運輸網(wǎng)，圖的頂點代表城市，圖上的邊表示兩端點對應城市之間存在

3、著運輸線，邊上的權(quán)表示該運輸線上的運輸時間或單位重量的運費，考慮到兩城市間的海拔高度不同，流水方向不同等因素，將造成來回運輸時間或運費的不同，所以這種圖通常是一個有向圖。如何能夠使從一城市到另一城市的運輸時間最短或者運費最省呢？這就是一個求兩城市間的最短路徑問題。 求圖的最短路徑問題包括兩個方面：一是求圖中一頂點到其余各頂點的最短路徑，二是求圖中每對頂點之間的最短路徑。下面分別進行討論。 1. 從一頂點到其余各頂點的最短路徑 對于一個具有n個頂點和e條邊的圖G，從某一頂點vi(稱此為源點)到其余任一頂點vj(稱此為終點)的最短路徑，可能是它們之間的邊(i,j)或，也可能是經(jīng)過k個（1kn-2，

4、最多經(jīng)過除源點和終點之外的所有頂點）中間頂點和k+1條邊所形成的路徑。例如在圖3-1中，從v0到v1的最短路徑就是它們之間的有向邊，其長度為3；從v0到v4的最短路徑經(jīng)過兩個中間點v1和v3以及三條有向邊,和，其長度為23。 那么，如何求出從源點i到圖中其余每一個頂點的最短路徑呢？狄克斯特拉(Dijkstra)于1959年提出了解決此問題的一般算法，具體做法是按照從源點到其余每一頂點的最短路徑長度的升序依次求出從源點到各頂點的最短路徑及長度，每次求出從源點i到一個終點m的最短路徑及長度后，都要以該頂點m作為新考慮的中間點，用vi到vm的最短路徑和最短路徑長度對vi到其它尚未求出最短路徑的那些終

5、點的當前最短路徑及長度作必要地修改，使之成為當前新的最短路徑和最短路徑長度，當進行n-2次（因最多考慮n-2個中間點）后算法結(jié)束。 狄克斯特拉算法需要設置一個集合，假定用S表示，其作用是保存已求得最短路徑的終點序號，它的初值中只有一個元素，即源點i，以后每求出一個從源點i到終點m的最短路徑，就將該頂點m并入S集合中，以便作為新考慮的中間點；還需要設置一個整型（假定權(quán)值類型為整型）數(shù)組distMaxVertexNum，該數(shù)組中的第j個元素distj用來保存從源點i到終點j的目前最短路徑長度，它的初值為(i,j)或邊上的權(quán)值，若vi到vj沒有邊，則權(quán)值為MaxValue，以后每考慮一個新的中間點時

6、，distj的值可能變??； 另外，再設置一個與dist數(shù)組相對應的、類型為adjlist的鄰接表表頭向量數(shù)組path，該數(shù)組中的第j個元素pathj指向一個單鏈表，該單鏈表中保存著從源點i到終點j的目前最短路徑，即一個頂點序列，當vi到vj存在著一條邊時，則pathj初始指向由頂點i和j構(gòu)成的單鏈表，否則pathj的初值為空。 此算法的執(zhí)行過程是：首先從S集合以外的頂點（即待求出最短路徑的終點）所對應的dist數(shù)組元素中，查找出其值最小的元素，假定為distm，該元素值就是從源點i到終點m的最短路徑長度(證明從略)，對應path數(shù)組中的元素pathm所指向的單鏈表鏈接著從源點i到終點m的最短路

7、徑，即經(jīng)過的頂點序列或稱邊序列；接著把已求得最短路徑的終點m并入集合S中；然后以vm作為新考慮的中間點，對S集合以外的每個頂點j，比較distm+GAmj（GA為圖G的鄰接矩陣）與distj的大小，若前者小于后者，表明加入了新的中間點vm之后，從vi到vj的路徑長度比原來變短，應用它替換distj的原值，使distj始終保持到目前為止最短的路徑長度，同時把pathm單鏈表復制到pathj上，并在其后插入vj結(jié)點，使之構(gòu)成從源點i到終點j的目前最短路徑。重復n-2次上述運算過程，即可在dist數(shù)組中得到從源點i到其余每個頂點的最短路徑長度，在path數(shù)組中得到相應的最短路徑。 為了簡便起見，可采

8、用一維數(shù)組sn來保存已求得最短路徑的終點的集合S，具體做法是：若頂點j在集合S中，則令數(shù)組元素sj的值取1，否則取0。這樣，當判斷一個頂點j是否在集合S以外時，只要判斷對應的數(shù)組元素sj是否為0即可。 例如，對于圖3-1來說，若求從源點v0到其余各頂點的最短路徑，則開始時三個一維數(shù)組s,dist和path的值為： 1 0 0 0 0 0 3 30 v0,v1v0,v4 0 1 2 3 4 s dist path 下面開始進行第一次運算，求出從源點v0到第一個終點的最短路徑。首先從s元素為0的對應dist元素中，查找出值最小的元素，求得dist2的值最小，所以第一個終點為v1, 最短距離為dis

9、t2=3，最短路徑為path2=0,1，接著把s1置為1，表示v1已加入S集合中，然后以v1為新考慮的中間點，對s數(shù)組中元素為0的每個頂點j（此時2j4）的目前最短路徑長度distj和目前最短路徑pathj進行必要地修改，因dist1+GA12=3+25=28，小于dist2=，所以將28賦給dist2，將path1并上v2后賦給path2，同理因dist1+GA13=3+8=11，小于dist3=，所以將11賦給dist3，將path1并上v3后賦給path3，最后再看從v0到v4，以v1作為新考慮的中間點的情況，由于v1到v4沒有出邊，所以GA14=，故dist1+GA14不小于dist4

10、，因此dist4和path4無需修改，應維持原值。至此，第一次運算結(jié)束，三個一維數(shù)組的當前狀態(tài)為： 0 1 2 3 4 1 1 0 0 0 0 3 28 11 30 v0,v1v0,v1,v2v0,v1,v3v0,v4 s dist path 下面開始進行第二次運算，求出從源點v0到第二個終點的最短路徑。首先從s數(shù)組中元素為0的對應dist元素中，查找出值最小的元素，求得dist3的值最小，所以第二個終點為v3, 最短距離為dist3=11，最短路徑為path3=0,1,3，接著把s3置為1，然后以v3作為新考慮的中間點，對s中元素為0的每個頂點j（此時j=3,5）的distj和pathj進行

11、必要的修改，因dist3+GA32=11+4=15，小于dist2=28，所以將15賦給dist2，將path3并上v2后賦給path2，同理，因dist3+GA34=11+12=23，小于dist4=30，所以將23賦給dist4，將path3并上v4后賦給path4。至此，第二次運算結(jié)束，三個一維數(shù)組的當前狀態(tài)為： 0 1 2 3 41 1 0 1 00 3 15 11 23v0,v1v0,v1,v3,v2v0,v1,v3v0,v1,v3,v4 s dist path 下面開始進行第三次運算，求出從源點v0到第三個終點的最短路徑。首先從s中元素為0的對應dist元素中，查找出值最小的元素為

12、dist2，所以求得第三個終點為v2，最短距離為dist2=15，最短路徑為path2=0,1,3,2，接著把s2置為1，然后以v2作為新考慮的中間點，對s中元素為0的每個頂點j（此時只有v4一個）的distj和pathj進行必要的修改，因dist2+GA24=15+10=25，大于dist4=23，所以無需修改，原值不變。至此，第三次運算結(jié)束，三個一維數(shù)組的當前狀態(tài)為：1 1 1 1 00 3 15 11 23 v0,v1v0,v1,v3,v2v0,v1,v3v0,v1,v3,v4 0 1 2 3 4 s dist path 由于圖中有5個頂點，只需運算3次，即n-2次，雖然此時還有一個頂點

13、未加入S集合中，但它的最短路徑及最短距離已經(jīng)最后確定，所以整個運算結(jié)束。最后在dist中得到從源v0到每個頂點的最短路徑長度，在path中得到相應的最短路徑。 如果用圖形表示上述過程中每次運算的結(jié)果，則對應的圖形分別如圖3-2(b)(e)所示，其中實線有向邊所指向的頂點為集合S中的頂點，虛線有向邊所指向的頂點為集合S外的頂點；S集合中的頂點上所標數(shù)值為從源點v0到該頂點的最短路徑長度，從源點v0到該頂點所經(jīng)過的有向邊為從v0到該頂點的最短路徑；S集合外的頂點上所標數(shù)值為從源點v0到該頂點的目前最短路徑長度，從v0到該頂點所經(jīng)過的有向邊為從v0到該頂點的目前最短路徑。為了便于對照分析，把圖3-1

14、(a)重畫于圖3-2(a)中。圖3-2 利用狄克斯特拉算法求最短路徑的圖形說明 根據(jù)以上分析和舉例，不難給出狄克斯特拉算法的描述： void Dijkstra(adjmatrix GA, int dist, adjlist path, int i, int n) /利用狄克斯特拉算法求圖GA中從頂點i到其余每個頂點間的/最短距離和最短路徑，它們分別被存于數(shù)組dist和path數(shù)組中 int j,k,w,m; /定義作為集合使用的動態(tài)數(shù)組s int* s=new intn; /分別給s,dist和path數(shù)組賦初值 for(j=0; jn; j+) if(j=i) sj=1; else sj=0

15、; distj=GAij; if(distjadjvex=i; p2-adjvex=j; p2-next=NULL; p1-next=p2; pathj=p1; else pathj=NULL; /共進行n-2次循環(huán)，每次求出從源點i到終點m的最短路徑及長度 for(k=1; k=n-2; k+) /求出第k個終點m w=MaxValue; m=i; for(j=0; jn; j+) if(sj=0 & distjw) w=distj; m=j; /若條件成立,則把頂點m并入集合S中,否則退出循環(huán),因為剩余 /的頂點,其最短路徑長度均為MaxValue,無需再計算下去 if(m!=i) sm=

16、1; else break; /對s元素為0的對應dist和path中的元素作必要修改 for(j=0; jn; j+) if(sj=0 & distm+GAmjnext; delete p; p=pathj; /把到頂點m的最短路徑拷貝過來到頂點j的最短路徑上 p=pathm; while(p!=NULL) q=new edgenode; q-adjvex=p-adjvex; if(pathj=NULL) pathj=q; else s-next=q; s=q; p=p-next; /把頂點j加入到pathj單鏈表的最后，形成新的目前最短路徑 q=new edgenode; q-adjvex

17、=j; q-next=NULL; s-next=q; 2. 每對頂點之間的最短路徑 求圖中每對頂點之間的最短路徑是指把圖中任意兩個頂點vi和vj(ij)之間的最短路徑都計算出來。若圖中有n個頂點，則共需要計算n(n-1)條最短路徑。解決此問題有兩種方法：一是分別以圖中的每個頂點為源點共調(diào)用n次狄克斯特拉算法，因狄克斯特拉算法的時間復雜性為O(n2)，所以此方法的時間復雜性為O(n3)；二是采用下面介紹的弗洛伊德(Floyed)算法，此算法的時間復雜性仍為O(n3)，但比較簡單。 弗洛伊德算法從圖的鄰接矩陣開始，按照頂點v0,v1,vn-1的次序，分別以每個頂點vk(0kn-1)作為新考慮的中間

18、點，在第k-1次運算得到的A(k-1)（A(-1)為圖的鄰接矩陣GA）的基礎上，求出每對頂點vi到vj的目前最短路徑長度A(k)ij，計算公式為： A(k)ij=min(A(k-1)ij, A(k-1)ik+A(k-1)kj) (0in-1,0jn-1) 其中min函數(shù)表示取其參數(shù)表中的較小值，參數(shù)表中的前項表示在第k-1次運算后得到的從vi到vj的目前最短路徑長度，后項表示考慮以vk作為新的中間點所得到的從vi到vj的路徑長度。若后項小于前項，則表明以vk作為中間點（不排除已經(jīng)以v0,v1,vk-1中的一部分或全部作為其中間點）使得從vi到vj的路徑長度變短，所以應把它的值賦給A(k)ij，

19、否則把A(k-1)ij的值賦給A(k)ij?？傊笰(k)ij保存第k次運算后得到的從vi到vj的目前最短路徑長度。當k從0取到n-1后，矩陣A(n-1)就是最后得到的結(jié)果，其中每個元素A(n-1)ij就是從頂點vi到vj的最短路徑長度。 對于上面的計算公式，當i=j時變?yōu)椋?A(k)ii=min(A(k-1)ii, A(k-1)ik+A(k-1)ki) (0in-1) 若k=0，則參數(shù)表中的前項A(-1)ii=GAii=0，后項A(-1)i0+A(-1)0i必定大于等于0，所以A(0)中的對角線元素同A(-1)中的對角線元素一樣，均為0。同理，當k=1,2,n-1時，A（k）中的對角線元素

20、也均為0。 對于上面的計算公式，當i=k或j=k時分別變?yōu)椋?A(k)kj=min(A(k-1)kj, A(k-1)kk+A(k-1)kj) (0jn-1) A(k)ik=min(A(k-1)ik, A(k-1)ik+A(k-1)kk) (0in-1) 每個參數(shù)表中的后一項都由它的前一項加上A(k-1)kk所組成，因A(k-1)kk=0，所以A(k)kj和A(k)ik分別取上一次的運算結(jié)果A(k-1)kj和A(k-1)ik的值，也就是說，矩陣A(k)中的第k行和第k列上的元素均取上一次運算的結(jié)果。 下面以求圖3-3(a)中每對頂點之間的最短路徑長度為例來說明弗洛伊德算法的運算過程。圖3-3 弗

21、洛伊德算法求最短路徑的運算過程。 (1) 令k取0，即以v0作為新考慮的中間點，對圖3-3(b)所示A(-1)中的每對頂點之間的路徑長度進行必要的修改后得到第0次運算結(jié)果A(0)，如圖3-3(c)所示。在A（0）中，第0行和第0列用虛線框起來表示i=k和j=k的情況，它們同對角線上的元素一樣為A（-1）中的對應值，對于其它六個元素，若vi通過新中間點v0然后到vj的路徑長度A(-1)i0+A(-1)0j小于原來的路徑長度A(-1)ij，則用前者修改之，否則仍保持原值。因v2到v1的路徑長度A(-1)21=5，通過新中間點v0后變短，即為A(-1)20+A(-1)01=3+1=4，所以被修改為4

22、，對應的路徑為2,0,1；同樣，v2到v3的路徑長度通過新中間點v0后也由8變?yōu)?，所以被修改為7，對應的路徑為2,0,3；剩余的四對頂點的路徑長度，因加入v0作為新中間點后仍不變短，所以保持原值不變。 (2) 令k=1，即以v1作為新考慮的中間點，對A(0)中每對頂點之間的路徑長度進行必要的修改后得到第1次運算結(jié)果A(1)，如圖3-3(d)所示。此時第1行和第1列同對角線的元素一樣，取上一次的值，對于其它六個元素，若vi通過新中間點v1然后到vj的路徑長度A(0)i1+A(0)1j小于原來的路徑長度A(0)ij，則用前者修改之，否則仍保持原值。因v0到v2的路徑長度A（0）02=，通過新中間

23、點v1后變短，即為A（0）01+A（0）12=1+9=10，所以被修改為10，對應的路徑為0,1,2；v0到v3的路徑長度A(0)03=4，通過新中間點v1后變短，即為A（0）01+A（0）13=1+2=3，所以也被修改為3，對應的路徑為0,1,3；v2到v3的路徑長度A(0)23=7，通過新中間點v1后也變短，即為A（0）21+A（0）13=4+2=6，所以在第一次被修改的基礎上又重新被修改為6，對應的路徑為A（0）21的路徑2,0,1并上A（0）13的路徑1,3，即為2,0,1,3；剩余三對頂點的路徑長度，因加入新中間點v1后不變短，所以仍保持原值不變。 (3) 令k=2，即以v2作為新考

24、慮的中間點，對A（1）中每對頂點的路徑長度進行必要地修改，得到第2次運算的結(jié)果，如圖3-3(e)所示。同上兩次的分析過程一樣，請讀者分析這一次結(jié)果。 (4) 令k=3，即以v3作為新考慮的中間點，這也是最后一個要考慮的中間點，在A（2）的基礎上進行運算，得到的運算結(jié)果A（3）如圖3-3(f)所示，也請讀者同學們自行分析。A(3)就是最后得到的整個運算的結(jié)果，A（3）中的每個元素A（3）ij的值就是圖3-3(a)中頂點vi到vj的最短路徑長度。當然相應的最短路徑也可以通過另設一個矩陣記錄下來。 通過以上分析可知，在每次運算中，對i=k或j=k或i=j的那些元素無需進行計算，因為它們不會被修改，對

25、于其余元素，只有滿足A(k-1)ik+A(k-1)kjA(k-1)ij的元素才會被修改，即把小于號左邊的兩個元素之和賦給A(k)ij，在這兩個元素中，一個是列號等于k，一個是行號等于k，所以它們在進行第k次運算的整個過程中，其值都不會改變，故每一次運算都可以在原數(shù)組上“就地”進行，即用新修改的值替換原值即可，不需要使用兩個數(shù)組交替進行。 設具有n個頂點的一個帶權(quán)圖G的鄰接矩陣用GA表示，與GA同類型的，求每對頂點之間最短路徑長度的二維數(shù)組用A表示，A的初值等于GA。弗洛伊德算法需要在A上進行n次運算，每次以vk(0kn-1)作為一個新考慮的中間點，求出每對頂點之間的當前最短路徑長度，最后一次運

26、算后，A中的每個元素Aij就是圖G中從頂點vi到頂點vj的最短路徑長度。利用C+語言編寫出弗洛伊德算法如下，假定在該算法中不需要記錄每對頂點之間的最短路徑，只需要記錄每對頂點之間的最短距離。 void Floyed(adjmatrix GA, adjmatrix A, int n) /利用弗洛伊德算法求GA表示的圖中每對頂點之間的最短長度，/對應保存于二維數(shù)組A中 int i,j,k; /給二維數(shù)組A賦初值，它等于圖的鄰接矩陣GA for(i=0; in; i+) for(j=0; jn; j+) Aij=GAij; /依次以每個頂點作為中間點，逐步優(yōu)化數(shù)組A for(k=0; kn; k+)

27、 for(i=0; in; i+) for(j=0; jn; j+) if(i=k | j=k | i=j) continue; if(Aik+AkjAij) Aij=Aik+Akj; 二、拓 撲 排 序 一個較大的工程往往被劃分成許多子工程，我們把這些子工程稱作活動(activity)。在整個工程中，有些子工程(活動)必須在其它有關(guān)子工程完成之后才能開始，也就是說，一個子工程的開始是以它的所有前序子工程的結(jié)束為先決條件的，但有些子工程沒有先決條件，可以安排在任何時間開始。為了形象地反映出整個工程中各個子工程(活動)之間的先后關(guān)系，可用一個有向圖來表示，圖中的頂點代表活動(子工程)，圖中的有向

28、邊代表活動的先后關(guān)系，即有向邊的起點的活動是終點活動的前序活動，只有當起點活動完成之后，其終點活動才能進行。通常，我們把這種頂點表示活動、邊表示活動間先后關(guān)系的有向圖稱做頂點活動網(wǎng)(Activity On Vertex network)，簡稱AOV網(wǎng)。 課程代號 課程名稱 先修課程 C1 高等數(shù)學 無 C2 程序設計基礎 無 C3 離散數(shù)學 C1,C2 C4 數(shù)據(jù)結(jié)構(gòu) C3,C5 C5 算法語言 C2 C6 編譯技術(shù) C4,C5 C7 操作系統(tǒng) C4,C9 C8 普通物理 C1 C9 計算機原理 C8圖3-4 課程表例如，假定一個計算機專業(yè)的學生必須完成圖3-4所列出的全部課程。在這里，課程代

29、表活動，學習一門課程就表示進行一項活動，學習每門課程的先決條件是學完它的全部先修課程。如學習數(shù)據(jù)結(jié)構(gòu)課程就必須安排在學完它的兩門先修課程離散數(shù)學和算法語言之后。學習高等數(shù)學課程則可以隨時安排，因為它是基礎課程，沒有先修課。若用AOV網(wǎng)來表示這種課程安排的先后關(guān)系，則如圖3-5所示。圖中的每個頂點代表一門課程，每條有向邊代表起點對應的課程是終點對應課程的先修課。圖中的每個頂點代表一從圖中可以清楚地看出各課程之間的先修和后續(xù)的關(guān)系。如課程C5的先修課為C2，后續(xù)課程為C4和C6。 圖3-5 AOV網(wǎng) 圖3-6 三個頂點的回路 一個AOV網(wǎng)應該是一個有向無環(huán)圖，即不應該帶有回路，因為若帶有回路，則回

30、路上的所有活動都無法進行。如圖3-6是一個具有三個頂點的回路，由邊可得B活動必須在A活動之后，由邊可得C活動必須在B活動之后，所以推出C活動必然在A活動之后，但由邊可得C活動必須在A活動之前，從而出現(xiàn)矛盾，使每一項活動都無法進行。這種情況若在程序中出現(xiàn)，則稱為死鎖或死循環(huán)，是應該必須避免的。 在AOV網(wǎng)中，若不存在回路，則所有活動可排列成一個線性序列，使得每個活動的所有前驅(qū)活動都排在該活動的前面，我們把此序列叫做拓撲序列(Topological order)，由AOV網(wǎng)構(gòu)造拓撲序列的過程叫做拓撲排序(Topological sort)。AOV網(wǎng)的拓撲序列不是唯一的，滿足上述定義的任一線性序列都

31、稱作它的拓撲序列。例如，下面的三個序列都是圖3-5的拓撲序列，當然還可以寫出許多。 (1) C1,C8,C9,C2,C3,C5,C4,C7,C6 (2) C2,C1,C3,C5,C4,C6,C8,C9,C7 (3) C1,C2,C3,C8,C9,C5,C4,C6,C7 由AOV網(wǎng)構(gòu)造出拓撲序列的實際意義是：如果按照拓撲序列中的頂點次序，在開始每一項活動時，能夠保證它的所有前驅(qū)活動都已完成，從而使整個工程順序進行，不會出現(xiàn)沖突的情況。 由AOV網(wǎng)構(gòu)造拓撲序列的拓撲排序算法主要是循環(huán)執(zhí)行以下兩步，直到不存在入度為0的頂點為止。 (1) 選擇一個入度為0的頂點并輸出之； (2) 從網(wǎng)中刪除此頂點及所

32、有出邊。 循環(huán)結(jié)束后，若輸出的頂點數(shù)小于網(wǎng)中的頂點數(shù)，則輸出“有回路”信息，否則輸出的頂點序列就是一種拓撲序列。 下面以圖3-7(a)為例，來說明拓撲排序算法的執(zhí)行過程。圖3-7 拓撲排序的圖形說明 (1) 在(a)圖中v0和v1的入度都為0，不妨選擇v0并輸出之，接著刪去頂點v0及出邊，得到的結(jié)果如(b)圖所示。 (2) 在(b)圖中只有一個入度為0的頂點v1，輸出v1，接著刪去v1和它的三條出邊,和，得到的結(jié)果如(c)圖所示。 (3) 在(c)圖中v2和v4的入度都為0，不妨選擇v2并輸出之，接著刪去v2及兩條出邊和，得到的結(jié)果如(d)圖所示。 (4) 在(d)圖上依次輸出頂點v3,v4和

33、v5，并在每個頂點輸出后刪除該頂點及出邊，操作都很簡單，不再贅述。為了利用C+語言在計算機上實現(xiàn)拓撲排序算法，AOV網(wǎng)采用鄰接表表示較方便。如對于圖3-8(a)，對應的鄰接表如圖3-8所示。圖3-8 圖3-7(a)的鏈接表（其中值的含義：GLi的值是i節(jié)點的直接后續(xù)節(jié)點形成的鏈表）在拓撲排序算法中，需要設置一個包含n個元素的一維整型數(shù)組，假定用d表示，用它來保存AOV網(wǎng)中每個頂點的入度值。如對于圖3-8(a)，得到數(shù)組d的初始值為 0 1 2 3 4 5 0 0 2 2 1 3 在進行拓撲排序中，為了把所有入度為0的頂點都保存起來，而且又便于插入、刪除以及節(jié)省存儲，最好的方法是把它們鏈接成一個

34、棧。另外，當一個頂點vi的入度為0時，數(shù)組d中下標為i的元素di的值為0，正好可利用該元素作為鏈棧中的一個結(jié)點使用，保存下一個入度為0的頂點的序號，這樣就可以把所有入度為0的頂點通過數(shù)組d中的對應元素靜態(tài)鏈接成一個棧。在這個鏈棧中，棧頂指針top指向第一個入度為0的頂點所對應的數(shù)組d中的元素，該元素的值則指向第二個入度為0的頂點所對應的數(shù)組d中的元素，依此類推，最后一個入度為0頂點所對應的數(shù)組d中的元素保存著-1，表示為棧底。 例如，根據(jù)圖3-8所示的鄰接表，建立的入度為0的初始棧的過程為： (1) 開始置鏈棧為空，即給鏈棧指針top賦初值為-1： top=-1; (2) 將入度為0的元素d0

35、進棧，即： d0=top; top=0; 此時top指向d0元素，表示頂點v0的入度為0，而d0的值為-1，表明為棧底。 (3) 將入度為0的元素d1進棧，即: d1=top; top=1; 此時top指向d1元素，表示頂點v1的入度為0，而d1的值為0，表明下一個入度為0的元素為d0，即對應下一個入度為0的頂點為v0，d0的值為-1，所以此棧當前有兩個元素d1和d0。 (4) 因d2至d5的值均不為0，即對應的v2到v5的入度均不為0，所以它們均不進棧，至此，初始棧建立完畢，得到的數(shù)組d為： 0 1 2 3 4 5-1 0 2 2 1 3 top 將入度為0的頂點利用上述鏈棧鏈接起來后，拓撲

36、算法中循環(huán)執(zhí)行的第(1)步“選擇一個入度為0的頂點并輸出之”，可通過輸出棧頂指針top所代表的頂點序號來實現(xiàn)；第(2)步“從AOV網(wǎng)中刪除剛輸出的頂點（假定為vj，其中j等于top的值）及所有出邊”，可通過首先作退棧處理，使top指向下一個入度為0的元素，然后遍歷vj的鄰接點表，分別把所有鄰接點的入度減1，若減1后的入度為0則令該元素進棧來實現(xiàn)。此外，該循環(huán)的終止條件“直到不存在入度為0的頂點為止”，可通過判斷?？諄韺崿F(xiàn)。 對于圖3-7(a)，當刪除由top值所代表的頂點v1及所有出邊后，數(shù)組d變?yōu)椋?0 1 2 3 4 5-1 1 1 0 3 top 當依次刪除top所表示的每個頂點及所有出

37、邊后，數(shù)組d的變化分別如圖3-9(a)至(d)所示： 0 1 2 3 4 5-1 1 1 2 top (a) 刪除頂點v4及所有出邊 0 1 2 3 4 5 -1 1 2 top (b) 刪除頂點v0及所有出邊 0 1 2 3 4 5 -1 1 top (c) 刪除頂點v2及所有出邊 0 1 2 3 4 5 -1 top (d) 刪除頂點v3及所有出邊 圖3-9 數(shù)組d變化示意圖 當刪除頂點v5及所有出邊后，top的值為1，表示棧空，至此算法執(zhí)行結(jié)束，得到的拓撲序列為：1,4,0,2,3,5。 根據(jù)以上分析，給出拓撲排序算法的具體描述為： void Toposort(adjlist GL, i

38、nt n) /對用鄰接表GL表示的有向圖進行拓撲排序 int i,j,k,top,m=0; /m用來統(tǒng)計拓撲序列中的頂點數(shù) edgenode *p; /定義存儲圖中每個頂點入度的一維整型數(shù)組d int* d=new intn; /初始化數(shù)組d中的每個元素值為0 for(i=0; in; i+) di=0; /利用數(shù)組d中的對應元素統(tǒng)計出每個頂點的入度 for(i=0; iadjvex; dj+; p=p-next; /初始化用于鏈接入度為0的元素的棧的棧頂指針top為-1 top=-1; /建立初始化棧 for(i=0; in; i+) if(di=0) di=top; top=i; /每循環(huán)

39、一次刪除一個頂點及所有出邊 while(top!=-1) j=top; /j的值為一個入度為0的頂點序號 top=dtop; /刪除棧頂元素 coutjadjvex; /vk是vj的一個鄰接點 dk-; /vk的入度減1 if(dk=0) /把入度為0的元素進棧 dk=top; top=k; p=p-next; /p指向vj鄰接點表的下一個結(jié)點 coutendl; if(mn) /當輸出的頂點數(shù)小于圖中的頂點數(shù)時，輸出有回路信息 coutThe network has a cycle!endl; 拓撲排序?qū)嶋H上是對鄰接表表示的圖G進行遍歷的過程，每次訪問一個入度為0的頂點。若圖G中沒有回路，則

40、需要掃描鄰接表中的所有邊結(jié)點，再加上在算法開始時，為建立入度數(shù)組d需要訪問表頭向量中的每個域和其單鏈表中的每個結(jié)點，所以此算法的時間復雜性為O(n+e)。三、關(guān) 鍵 路 徑 與上節(jié)AOV網(wǎng)相對應的是AOE網(wǎng)(Activity On Edge network)，即邊表示活動的網(wǎng)絡。它與AOV網(wǎng)比較，更具有實用價值，通常用它表示一個工程的計劃或進度。 AOE網(wǎng)是一個有向帶權(quán)圖，圖中的邊表示活動(子工程)，邊上的權(quán)表示該活動的持續(xù)時間(duration time)，即完成該活動所需要的時間； 圖中的頂點表示事件，每個事件是活動之間的轉(zhuǎn)接點，即表示它的所有入邊活動到此完成，所有出邊活動從此開始。AOE

41、網(wǎng)中有兩個特殊的頂點(事件)，一個稱作源點，它表示整個工程的開始，亦即最早活動的起點，顯然它只有出邊，沒有入邊； 另一個稱作匯點，它表示整個工程的結(jié)束，亦即最后活動的終點，顯然它只有入邊，沒有出邊。除這兩個頂點外，其余頂點都既有入邊，也有出邊，是入邊活動和出邊活動的轉(zhuǎn)接點。在一個AOE網(wǎng)中，若包含有n個事件，通常令源點為第0個事件(假定從0開始編號)，匯點為第n-1個事件，其余事件的編號（即頂點序號）分別從1至n-2。 圖3-10就是一個AOE網(wǎng)，該網(wǎng)中包含有11項活動和9個事件。例如，邊表示活動a1，持續(xù)時間（即權(quán)值）為6，假定以天為單位，即a1需要6天完成，它以v0事件為起點，以v1事件為

42、終點；邊和分別表示活動a7和a8，它們的持續(xù)時間分別為9天和7天，它們均以v4事件為起點，但分別以v6和v7事件為終點。該網(wǎng)中的源點和匯點分別為第0個事件v0和最后一個事件v8，它們分別表示整個工程的開始和結(jié)束。圖3-10 一個AOE網(wǎng)對于一個AOE網(wǎng)，待研究的問題是：(1) 整個工程至少需要多長時間完成?(2) 哪些活動是影響工程進度的關(guān)鍵? 在AOE網(wǎng)中，一個頂點事件的發(fā)生或出現(xiàn)必須在它的所有入邊活動(或稱前驅(qū)活動)都完成之后，也就是說，只要有一個入邊活動沒有完成，該事件就不可能發(fā)生，顯然，一個事件的最早發(fā)生時間是它的所有入邊活動，或者說最后一個入邊活動剛完成的時間。同樣，一個活動的開始必

43、須在它的起點事件發(fā)生之后，也就是說，一個頂點事件沒有發(fā)生時，它的所有出邊活動(或稱后繼活動)都不可能開始，顯然一個活動的最早開始時間是它的起點事件的最早發(fā)生時間。若用vej表示頂點vj事件的最早發(fā)生時間，用ei表示vj一條出邊活動ai的最早開始時間，則有ei=vej。對于AOE網(wǎng)中的源點事件來說，因為它沒有入邊，所以隨時都可以發(fā)生，整個工程的開始時間就是它的發(fā)生時間，亦即最早發(fā)生時間，通常把此時間定義為0，從此開始推出其它事件的最早發(fā)生時間。例如，在圖3-10所示的AOE網(wǎng)中，v4事件的發(fā)生必須在a4和a5活動都完成之后，而a4和a5活動的開始又必須分別在v1和v2事件的發(fā)生之后，v1和v2事件的發(fā)生又必須分別在a1和a2活動的完成之后，因a1和a2的活動都起于源點，其最早開始時間均為0，所以a1和a2的完成時間分別為6和4，這也分別是v1和v2的最早發(fā)生時間，以及a4和a5的最早開始時間，故a4和a5的完成時間分別為7和5，由此可知v4事件的最早發(fā)生時間為7，即所有入邊活動中最后一個完成的時間。 從以上分析可知，一個事件的發(fā)生有待于它的所有入邊活動的完成，而每個入邊活動的開始和完成又有待于前驅(qū)事件的發(fā)生，而每個前驅(qū)事件的發(fā)生又有待于它們的所有入邊活動的完成，。總之，一個事件發(fā)生在從源點到該頂點