圖論中的概念及重要算法

1、圖論中的概念及重要算法常州一中 林厚從ch1、圖論中的基本概念一、 圖的概念簡單講，一個圖是由一些點和這些點之間的連線組成的。嚴格意義講，圖是一種數(shù)據(jù)結(jié)構(gòu)，定義為：graph=（V，E），V是點（稱為“頂點”）的非空有限集合，E是線（稱為“邊”）的集合，邊一般用（vx，vy）表示，其中vx，vy屬于V。圖（A）共有4個頂點、5條邊，表示為：V=v1，v2，v3，v4，E=（v1，v2），（v1，v3），（v1，v4），（v2，v3），（v2，v4）二、 無向圖和有向圖如果邊是沒有方向的，稱此圖為“無向圖”，如圖（A）和圖（C），用一對圓括號表示無向邊，如圖（A）中的邊（v1，v2），顯然（vx

2、，vy）和（vy，vx）是兩條等價的邊，所以在上面E的集合中沒有再出現(xiàn)邊（v2，v1）。 如果邊是有方向（帶箭頭）的，則稱此圖為“有向圖”，如圖（B），用一對尖括號表示有向邊，如圖（B）中的邊<v1，v2>。把邊<Vx，Vy>中Vx稱為起點，Vy稱為終點。顯然此時邊<vx，vy>與邊<vy，vx>是不同的兩條邊。有向圖中的邊又稱為弧，起點稱為弧頭，終點稱為弧尾。圖（B）表示為：V=v1，v2，v3，E=<v1，v2>，<v1，v3>，<v2，v3>，<v3，v2>如果兩個頂點U、V之間有一條邊相連，

3、則稱U、V這兩個頂點是關(guān)聯(lián)的。三、 帶權(quán)圖一個圖中的兩頂點間不僅是關(guān)聯(lián)的，而且在邊上還標明了數(shù)量關(guān)系，如圖（C），這種數(shù)量關(guān)系可能是距離、費用、時間、電阻等等，這些數(shù)值稱為相應(yīng)邊的權(quán)。邊上帶有權(quán)的圖稱為帶權(quán)圖，也稱為網(wǎng)（絡(luò)）。四、 階圖中頂點的個數(shù)稱為圖的階。圖（A）、圖（B）、圖（C）的階分別為4、3、5。五、 度圖中與某個頂點相關(guān)聯(lián)的邊的數(shù)目，稱為該頂點的度。度為奇數(shù)的頂點稱為奇點，度為偶數(shù)的頂點稱為偶點。圖（A）中頂點v1，v2是奇點，v3，v4是偶點。在有向圖中，把以頂點V為終點的邊的數(shù)目稱為頂點V的入度，把以頂點U為起點的邊的數(shù)目稱為頂點U的出度，出度為0的頂點稱為終端頂點。如圖（B

4、）中頂點v1的入度是0、出度是2，v2的入度是2、出度是1，v3的入度是2、出度是1，沒有終端頂點。 定理1：無向圖中所有頂點的度之和等于邊數(shù)的2倍，有向圖中的所有頂點的入度之和等于所有頂點的出度之和。 定理2：任意一個無向圖一定有偶數(shù)個(或0個)奇點。六、 完全圖若無向圖中的任意兩個頂點之間都存在著一條邊，有向圖中的任意兩個頂點之間都存在著方向相反的兩條邊，則稱此圖為完全圖。n階完全有向圖含有n*(n-1)條邊，n階完全無向圖含有 n*(n-1)/2條邊，當一個圖接近完全圖時，稱為稠密圖；相反，當一個圖的邊很少時，稱為稀疏圖。七、 子圖設(shè)有兩個圖G =（V，E）和G=（V，E），若V是V的子

5、集，E是E的子集，則稱G為G的子圖。八、 路（徑）在一個G =（V，E）的圖中，從頂點v到頂點v的一條路徑是一個頂點序列vi0，vi1，vi2，, vim，其中 vi0 = v， vim = v，若此圖是無向圖，則(vij-1，vij)E，1jm；若此圖是有向圖，則<vij-1，vij>E，1jm。路徑長度是指路徑上的邊或弧的數(shù)目。序列中頂點不重復(fù)出現(xiàn)的路徑稱為簡單路徑，頂點v和頂點v相同的路徑稱為回路（或環(huán)）。除了第一個頂點和最后一個頂點之外，其余頂點不重復(fù)出現(xiàn)的回路，稱為簡單回路（或簡單環(huán)）。九、連通圖在無向圖G中，如果從頂點U到頂點V有路徑，則稱U和V是連通的。如果對于圖G中

6、的任意兩個頂點U和V都是連通的，則稱圖G是連通圖，否則稱為非連通圖。在有向圖G中，如果對于任意兩個頂點U和V，從U到V和從V到U都存在路徑，則稱圖G是強連通圖。Ch2、圖的存儲結(jié)構(gòu)一、 鄰接矩陣表示法鄰接矩陣是表示頂點之間相鄰關(guān)系的矩陣，設(shè)G=V，E是一個度為n的圖（頂點序號分別用1，2，n表示），則G的鄰接矩陣是一個n階方陣，Gi,j的值定義如下：1或權(quán)值 當vi與vj之間有邊或弧時，取值為1或權(quán)值G i，j = 0或 當vi與vj之間無邊或弧時，取值為0或（無窮大）上面3個圖對應(yīng)的鄰接矩陣分別如下： 0 1 1 1 0 1 1 5 8 3G（A）= 1 0 1 1 G（B）= 0 0 1

7、G（C）= 5 2 6 1 1 0 0 0 1 0 8 2 10 4 1 1 0 0 10 11 3 6 4 11 采用鄰接矩陣表示圖，直觀方便，很容易查找圖中任兩個頂點i和j之間有無邊（或?。?，以及邊上的權(quán)值，只要看Ai,j的值即可，因為可以根據(jù)i,j的值隨機查找存取，所以時間復(fù)雜性為O（1）。也很容易計算一個頂點的度（或入度、出度）和鄰接點，其時間復(fù)雜性均為O（n）。但是，鄰接矩陣表示法的空間復(fù)雜性為O（n*n），如果用來表示稀疏圖，則會造成很大的空間浪費。二、邊集數(shù)組表示法邊集數(shù)組是利用一維數(shù)組存儲圖中所有邊的一種圖的表示方法。每個數(shù)組元素存儲一條邊的起點、終點和權(quán)值（如果有的話）。在邊

8、集數(shù)組中查找一條邊或一個頂點的度都需要掃描整個數(shù)組，所以其時間復(fù)雜性為O（e），e為邊數(shù)。這種表示方法適合那些對邊依次進行處理的運算，而不適合對頂點的運算和對任意一條邊的運算。從空間復(fù)雜性上講，邊集數(shù)組適合于存儲稀疏圖。三、鄰接表表示法（鏈式存儲法）鄰接表表示法是指對圖中的每個頂點vi（1in）建立一個鄰接關(guān)系的單鏈表，并把它們的表頭指針用一維向量數(shù)組存儲起來的一種圖的表示方法。為每個頂點vi（1in）建立的單鏈表，是表示以該頂點為起點的所有邊的信息（包括一個終點（鄰接點）序號、一個權(quán)值和一個鏈接域）。一維向量數(shù)組除了存儲每個頂點的表頭指針外，還要存儲該頂點的編號i。圖（C）的鄰接表表示為：圖

9、的鄰接表表示法便于查找任一頂點的關(guān)聯(lián)邊及鄰接點，只要從表頭向量中取出對應(yīng)的表頭指針，然后進行查找即可。由于無向圖的每個頂點的單鏈表平均長度為2e/n，所以查找運算的時間復(fù)雜性為O(e/n)。對于有向圖來說，想要查找一個頂點的后繼頂點和以該頂點為起點的邊、包括求該頂點的出度都很容易；但要查找一個頂點的前驅(qū)頂點和以此頂點為終點的邊、以及該頂點的入度就不方便了，需要掃描整個表，時間復(fù)雜度為O（n+e）。所以，對于經(jīng)常查找頂點入度或以該頂點為終點的關(guān)聯(lián)邊的運算時，可以建立一個逆鄰接表，該表中每個頂點的單鏈表存儲的是所有以該點為終點的關(guān)聯(lián)邊信息。甚至還可以把鄰接表和逆鄰接表結(jié)合起來，構(gòu)造出“十字鄰接表”

10、，此時，每個邊結(jié)點的數(shù)據(jù)信息包含五個域：起點、終點、權(quán)、以該頂點為終點的關(guān)聯(lián)邊的鏈接、以該頂點為起點的關(guān)聯(lián)邊的鏈接。表頭向量的結(jié)點也包括三個域：頂點編號、以該點為終點的表頭指針域、以該點為起點的表頭指針域。Ch3、圖的遍歷一、 概念從圖中某一頂點出發(fā)系統(tǒng)地訪問圖中所有頂點，使每個頂點恰好被訪問一次，這種運算操作被稱為圖的遍歷。為了避免重復(fù)訪問某個頂點，可以設(shè)一個標志數(shù)組visitedi，未訪問時值為false，訪問一次后就改為true。圖的遍歷分為深度優(yōu)先遍歷和廣度（寬度）優(yōu)先遍歷兩種方法。后面的函授將專門講解。這兒我們先作個介紹。二、深度優(yōu)先遍歷從圖中某個頂點Vi出發(fā)，訪問此頂點并作已訪問標

11、記，然后從Vi的一個未被訪問過的鄰接點Vj出發(fā)再進行深度優(yōu)先遍歷，當Vi的所有鄰接點都被訪問過時，則退回到上一個頂點Vk，再從Vk的另一個未被訪問過的鄰接點出發(fā)進行深度優(yōu)先遍歷，直至圖中所有頂點都被訪問到為止。如下面的左圖從頂點a出發(fā)，進行深度優(yōu)先遍歷的結(jié)果為：a，b，c，d，e，g，f；右圖從V1出發(fā)進行深度優(yōu)先遍歷的結(jié)果為：V1，V2，V4，V8，V5，V3，V6，V7。三、廣度（寬度）優(yōu)先遍歷從圖中某個頂點V0出發(fā)，訪問此頂點，然后依次訪問與V0鄰接的、未被訪問過的所有頂點，然后再分別從這些頂點出發(fā)進行廣度優(yōu)先遍歷，直到圖中所有被訪問過的頂點的相鄰頂點都被訪問到。若此時圖中還有頂點尚未被

12、訪問，則另選圖中一個未被訪問過的頂點作為起點，重復(fù)上述過程，直到圖中所有頂點都被訪問到為止。如上面的左圖從頂點a出發(fā)，進行廣度優(yōu)先遍歷的結(jié)果為：a，b，d，e，f，c，g；右圖從頂點V1出發(fā)，進行廣度優(yōu)先遍歷的結(jié)果為：V1，V2，V3，V4，V5，V6，V7，V8。兩種遍歷方法相比，深度優(yōu)先遍歷實際上是盡可能地走“頂點表”；而廣度優(yōu)先遍歷是盡可能沿頂點的“邊表”進行訪問，然后再沿邊表對應(yīng)頂點的邊表進行訪問，因此，有關(guān)邊表的頂點需要保存(用隊列，先進先出)，以便進一步進行廣度優(yōu)先遍歷。ch4、圖的重要算法一、 求圖的最小生成樹算法如果圖G=（V，E）是一個連通的無向圖，則把它的全部頂點V和一部分

13、邊E構(gòu)成一個子圖G，即G=（V， E），且邊集E能將圖中所有頂點連通又不形成回路，則稱子圖G是圖G的一棵生成樹。同一個圖可以有不同的生成樹，但可以證明：n個頂點的連通圖的生成樹必定含有n-1條邊。對于加權(quán)連通圖（連通網(wǎng)），生成樹的權(quán)即為生成樹中所有邊上的權(quán)值總和，權(quán)值最小的生成樹稱為圖的最小生成樹。求圖的最小生成樹具有很高的實際應(yīng)用價值，比如要在若干個城市之間建一個交通網(wǎng)，要求各個城市都能到達且造價最低，這就是一個典型的最小生成樹問題。那么如何求（最?。┥蓸淠?？求（最?。┥蓸淇梢詮哪硞€頂點采用深度優(yōu)先遍歷的方法，也可采用廣度優(yōu)先遍歷的方法，分別稱為深度優(yōu)先生成樹和廣度優(yōu)先生成樹。上圖中的圖

14、（B）和圖（C）所示兩棵生成樹，是對圖（A）分別進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷得到的一棵生成樹。也可以綜合應(yīng)用深度優(yōu)先遍歷和廣度優(yōu)先遍歷的特定算法，如：Prim算法和Kruskal算法，下面我們將分別介紹。1、用Prim算法求最小生成樹的思想如下：（設(shè)圖G的度為n，G=（V，E）設(shè)置一個頂點的集合S和一個邊的集合TE，S和TE的初始狀態(tài)均為空集；選定圖中的一個頂點K，從K開始生成最小生成樹，將K加入到集合S；重復(fù)下列操作，直到選取了n-1條邊： 選取一條權(quán)值最小的邊（X，Y），其中XS，not (YS)；將頂點Y加入集合S，邊（X，Y）加入集合TE；得到最小生成樹T =（S，TE）下面給出Pr

15、im算法構(gòu)造圖的最小生成樹的具體算法框架。 從文件中讀入圖的鄰接矩陣g； 邊集數(shù)組elist初始化；For i:=1 To n-1 Do Begin elisti.fromv:=1；elisti.endv:=i+1；elisti.weight:=g1,i+1； End； 求出最小生成樹的n-1條邊； For k:=1 To n-1 Do Begin min:=maxint；m:=k； For j:=k To n-1 Do 查找權(quán)值最小的一條邊 If elistj.weight<min Then Begin min:=elistj.weight；m:=j；End； If m<>

16、k Then Begin t:=elistk；elistk:=elistm；elistm:=t；End；把權(quán)值最小的邊調(diào)到第k個單元 j:=elistk.endv； j為新加入的頂點 For i:=k+1 To n-1 Do 修改未加入的邊集 Begin s:=elisti.endv； w:=gj,s； If w<elisti.weight Then Begin elisti.weight:=w；elisti.fromv:=j；End； End； End； 輸出；2、用Kruskal算法求最小生成樹的思想如下：（設(shè)圖G的度為n，G=（V，E）設(shè)最小生成樹為T=（V，TE），設(shè)置邊的集合T

17、E的初始狀態(tài)為空集。將圖G中的邊按權(quán)值從小到大排好序，然后從小的開始依次選取，若選取的邊使生成樹T不形成回路，則把它并入TE中，保留作為T的一條邊；若選取的邊使生成樹形成回路，則將其舍棄；如此進行下去，直到TE中包含n-1條邊為止。最后的T即為最小生成樹。Kruskal算法在實現(xiàn)過程中的關(guān)鍵和難點在于：如何判斷欲加入的一條邊是否與生成樹中已保留的邊形成回路？我們可以將頂點劃分到不同的集合中，每個集合中的頂點表示一個無回路的連通分量，很明顯算法開始時，把所有n個頂點劃分到n個集合中，每個集合只有一個頂點，表明頂點之間互不相通。當選取一條邊時，若它的兩個頂點分屬于不同的集合，則表明此邊連通了兩個不

18、同的連通分量，因每個連通分量無回路，所以連通后得到的連通分量仍不會產(chǎn)生回路，因此這條邊應(yīng)該保留，且把它們作為一個連通分量，即把它的兩個頂點所在集合合并成一個集合。如果選取的一條邊的兩個頂點屬于同一個集合，則此邊應(yīng)該舍棄，因為同一個集合中的頂點是連通無回路的，若再加入一條邊則必然產(chǎn)生回路。下面給出利用Kruskal算法構(gòu)造圖的最小生成樹的具體算法框架。 將圖的存儲結(jié)構(gòu)轉(zhuǎn)換成邊集數(shù)組表示的形式elist，并按照權(quán)值從小到大排好序； 設(shè)數(shù)組C1.n-1用來存儲最小生成樹的所有邊，Ci是第i次選取的可行邊在排好序的elist中的下標； 設(shè)一個數(shù)組S1.n，Si都是集合，初始時Si= i 。 i:=1；

19、獲取的第i條最小生成樹的邊j:=1；邊集數(shù)組的下標While i<=n-1 Do Begin For k:=1 To n Do Begin 取出第j條邊，記下兩個頂點分屬的集合序號 If elistj.fromv in sk Then m1:=k； If elistj.endv in sk Then m2:=k； End； If m1<>m2 Then Begin 找到的elist第j條邊滿足條件，作為第i條邊保留 Ci:=j； i:=i+1； sm1:=sm1+sm2；合并兩個集合 sm2:= ； 另一集合置空 End； j:=j+1； 取下條邊，繼續(xù)判斷 End； 輸出最

20、小生成樹的各邊：elistCi二、求圖的最短路徑算法在帶權(quán)圖G=（V，E）中，若頂點 Vi,Vj是圖G的兩個頂點，從頂點Vi到Vj的路徑長度定義為路徑上各條邊的權(quán)值之和。從頂點Vi到Vj可能有多條路徑，其中路徑長度最小的一條路徑稱為頂點Vi到Vj的最短路徑。求最短路徑具有很高的實用價值，在各種競賽中經(jīng)常遇到。一般有兩類最短路徑問題：一類是求從某個頂點（源點）到其它頂點（終點）的最短路徑；另一類是求圖中每一對頂點間的最短路徑。對于不帶權(quán)的圖，只要人為的把每條邊加上權(quán)值1，即可當作帶權(quán)圖一樣處理了。1、從一個頂點到其余各頂點的最短路徑看上圖，假設(shè)C1,C2,C3,C4,C5,C6是六座城市，他們之

21、間的連線表示兩城市間有道路相通，連線旁的數(shù)字表示路程。請編寫一程序，找出C1到Ci的最短路徑(2i6)，輸出路徑序列及最短路徑的路程長度。對于一個含有n個頂點和e條邊的圖來說，從某一個頂點Vi到其余任一頂點Vj的最短路徑，可能是它們之間的邊（Vi，Vj），也可能是經(jīng)過k個中間頂點和k+1條邊所形成的路徑(1kn-2)。下面給出解決這個問題的Dijkstra算法思想。設(shè)圖G用鄰接矩陣的方式存儲在GA中，GAi,j=maxint表示Vi，Vj是不關(guān)聯(lián)的，否則為權(quán)值（大于0的實數(shù)）。設(shè)集合S用來保存已求得最短路徑的終點序號，初始時S=Vi表示只有源點，以后每求出一個終點Vj，就把它加入到集合中并作為

22、新考慮的中間頂點。設(shè)數(shù)組dist1.n用來存儲當前求得的最短路徑，初始時Vi，Vj如果是關(guān)聯(lián)的，則distj等于權(quán)值，否則等于maxint，以后隨著新考慮的中間頂點越來越多，distj可能越來越小。再設(shè)一個與dist對應(yīng)的數(shù)組path1.n用來存放當前最短路徑的邊，初始時為Vi到Vj的邊，如果不存在邊則為空。執(zhí)行時，先從S以外的頂點（即待求出最短路徑的終點）所對應(yīng)的dist數(shù)組元素中，找出其值最小的元素（假設(shè)為distm），該元素值就是從源點Vi到終點Vm的最短路徑長度，對應(yīng)的pathm中的頂點或邊的序列即為最短路徑。接著把Vm并入集合S中，然后以Vm作為新考慮的中間頂點，對S以外的每個頂點V

23、j，比較distm+GAm,j的distj的大小，若前者小，表明加入了新的中間頂點后可以得到更好的方案，即可求得更短的路徑，則用它代替distj，同時把Vj或邊（Vm，Vj）并入到pathj中。重復(fù)以上過程n-2次，即可在dist數(shù)組中得到從源點到其余各終點的最段路徑長度，對應(yīng)的path數(shù)組中保存著相應(yīng)的最段路徑。對于上圖，采用Dijkstra算法找出C1到Ci之間的最短路徑(2i6)的過程如下：初始時：123456Dist048maxintmaxintmaxintPathC1C1,C2C1,C3第一次：選擇m=2，則S=C1,C2，計算比較dist2+GA2,j與distj的大小（3j6）1

24、23456Dist047810maxintPathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C5第二次：選擇m=3，則S=C1,C2,C3，計算比較dist3+GA3,j與distj的大?。?j6）123456Dist04789maxintPathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5第三次：選擇m=4，S=C1,C2,C3,C4，計算比較dist4+GA4,j與distj的大?。?j6）123456Dist0478917PathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5C1,C2,C4,C6第四次：選擇m=5，則S=C1

25、,C2,C3,C4,C5，計算比較dist5+GA5,j與distj的大小（j=6）123456Dist0478913PathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5C1,C2,C3,C5,C6因為該圖的度n=6，所以執(zhí)行n-2=4次后結(jié)束，此時通過dist和path數(shù)組可以看出：C1到C2的最短路徑為：C1C2，長度為：4；C1到C3的最短路徑為：C1C2C3，長度為：7；C1到C4的最短路徑為：C1C2C4，長度為：8；C1到C5的最短路徑為：C1C2C3C5，長度為：9；C1到C6的最短路徑為：C1C2C3C5C6，長度為：13；下面給出具體的Dijkstra

26、算法框架（注：為了實現(xiàn)上的方便，我們用一個一維數(shù)組s1.n代替集合S，用來保存已求得最短路徑的終點集合，即如果sj=0表示頂點Vj不在集合中，反之，sj=1表示頂點Vj已在集合中）。Procedure Dijkstra(GA,dist,path,i)； 表示求Vi到圖G中其余頂點的最短路徑，GA為 圖G的鄰接矩陣，dist和path為變量型參數(shù)，其中path的基類型為集合BeginFor j:=1 To n Do Begin 初始化 If j<>i Then sj:=0 Else sj:=1； distj:=GAi,j； If distj<maxint maxint為假設(shè)的一

27、個足夠大的數(shù) Then pathj:=i+jElse pathj:= ； End；For k:=1 To n-2 Do Begin w:=maxint；m:=i； For j:=1 To n Do 求出第k個終點Vm If (sj=0) and (distj<w) Then Begin m:=j；w:=distj； End； If m<>i Then sm:=1 else exit；若條件成立，則把Vm加入到S中，否則退出循環(huán)，因為剩余的終點，其最短路徑長度均為maxint，無需再計算下去 For j:=1 To n Do 對sj=0的更優(yōu)元素作必要修改 If (sj=0)

28、and (distm+GAm,j<distj) Then Begin Distj:=distm+GAm,j；pathj:=pathm+j； End； End；End；2、任意一對頂點之間的最短路徑這個問題的解法有兩種：一是分別以圖中的每個頂點為源點共調(diào)用n次Dijkstra算法，這種算法的時間復(fù)雜度為O（n3）；另外還有一種算法：Floyed算法，它的思路簡單，但時間復(fù)雜度仍然為O（n3），下面介紹Floyed算法。設(shè)具有n個頂點的一個帶權(quán)圖G的鄰接矩陣用GA表示，再設(shè)一個與GA同類型的表示每對頂點之間最短路徑長度的二維數(shù)組A，A的初值等于GA。Floyed算法需要在A上進行n次運算，每

29、次以Vk（1kn）作為新考慮的中間點，求出每對頂點之間的當前最短路徑長度，最后依次運算后，A中的每個元素Ai，j就是圖G中從頂點Vi到頂點Vj的最短路徑長度。再設(shè)一個二維數(shù)組P1.n,1.n，記錄最短路徑，其元素類型為集合類型set of 1.n。Floyed算法的具體描述如下：Procedure Floyed(GA，A，P)； Begin For i:=1 To n Do 最短路徑長度數(shù)組和最短路徑數(shù)組初始化 For j:=1 To n Do Begin Ai,j:=GAi,j； If Ai,j<maxint Then pi,j:=i+jElse pi,j:= ； End； For k

30、:=1 To n Do n次運算 For i:=1 To n Do For j:=1 To n Do Begin If (i=k)or(j=k)or(i=j) Then Continue； 無需計算，直接進入下一輪循環(huán) If Ai,k+Ak,j<Ai,j Then Begin 找到更短路徑、保存 Ai,j：= Ai,k+Ak,j； Pi,j：= Pi,k+Pk,j； End； End； End；對于上圖，大家可以運用Floyed算法，手工或編程找出任意一對頂點之間的最短路徑及其長度。三、拓撲排序算法在日常生活中，一項大的工程可以看作是由若干個子工程（這些子工程稱為“活動”）組成的集合，這

31、些子工程（活動）之間必定存在一些先后關(guān)系，即某些子工程（活動）必須在其它一些子工程（活動）完成之后才能開始，我們可以用有向圖來形象地表示這些子工程（活動）之間的先后關(guān)系，子工程（活動）為頂點，子工程（活動）之間的先后關(guān)系為有向邊，這種有向圖稱為“頂點活動網(wǎng)絡(luò)”，又稱“AOV網(wǎng)”。在AOV網(wǎng)中，有向邊代表子工程（活動）的先后關(guān)系，即有向邊的起點活動是終點活動的前驅(qū)活動，只有當起點活動完成之后終點活動才能進行。如果有一條從頂點Vi到Vj的路徑，則說Vi是Vj的前驅(qū)，Vj是Vi的后繼。如果有弧<Vi，Vj>，則稱Vi是Vj的直接前驅(qū)，Vj是Vi的直接后繼。一個AOV網(wǎng)應(yīng)該是一個有向無環(huán)圖

32、，即不應(yīng)該帶有回路，否則必定會有一些活動互相牽制，造成環(huán)中的活動都無法進行。把不帶回路的AOV網(wǎng)中的所有活動排成一個線性序列，使得每個活動的所有前驅(qū)活動都排在該活動的前面，這個過程稱為“拓撲排序”，所得到的活動序列稱為“拓撲序列”。需要注意的是AOV網(wǎng)的拓撲序列是不唯一的，如對下圖進行拓撲排序至少可以得到如下幾種拓撲序列：02143567、01243657、02143657、01243567。 在上圖所示的AOV網(wǎng)中，工程1和過程2顯然可以同時進行，先后無所謂；但工程4卻要等工程1和工程2都完成以后才可進行；工程3要等到工程1和工程4完成以后才可進行；工程5又要等到工程3、工程4完成以后才可進

33、行；工程6則要等到工程4完成后才能進行；工程7要等到工程3、工程5、過程6都完成后才能進行。可見由AOV網(wǎng)構(gòu)造拓撲序列具有很高的實際應(yīng)用價值。其實，構(gòu)造拓撲序列的拓撲排序算法思想很簡單：只要選擇一個入度為0的頂點并輸出，然后從AOV網(wǎng)中刪除此頂點及以此頂點為起點的所有關(guān)聯(lián)邊；重復(fù)上述兩步，直到不存在入度為0的頂點為止，若輸出的頂點數(shù)小于AOV網(wǎng)中的頂點數(shù)，則輸出“有回路信息”，否則輸出的頂點序列就是一種拓撲序列。對上圖進行拓撲排序的過程如下：1、 選擇頂點0（唯一）， 輸出0， 刪除邊<0，1>，<0，2>；2、 選擇頂點1（不唯一，可選頂點2）， 輸出1， 刪除邊&l

34、t;1，3>，<1，4>；3、 選擇頂點2（唯一）， 輸出2， 刪除邊<2，4>；4、 選擇頂點4（唯一）， 輸出4， 刪除邊<4，3>，<4，5>，<4,6>；5、 選擇頂點3（不唯一，可選頂點6）， 輸出3， 刪除邊<3，5>，<3，7>；6、 選擇頂點5（不唯一，可選頂點6）， 輸出5， 刪除邊<5，7>；7、 選擇頂點6（唯一）， 輸出6， 刪除邊<6，7>；8、 選擇頂點7（唯一）， 輸出7， 結(jié)束。輸出的頂點數(shù)m=8，與AOV網(wǎng)中的頂點數(shù)n=8相等，所以輸出一種拓撲序列

35、：01243567。為了算法實現(xiàn)上的方便，我們采用鄰接表存儲AOV網(wǎng)，不過稍做修改，在頂點表中增加一個記錄頂點入度的域id，具體的拓撲排序算法描述如下：Procedure TopSort(dig:graphlist)；用鄰接表dig存儲圖GVar n,top,i,j,k,m: Integer；P:graphlist；Begin n:=dig.adjv； 取頂點總個數(shù) top:=0； 堆棧、初始化 For i:=1 To n Do 對入度為0的所有頂點進行訪問，序號壓棧If dig.adji.id = 0 Then Begin dig.adji.id:=top； top:=i； End； m:=

36、0； 記錄輸出的頂點個數(shù) While top<>0 Do 棧不空Begin j:=top； 取一個入度為0的頂點序號 top:=dig.adjtop.id； 出棧、刪除當前處理的頂點、指向下個入度為0的頂點 Write(dig.adjtop.v)； 輸出頂點序號 m:=m+1； p:=dig.adjj.link； 指向Vj鄰接表的第一個鄰接點 While p<>nil Do 刪除所有與Vj相關(guān)邊 Begin k:=p.adjv； 下一個鄰接點 dig.adjk.id:= dig.adjk.id - 1； 修正相應(yīng)點的入度 If dig.adjk.id = 0 Then

37、Begin 入度為0的頂點入棧 dig.adjk.id:=top；top:=k； End； p:=p.next； 沿邊表找下一個鄰接點 End；End；If m<n Then Writeln(no solution!)； 有回路End；四、關(guān)鍵路徑算法利用AOV網(wǎng)絡(luò)，對其進行拓撲排序能對工程中活動的先后順序作出安排。但一個活動的完成總需要一定的時間，為了能估算出某個活動的開始時間，找出那些影響工程完成時間的最主要的活動，我們可以利用帶權(quán)的有向網(wǎng)，圖中的邊表示活動，邊上的權(quán)表示完成該活動所需要的時間，一條邊的兩個頂點分別表示活動的開始事件和結(jié)束事件，這種用邊表示活動的網(wǎng)絡(luò)，稱為“AOE網(wǎng)”

38、。其中，有兩個特殊的頂點（事件），分別稱為源點和匯點，源點表示整個工程的開始，通常令第一個事件（事件1）作為源點，它只有出邊沒有入邊；匯點表示整個工程的結(jié)束，通常令最后一個事件（事件n）作為匯點，它只有入邊沒有出邊；其余事件的編號為2到n-1。在實際應(yīng)用中，AOE網(wǎng)應(yīng)該是沒有回路的，并且存在唯一的入度為0的源點和唯一的出度為0的匯點。下圖表示一個具有12個活動的AOE網(wǎng)。圖中有8個頂點，分別表示事件0到7，其中，0表示開始事件，7表示結(jié)束事件，邊上的權(quán)表示完成該活動所需要的時間。AOE網(wǎng)絡(luò)要研究的問題是完成整個工程至少需要多少時間？哪些活動是影響工程進度的關(guān)鍵？下面先討論一個事件的最早發(fā)生時間

39、和一個活動的最早開始時間。如上圖，事件Vj必須在它的所有入邊活動eik（1kn）都完成后才能發(fā)生。活動eik（1kn）的最早開始時間是與它對應(yīng)的起點事件Vik的最早發(fā)生時間。所有以事件Vj為起點事件的出邊活動ejk（1km）的最早開始時間都等于事件Vj的最早發(fā)生時間。所以，我們可以從源點出發(fā)按照上述方法，求出所有事件的最早發(fā)生時間。設(shè)數(shù)組earliest1.n表示所有事件的最早發(fā)生時間，則我們可以按照拓撲順序依次計算出earliestk：earliest1=0earliestk=maxearliestj+dutj,k (其中，事件j是事件k的直接前驅(qū)事件，dutj,k表示邊<j，k>

40、;上的權(quán))對于圖5_10，用上述方法求earliest0.7的過程如下：earliest0=0earliest1=earliest0+dut0,1=0+6=6earliest2=earliest0+dut0,2=0+7=7earliest4=maxearliest1+dut1,4，earliest2+dut2,4=max6+5,7+4=11earliest3=maxearliest1+dut1,3，earliest4+dut4,3=max6+3,11+3=14earliest5=maxearliest3+dut3,5，earliest4+dut4,5=max14+2,11+4=16earlie

41、st6=earliest4+dut4,6=11+3=14earliest7=maxearliest3+dut3,7，earliest5+dut5,7, earliest6+dut6,7=max14+5,16+2,14+4=19最后得到的earliest7就是匯點的最早發(fā)生時間，從而可知整個工程至少需要19天完成。但是，在不影響整個工程按時完成的前提下，一些事件可以不在最早發(fā)生時間發(fā)生，而向后推遲一段時間，我們把事件最晚必須發(fā)生的時間稱為該事件的最遲發(fā)生時間。同樣，有些活動也可以推遲一段時間完成而不影響整個工程的完成，我們把活動最晚必須開始的時間稱為該活動的最遲開始時間。一個事件在最遲發(fā)生時間內(nèi)

42、仍沒發(fā)生，或一個活動在最遲開始時間內(nèi)仍沒開始，則必然會影響整個工程的按時完成。如上圖，事件Vj的最遲發(fā)生時間應(yīng)該為：它的所有直接后繼事件Vjk（1km）的最遲發(fā)生時間減去相應(yīng)邊<Vj，Vjk>上的權(quán)（活動ejk需要時間），取其中的最小值。且匯點的最遲發(fā)生時間就是它的最早發(fā)生時間，再按照逆拓撲順序依次計算出所有事件的最遲發(fā)生時間，設(shè)用數(shù)組lastest1.n表示，即：lastestn=earliestnlastestj=minlastestk-dutj,k (其中，事件k是事件j的直接后繼事件，dutj,k表示邊<j，k>上的權(quán))對于圖5_10，用上述方法求lastest

43、 0.7的過程如下：lastest7=earliest7=19lastest6=lastest7-dut6,7=19-4=15lastest5=lastest7-dut5,7=19-2=17lastest3=minlastest5-dut3,5，lastest7-dut3,7 =min17-2,19-5 =14lastest4=minlastest3-dut4,3，lastest5-dut4,5, lastest6-dut4,6 =min14-3,17-4,15-3 =11lastest2=lastest4-dut2,4=11-4=7lastest1=minlastest3-dut1,3，la

44、stest4-dut1,4 =min14-3,11-5 =6lastest0=minlastest1-dut0,1，lastest2-dut0,2 =min6-6,7-7 =0計算好每個事件的最早和最遲發(fā)生時間后，我們可以很容易地算出每個活動的最早和最遲開始時間，假設(shè)分別用actearliest和actlastest數(shù)組表示，設(shè)活動i的兩端事件分別為事件j和事件k,如下所示： 活動i 事件j > 事件k則：actearliesti=earliestjactlastesti=lastestk-dutj,k對于上面的例子，用上述方法求得所有活動的最早和最遲開始時間如下表：活動<0,1><0,2><1,3><1,4><2,4><3,5><3,7><4,3><4,5><4,6><5,7><6,7>最早0066714141111111614最遲00116715141113121715余量00500