圖論中的概念及重要算法

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

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

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

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

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

6、的任意兩個(gè)頂點(diǎn)U和V都是連通的，則稱圖G是連通圖，否則稱為非連通圖。在有向圖G中，如果對(duì)于任意兩個(gè)頂點(diǎn)U和V，從U到V和從V到U都存在路徑，則稱圖G是強(qiáng)連通圖。Ch2、圖的存儲(chǔ)結(jié)構(gòu)一、 鄰接矩陣表示法鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣，設(shè)G=V，E是一個(gè)度為n的圖（頂點(diǎn)序號(hào)分別用1，2，n表示），則G的鄰接矩陣是一個(gè)n階方陣，Gi,j的值定義如下：1或權(quán)值 當(dāng)vi與vj之間有邊或弧時(shí)，取值為1或權(quán)值G i，j = 0或 當(dāng)vi與vj之間無邊或弧時(shí)，取值為0或（無窮大）上面3個(gè)圖對(duì)應(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 采用鄰接矩陣表示圖，直觀方便，很容易查找圖中任兩個(gè)頂點(diǎn)i和j之間有無邊（或?。?，以及邊上的權(quán)值，只要看Ai,j的值即可，因?yàn)榭梢愿鶕?jù)i,j的值隨機(jī)查找存取，所以時(shí)間復(fù)雜性為O（1）。也很容易計(jì)算一個(gè)頂點(diǎn)的度（或入度、出度）和鄰接點(diǎn)，其時(shí)間復(fù)雜性均為O（n）。但是，鄰接矩陣表示法的空間復(fù)雜性為O（n*n），如果用來表示稀疏圖，則會(huì)造成很大的空間浪費(fèi)。二、邊集數(shù)組表示法邊集數(shù)組是利用一維數(shù)組存儲(chǔ)圖中所有邊的一種圖的表示方法。每個(gè)數(shù)組元素存儲(chǔ)一條邊的起點(diǎn)、終點(diǎn)和權(quán)值（如果有的話）。在邊

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

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

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

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

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

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

14、（B）和圖（C）所示兩棵生成樹，是對(duì)圖（A）分別進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷得到的一棵生成樹。也可以綜合應(yīng)用深度優(yōu)先遍歷和廣度優(yōu)先遍歷的特定算法，如：Prim算法和Kruskal算法，下面我們將分別介紹。1、用Prim算法求最小生成樹的思想如下：（設(shè)圖G的度為n，G=（V，E）設(shè)置一個(gè)頂點(diǎn)的集合S和一個(gè)邊的集合TE，S和TE的初始狀態(tài)均為空集；選定圖中的一個(gè)頂點(diǎn)K，從K開始生成最小生成樹，將K加入到集合S；重復(fù)下列操作，直到選取了n-1條邊： 選取一條權(quán)值最小的邊（X，Y），其中XS，not (YS)；將頂點(diǎn)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個(gè)單元 j:=elistk.endv； j為新加入的頂點(diǎn) 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的一條邊；若選取的邊使生成樹形成回路，則將其舍棄；如此進(jìn)行下去，直到TE中包含n-1條邊為止。最后的T即為最小生成樹。Kruskal算法在實(shí)現(xiàn)過程中的關(guān)鍵和難點(diǎn)在于：如何判斷欲加入的一條邊是否與生成樹中已保留的邊形成回路？我們可以將頂點(diǎn)劃分到不同的集合中，每個(gè)集合中的頂點(diǎn)表示一個(gè)無回路的連通分量，很明顯算法開始時(shí)，把所有n個(gè)頂點(diǎn)劃分到n個(gè)集合中，每個(gè)集合只有一個(gè)頂點(diǎn)，表明頂點(diǎn)之間互不相通。當(dāng)選取一條邊時(shí)，若它的兩個(gè)頂點(diǎn)分屬于不同的集合，則表明此邊連通了兩個(gè)不

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

19、獲取的第i條最小生成樹的邊j:=1；邊集數(shù)組的下標(biāo)While i<=n-1 Do Begin For k:=1 To n Do Begin 取出第j條邊，記下兩個(gè)頂點(diǎn)分屬的集合序號(hào) 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；合并兩個(gè)集合 sm2:= ； 另一集合置空 End； j:=j+1； 取下條邊，繼續(xù)判斷 End； 輸出最

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

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

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

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

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

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

26、算法框架（注：為了實(shí)現(xiàn)上的方便，我們用一個(gè)一維數(shù)組s1.n代替集合S，用來保存已求得最短路徑的終點(diǎn)集合，即如果sj=0表示頂點(diǎn)Vj不在集合中，反之，sj=1表示頂點(diǎn)Vj已在集合中）。Procedure Dijkstra(GA,dist,path,i)； 表示求Vi到圖G中其余頂點(diǎn)的最短路徑，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、個(gè)足夠大的數(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個(gè)終點(diǎn)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)，因?yàn)槭Ｓ嗟慕K點(diǎn)，其最短路徑長(zhǎng)度均為maxint，無需再計(jì)算下去 For j:=1 To n Do 對(duì)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、任意一對(duì)頂點(diǎn)之間的最短路徑這個(gè)問題的解法有兩種：一是分別以圖中的每個(gè)頂點(diǎn)為源點(diǎn)共調(diào)用n次Dijkstra算法，這種算法的時(shí)間復(fù)雜度為O（n3）；另外還有一種算法：Floyed算法，它的思路簡(jiǎn)單，但時(shí)間復(fù)雜度仍然為O（n3），下面介紹Floyed算法。設(shè)具有n個(gè)頂點(diǎn)的一個(gè)帶權(quán)圖G的鄰接矩陣用GA表示，再設(shè)一個(gè)與GA同類型的表示每對(duì)頂點(diǎn)之間最短路徑長(zhǎng)度的二維數(shù)組A，A的初值等于GA。Floyed算法需要在A上進(jìn)行n次運(yùn)算，每

29、次以Vk（1kn）作為新考慮的中間點(diǎn)，求出每對(duì)頂點(diǎn)之間的當(dāng)前最短路徑長(zhǎng)度，最后依次運(yùn)算后，A中的每個(gè)元素Ai，j就是圖G中從頂點(diǎn)Vi到頂點(diǎn)Vj的最短路徑長(zhǎng)度。再設(shè)一個(gè)二維數(shù)組P1.n,1.n，記錄最短路徑，其元素類型為集合類型set of 1.n。Floyed算法的具體描述如下：Procedure Floyed(GA，A，P)； Begin For i:=1 To n Do 最短路徑長(zhǎng)度數(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次運(yù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； 無需計(jì)算，直接進(jìn)入下一輪循環(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；對(duì)于上圖，大家可以運(yùn)用Floyed算法，手工或編程找出任意一對(duì)頂點(diǎn)之間的最短路徑及其長(zhǎng)度。三、拓?fù)渑判蛩惴ㄔ谌粘Ｉ钪?，一?xiàng)大的工程可以看作是由若干個(gè)子工程（這些子工程稱為“活動(dòng)”）組成的集合，這

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

32、，即不應(yīng)該帶有回路，否則必定會(huì)有一些活動(dòng)互相牽制，造成環(huán)中的活動(dòng)都無法進(jìn)行。把不帶回路的AOV網(wǎng)中的所有活動(dòng)排成一個(gè)線性序列，使得每個(gè)活動(dòng)的所有前驅(qū)活動(dòng)都排在該活動(dòng)的前面，這個(gè)過程稱為“拓?fù)渑判颉?，所得到的活?dòng)序列稱為“拓?fù)湫蛄小薄Ｐ枰⒁獾氖茿OV網(wǎng)的拓?fù)湫蛄惺遣晃ㄒ坏?，如?duì)下圖進(jìn)行拓?fù)渑判蛑辽倏梢缘玫饺缦聨追N拓?fù)湫蛄校?2143567、01243657、02143657、01243567。 在上圖所示的AOV網(wǎng)中，工程1和過程2顯然可以同時(shí)進(jìn)行，先后無所謂；但工程4卻要等工程1和工程2都完成以后才可進(jìn)行；工程3要等到工程1和工程4完成以后才可進(jìn)行；工程5又要等到工程3、工程4完成以后才可進(jìn)

33、行；工程6則要等到工程4完成后才能進(jìn)行；工程7要等到工程3、工程5、過程6都完成后才能進(jìn)行。可見由AOV網(wǎng)構(gòu)造拓?fù)湫蛄芯哂泻芨叩膶?shí)際應(yīng)用價(jià)值。其實(shí)，構(gòu)造拓?fù)湫蛄械耐負(fù)渑判蛩惴ㄋ枷牒芎?jiǎn)單：只要選擇一個(gè)入度為0的頂點(diǎn)并輸出，然后從AOV網(wǎng)中刪除此頂點(diǎn)及以此頂點(diǎn)為起點(diǎn)的所有關(guān)聯(lián)邊；重復(fù)上述兩步，直到不存在入度為0的頂點(diǎn)為止，若輸出的頂點(diǎn)數(shù)小于AOV網(wǎng)中的頂點(diǎn)數(shù)，則輸出“有回路信息”，否則輸出的頂點(diǎn)序列就是一種拓?fù)湫蛄?。?duì)上圖進(jìn)行拓?fù)渑判虻倪^程如下：1、 選擇頂點(diǎn)0（唯一）， 輸出0， 刪除邊<0，1>，<0，2>；2、 選擇頂點(diǎn)1（不唯一，可選頂點(diǎn)2）， 輸出1， 刪除邊&l

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

35、：01243567。為了算法實(shí)現(xiàn)上的方便，我們采用鄰接表存儲(chǔ)AOV網(wǎng)，不過稍做修改，在頂點(diǎn)表中增加一個(gè)記錄頂點(diǎn)入度的域id，具體的拓?fù)渑判蛩惴枋鋈缦拢篜rocedure TopSort(dig:graphlist)；用鄰接表dig存儲(chǔ)圖GVar n,top,i,j,k,m: Integer；P:graphlist；Begin n:=dig.adjv； 取頂點(diǎn)總個(gè)數(shù) top:=0； 堆棧、初始化 For i:=1 To n Do 對(duì)入度為0的所有頂點(diǎn)進(jìn)行訪問，序號(hào)壓棧If dig.adji.id = 0 Then Begin dig.adji.id:=top； top:=i； End； m:=

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

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

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

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

40、;上的權(quán))對(duì)于圖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就是匯點(diǎn)的最早發(fā)生時(shí)間，從而可知整個(gè)工程至少需要19天完成。但是，在不影響整個(gè)工程按時(shí)完成的前提下，一些事件可以不在最早發(fā)生時(shí)間發(fā)生，而向后推遲一段時(shí)間，我們把事件最晚必須發(fā)生的時(shí)間稱為該事件的最遲發(fā)生時(shí)間。同樣，有些活動(dòng)也可以推遲一段時(shí)間完成而不影響整個(gè)工程的完成，我們把活動(dòng)最晚必須開始的時(shí)間稱為該活動(dòng)的最遲開始時(shí)間。一個(gè)事件在最遲發(fā)生時(shí)間內(nèi)

42、仍沒發(fā)生，或一個(gè)活動(dòng)在最遲開始時(shí)間內(nèi)仍沒開始，則必然會(huì)影響整個(gè)工程的按時(shí)完成。如上圖，事件Vj的最遲發(fā)生時(shí)間應(yīng)該為：它的所有直接后繼事件Vjk（1km）的最遲發(fā)生時(shí)間減去相應(yīng)邊<Vj，Vjk>上的權(quán)（活動(dòng)ejk需要時(shí)間），取其中的最小值。且匯點(diǎn)的最遲發(fā)生時(shí)間就是它的最早發(fā)生時(shí)間，再按照逆拓?fù)漤樞蛞来斡?jì)算出所有事件的最遲發(fā)生時(shí)間，設(shè)用數(shù)組lastest1.n表示，即：lastestn=earliestnlastestj=minlastestk-dutj,k (其中，事件k是事件j的直接后繼事件，dutj,k表示邊<j，k>上的權(quán))對(duì)于圖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計(jì)算好每個(gè)事件的最早和最遲發(fā)生時(shí)間后，我們可以很容易地算出每個(gè)活動(dòng)的最早和最遲開始時(shí)間，假設(shè)分別用actearliest和actlastest數(shù)組表示，設(shè)活動(dòng)i的兩端事件分別為事件j和事件k,如下所示： 活動(dòng)i 事件j > 事件k則：actearliesti=earliestjactlastesti=lastestk-dutj,k對(duì)于上面的例子，用上述方法求得所有活動(dòng)的最早和最遲開始時(shí)間如下表：活動(dòng)<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