1、數(shù)據(jù)結(jié)構(gòu),第七章 圖,第六章 圖,第六章 圖,知 識(shí) 點(diǎn) 圖的邏輯結(jié)構(gòu)特征及圖的基本術(shù)語(yǔ) 鄰接矩陣和鄰接表兩種圖的存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍 深度優(yōu)先搜索和廣度優(yōu)先搜索兩種遍歷算法的特點(diǎn)和執(zhí)行過(guò)程 生成樹(shù)和最小生成樹(shù)的概念及構(gòu)造最小生成樹(shù)的prim和kruskal算法 最短路徑的含義及求最短路徑的算法 拓?fù)渑判虻幕舅枷牒筒襟E 關(guān)鍵路徑法及其在管理科學(xué)中的作用,第六章 圖,難 點(diǎn) 圖的遍歷、最小生成樹(shù)、最短路徑、拓樸排序算法的理解 關(guān)鍵路徑法求關(guān)鍵活動(dòng)和關(guān)鍵路徑的方法 要 求 熟練掌握以下內(nèi)容： 圖的存儲(chǔ)結(jié)構(gòu) 圖的遍歷算法 了解以下內(nèi)容： 圖的最小生成樹(shù)和求最小生成樹(shù)算法的基本思想 帶權(quán)有向圖的

2、最短路徑問(wèn)題 利用AOV網(wǎng)絡(luò)的拓樸排序問(wèn)題 利用AOE網(wǎng)絡(luò)的關(guān)鍵路徑法,第六章 圖,第六章目錄,7.1 圖的定義和基本術(shù)語(yǔ) 7.2 圖的存儲(chǔ)方式 7.3 圖的遍歷 7.4 最小生成樹(shù) 7.5 最短路徑 7.6 拓?fù)渑判?7.7 關(guān)鍵路徑法 7.8 應(yīng)用實(shí)例與分析 小 結(jié) 習(xí)題與練習(xí),第六章 圖,7.1 圖的定義和基本術(shù)語(yǔ),圖：圖G由V（G）和E（G）這兩個(gè)集合所組成，記為G=（V，E），其中V（G）是頂點(diǎn)（Vertex）的非空集，每個(gè)頂點(diǎn)可以標(biāo)以不同的字符或數(shù)字；E（G）是邊（Edge）的集合，特殊情況下E（G）可以是空集。每個(gè)邊由其所連接的兩個(gè)頂點(diǎn)表示。 無(wú)向圖：對(duì)于一個(gè)圖G，若邊集合E（G

3、）為無(wú)向邊的集合，則稱(chēng)該圖為無(wú)向圖。 有向圖：對(duì)于一個(gè)圖G，若邊集合E（G）為有向邊的集合，則稱(chēng)該圖為有向圖。,第六章 圖,圖7.1 有向圖與無(wú)向圖,無(wú)向圖G1,有向圖G2,第六章 圖,完全圖：在一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖中，若每個(gè)頂點(diǎn)到其它（n-1）個(gè)頂點(diǎn)都連有一條邊，則圖中共有n(n-1)/2條邊，這種圖稱(chēng)為完全圖（Complete graph，也稱(chēng)完備圖）。,左圖所示就是n=4的完全圖，它一共有六條邊。,第六章 圖,權(quán)和網(wǎng)絡(luò)：有些圖， 對(duì)應(yīng)每條邊有一相應(yīng)的數(shù)值，這個(gè)數(shù)值叫做該邊的權(quán)(Weight)。邊上帶權(quán)的圖稱(chēng)為帶權(quán)圖，也稱(chēng)為網(wǎng)絡(luò)(Network)。 子圖：設(shè)有兩個(gè)圖G =(V,E)和G=

4、(V,E)，若V(G)是V(G)的子集，且E(G)是E(G)的子集，則稱(chēng)G是G的子圖(Subgraph)。 例如圖7.3所示的圖是圖7.1中G1的一些子圖。,第六章 圖,圖7.3 子圖,第六章 圖,頂點(diǎn)的度：圖中與每個(gè)頂點(diǎn)相連的邊數(shù)，叫該頂點(diǎn)的度(Degree)。例如圖7.1的圖G1中，頂點(diǎn)的度數(shù)為2，頂點(diǎn)的度數(shù)為3，。 入度、出度：對(duì)于有向圖，頂點(diǎn)的度分為入度和出度，入度是以該頂點(diǎn)為終點(diǎn)的入邊數(shù)目；出度是以該頂點(diǎn)為起點(diǎn)的出邊數(shù)目，該頂點(diǎn)的度等于其入度和出度之和。例如在圖7.1的圖G2中，頂點(diǎn)的入度為1，出度為2，而頂點(diǎn)的入度為1，出度為0，因?yàn)橛幸粭l邊指向它，而沒(méi)有邊從它指出去。,第六章 圖

5、,路徑：在一個(gè)圖中，若從某頂點(diǎn)Vp出發(fā)，沿一些邊經(jīng)過(guò)頂點(diǎn)V1,V2,Vm到達(dá)，Vq，則稱(chēng)頂點(diǎn)序列(Vp, V1,V2,Vm, Vq)為從Vp到Vq的路徑(Path)。 路徑長(zhǎng)度：對(duì)于無(wú)權(quán)的圖，路徑長(zhǎng)度指的是沿此路徑上邊的數(shù)目；對(duì)于有權(quán)圖，一般是取沿路徑各邊的權(quán)之和作為此路徑的長(zhǎng)度。 若一條路徑上各頂點(diǎn)均不重復(fù)，即路徑經(jīng)過(guò)每一頂點(diǎn)不超過(guò)一次，則此路徑叫做簡(jiǎn)單路徑。 如果從一個(gè)頂點(diǎn)出發(fā)又回到該頂點(diǎn)，即Vp與Vq相同，則此路徑叫做環(huán)路（Cycle）。,第六章 圖,連通、連通圖：在無(wú)向圖中，如果從頂點(diǎn)Vi到頂點(diǎn)Vj之間有路徑，則稱(chēng)這兩個(gè)頂點(diǎn)是連通的。如果圖中任意一對(duì)頂點(diǎn)都是連通的，則稱(chēng)此圖是連通圖(C

6、onnected graph)。 連通分量：例如圖7.1中的圖G1是連通圖。圖7.4中的圖就是非連通圖，非連通圖的每一個(gè)極大連通子圖叫連通分量(Connected Component)，此圖包括二個(gè)連通分量。,第六章 圖,圖7.4 非連通圖G,第六章 圖,強(qiáng)連通圖和強(qiáng)連通分量：在有向圖G中，如果從頂點(diǎn)Vi到頂點(diǎn)Vj和從頂點(diǎn)Vj到頂點(diǎn)Vi之間都有路徑，則稱(chēng)這兩個(gè)頂點(diǎn)是強(qiáng)連通的。如果圖中任何一對(duì)頂點(diǎn)都是強(qiáng)連通的，則此圖叫做強(qiáng)連通圖。非強(qiáng)連通圖的每一個(gè)極大強(qiáng)連通子圖叫做強(qiáng)連通分量。 圖7.1中的G2不是強(qiáng)連通圖，它有兩個(gè)強(qiáng)連通分量，如圖7.5所示。,第六章 圖,圖7.5 圖G2的強(qiáng)連通分量,返回,第

7、六章 圖,7.2.1 鄰接矩陣,鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。所謂兩頂點(diǎn)的相鄰關(guān)系即它們之間有邊相連。 鄰接矩陣是一個(gè)（nn）階方陣，n為圖的頂點(diǎn)數(shù)，它的每一行分別對(duì)應(yīng)圖的各個(gè)頂點(diǎn)，它的每一列也分別對(duì)應(yīng)圖的各個(gè)頂點(diǎn)。我們規(guī)定矩陣的元素為：,第六章 圖,圖7.7 無(wú)向圖的鄰接矩陣,第六章 圖,圖7.7 有向圖的鄰接矩陣,第六章 圖,無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的，如果Ai，j=1，必有Aj，i=1。這說(shuō)明，只輸入和存儲(chǔ)其上三角陣元素即可得到整個(gè)鄰接矩陣。 一般有向圖的鄰接矩陣是不對(duì)稱(chēng)的，Ai，j不一定等于A(yíng)j，i。 鄰接矩陣用二維數(shù)組即可存儲(chǔ)，定義如下： int adjmatrix = ARR

8、AYnn; 如果圖的各邊是帶權(quán)的，只需將矩陣中的各個(gè)1元素?fù)Q成相應(yīng)邊的權(quán)即可。,第六章 圖,產(chǎn)生無(wú)向圖鄰接矩陣算法,void creatgraph (int adjarray ) int i,j,v1,v2,num; scanf (“%d”, /*矩陣初始化*/ do ,第六章 圖,產(chǎn)生無(wú)向圖鄰接矩陣算法續(xù),scanf (“%d,%d”, ,第六章 圖,7.2.2 鄰接表,鄰接表是圖的一種鏈接存儲(chǔ)結(jié)構(gòu)。 在鄰接表結(jié)構(gòu)中，對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于該頂點(diǎn)Vi的邊，即對(duì)于無(wú)向圖每個(gè)結(jié)點(diǎn)表示與該頂點(diǎn)相鄰接的一個(gè)頂點(diǎn)；對(duì)于有向圖則表示以該頂點(diǎn)為起點(diǎn)的一條邊的終點(diǎn)。 一

9、個(gè)圖的鄰接矩陣表示是唯一的，但其鄰接表表示是不唯一的。因?yàn)樵卩徑颖淼拿總€(gè)單鏈表中，各結(jié)點(diǎn)的順序是任意的。,第六章 圖,圖7.8 鄰接表,圖7.7中無(wú)向圖對(duì)應(yīng)的鄰接表,第六章 圖,圖7.7中有向圖對(duì)應(yīng)的鄰接表,第六章 圖,鄰接表中每個(gè)表結(jié)點(diǎn)均由兩個(gè)域組成，其一是鄰接點(diǎn)域（adjvex），用以存放與頂點(diǎn)Vi相鄰接的頂點(diǎn)在圖中的位置；其二是鏈域（next），用以指向依附于頂點(diǎn)Vi的下一條邊所對(duì)應(yīng)的結(jié)點(diǎn)。 如果用鄰接表存放網(wǎng)絡(luò)中的信息，則還需要在結(jié)點(diǎn)中增加一個(gè)存放權(quán)值的域。 在每個(gè)鏈表設(shè)一表頭結(jié)點(diǎn)，一般這些表頭結(jié)點(diǎn)本身以向量的形式存儲(chǔ)。,第六章 圖,對(duì)于無(wú)向圖的鄰接表來(lái)說(shuō)，一條邊對(duì)應(yīng)兩個(gè)單鏈表結(jié)點(diǎn)，鄰

10、接表結(jié)點(diǎn)總數(shù)是邊數(shù)的2倍。 在無(wú)向圖的鄰接表中，各頂點(diǎn)對(duì)應(yīng)的單鏈表的結(jié)點(diǎn)數(shù)（不算表頭結(jié)點(diǎn)）就等于該頂點(diǎn)的度數(shù)。 在有向圖鄰接表中，一條弧對(duì)應(yīng)一個(gè)表結(jié)點(diǎn)，表結(jié)點(diǎn)的數(shù)目和弧的數(shù)目相同。 在有向圖鄰接表中，單鏈表的結(jié)點(diǎn)數(shù)就等于相應(yīng)頂點(diǎn)的出度數(shù)。 要求有向圖中某頂點(diǎn)的入度數(shù)，需掃視鄰接表的所有單鏈表，統(tǒng)計(jì)與頂點(diǎn)標(biāo)號(hào)相應(yīng)的結(jié)點(diǎn)個(gè)數(shù)。,第六章 圖,鄰接表存儲(chǔ)結(jié)構(gòu)定義,#define MAXVEX 30 struct edgenode int adjvex ; /*鄰接點(diǎn)域*/ struct edgenode *next ; /*鏈域*/ ; struct vexnode char data; /*頂點(diǎn)信息

11、*/ struct edgenode *link; ; typedef struct vexnode adjlistMAXVEX;,第六章 圖,產(chǎn)生無(wú)向圖的鄰接表算法,void creategraph (adjlist g) int e,i,s,d,n; struct edgenode *p; printf(“請(qǐng)輸入結(jié)點(diǎn)數(shù)(n)和邊數(shù)(e):n”); scanf(“%d,%d”,i+),第六章 圖,產(chǎn)生無(wú)向圖的鄰接表算法續(xù), printf(“n請(qǐng)輸入第%d條邊起點(diǎn)序號(hào)，終點(diǎn)序號(hào)：”,i); scanf(“%d,%d”, /*將新結(jié)點(diǎn)插入頂點(diǎn)Vd邊表的頭部*/ ,返回,第六章 圖,7.3.1 深

12、度優(yōu)先搜索(DFS),首先訪(fǎng)問(wèn)圖中某指定起始點(diǎn)Vi ，然后由Vi出發(fā)訪(fǎng)問(wèn)它的任一相鄰接頂點(diǎn)Vj，再?gòu)腣j出發(fā)訪(fǎng)問(wèn)Vj的任一未訪(fǎng)問(wèn)過(guò)的相鄰接頂點(diǎn)Vk，再?gòu)腣k出發(fā)進(jìn)行類(lèi)似訪(fǎng)問(wèn)，如此進(jìn)行下去，直到某頂點(diǎn)已沒(méi)有未被訪(fǎng)問(wèn)過(guò)的相鄰接頂點(diǎn)時(shí)，則退回一步，退到前一個(gè)頂點(diǎn)，找前一個(gè)頂點(diǎn)的其它尚未被訪(fǎng)問(wèn)的相鄰接頂點(diǎn)。 如有未訪(fǎng)問(wèn)過(guò)的相鄰接頂點(diǎn)，則訪(fǎng)問(wèn)此頂點(diǎn)后，再?gòu)脑擁旤c(diǎn)出發(fā)向前進(jìn)行與前述類(lèi)似的訪(fǎng)問(wèn)； 如退回一步后，前一頂點(diǎn)也沒(méi)有未被訪(fǎng)問(wèn)過(guò)的相鄰接頂點(diǎn)，則再向回退一步進(jìn)行搜索，重復(fù)上述過(guò)程，一直到所有頂點(diǎn)均被訪(fǎng)問(wèn)過(guò)為止。,第六章 圖,圖7.9 圖的遍歷例子,第六章 圖,由于圖中的路徑可能有環(huán)路，為了避免重復(fù)訪(fǎng)問(wèn)某

13、些頂點(diǎn)，設(shè)計(jì)圖的搜索算法時(shí)，可設(shè)置一個(gè)表示頂點(diǎn)是否被訪(fǎng)問(wèn)過(guò)的輔助數(shù)組visited，初始時(shí)將數(shù)組元素置零，一旦某頂點(diǎn)Vi被訪(fǎng)問(wèn)過(guò)，則令visitedVi =1，以后此頂點(diǎn)即不再訪(fǎng)問(wèn)。,第六章 圖,深度優(yōu)先搜索算法,深度優(yōu)先搜索是一種遞歸的過(guò)程，可以簡(jiǎn)單地將其表示成遞歸的形式，其算法描述如下： DFS(V0) 訪(fǎng)問(wèn)V0頂點(diǎn); visitedV0=1; 對(duì)所有與V0相鄰接的頂點(diǎn)w if (visitedw=0) DFS(w); ,第六章 圖,鄰接表表示的圖的DFS算法,int visitedMAXVEX; void dfsgraph(adjlist adj, int n) int i; for(i

14、=1;i=n;i+) visitedi=0; /*給visited數(shù)組賦初值*/ for(i=1;i=n;i+) if(!visitedi) dfs(adj, i); ,第六章 圖,從Vi出發(fā)進(jìn)行DFS的遞歸算法,void dfs(adjlist adj,int v) struct edgenode *p; visitedv=1; printf(“%d”,v); p=adjvlink; while(p!=NULL) if(visitedpadjvex=0) dfs(adjlist,padjvex); /*從v未訪(fǎng)問(wèn)的鄰接點(diǎn)出發(fā)進(jìn)行DFS*/ p=pnext; ,第六章 圖,時(shí)間復(fù)雜性分析,一個(gè)

15、有n個(gè)頂點(diǎn)、e條邊的圖，在深度優(yōu)先搜索圖的過(guò)程中，找鄰接點(diǎn)所需時(shí)間為O(e)。 對(duì)輔助數(shù)組初始化時(shí)間為O(n)。 因此，當(dāng)用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，深度優(yōu)先搜索圖的時(shí)間復(fù)雜性為O(e+n)。,第六章 圖,非遞歸算法,從頂點(diǎn)Vi出發(fā)進(jìn)行深度優(yōu)先遍歷的遞歸過(guò)程也可以寫(xiě)成非遞歸的形式，此時(shí)需借助一個(gè)堆棧保存被訪(fǎng)問(wèn)過(guò)的結(jié)點(diǎn)，以便回溯時(shí)查找已被訪(fǎng)問(wèn)結(jié)點(diǎn)的未被訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)。 設(shè)堆棧由一個(gè)一維數(shù)組構(gòu)成，數(shù)組名為stack，棧頂指針為top ,假設(shè)此數(shù)組足夠大,不必考慮溢出的可能。,第六章 圖,非遞歸算法,#define MAXVEX 100 void dfs(adjlist g，int v,int n)

16、 /*從頂點(diǎn)v出發(fā)進(jìn)行深度優(yōu)先遍歷*/ struct vexnode *stackMAXVEX, *p; int visitedMAXVEX,top=0; for(i=1;i0|p!=NULL),第六章 圖,非遞歸算法續(xù), while(p!=NULL) if (visitedp-adjvex=1) p=p-next; else printf(“%d”,p-adjvex); visitedp-adjvex=1; top+; stacktop=p; p=gp-adjvex.link; ,第六章 圖,非遞歸算法續(xù),if(top0) top-; /*退棧，回溯查找已被訪(fǎng)問(wèn)結(jié)點(diǎn)的未被訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn) */

17、 p=stacktop; p =p-next; ,第六章 圖,7.3.2 廣度優(yōu)先搜索(BFS),圖的廣度優(yōu)先搜索（BFS）類(lèi)似于樹(shù)的按層次遍歷。 廣度優(yōu)先搜索的基本思想是：首先訪(fǎng)問(wèn)圖中某指定的起始點(diǎn)Vi并將其標(biāo)記為已訪(fǎng)問(wèn)過(guò)，然后由Vi出發(fā)訪(fǎng)問(wèn)與它相鄰接的所有頂點(diǎn)Vj、 Vk，并均標(biāo)記為已訪(fǎng)問(wèn)過(guò)，然后再按照Vj、Vk的次序，訪(fǎng)問(wèn)每一個(gè)頂點(diǎn)的所有未被訪(fǎng)問(wèn)過(guò)的鄰接頂點(diǎn)，并均標(biāo)記為已訪(fǎng)問(wèn)過(guò)，下一步再?gòu)倪@些頂點(diǎn)出發(fā)訪(fǎng)問(wèn)與它們相鄰接的尚未被訪(fǎng)問(wèn)的頂點(diǎn)，如此做下去，直到所有的頂點(diǎn)均被訪(fǎng)問(wèn)過(guò)為止。,第六章 圖,在廣度優(yōu)先搜索中，若對(duì)頂點(diǎn)V1的訪(fǎng)問(wèn)先于頂點(diǎn)V2的訪(fǎng)問(wèn)，則對(duì)V1鄰接頂點(diǎn)的訪(fǎng)問(wèn)也先于V2鄰接頂點(diǎn)的

18、訪(fǎng)問(wèn)。就是說(shuō)廣度優(yōu)先搜索中對(duì)鄰接點(diǎn)的尋找具有“先進(jìn)先出”的特性。因此，為了保證訪(fǎng)問(wèn)頂點(diǎn)的這種先后關(guān)系，需借助一個(gè)隊(duì)列暫存那些剛訪(fǎng)問(wèn)過(guò)的頂點(diǎn)。 設(shè)此隊(duì)列由一個(gè)一維數(shù)組構(gòu)成，數(shù)組名為Queue，隊(duì)首指針和隊(duì)尾指針?lè)謩e為front和rear。假設(shè)數(shù)組足夠大，不必考慮有溢出的可能性。 廣度優(yōu)先搜索不是遞歸過(guò)程，不能用遞歸形式。,第六章 圖,BFS算法描述,BFS(v0) 訪(fǎng)問(wèn)v0頂點(diǎn)； visitedv0=1; 被訪(fǎng)問(wèn)過(guò)的頂點(diǎn)入隊(duì)； 當(dāng)隊(duì)列非空時(shí)，進(jìn)行下面的循環(huán) （1）被訪(fǎng)問(wèn)過(guò)的頂點(diǎn)出隊(duì)； （2）對(duì)所有與該頂點(diǎn)相鄰接的頂點(diǎn)w if (visitedw=0) (a)訪(fǎng)問(wèn)w頂點(diǎn)； (b)visitedw=

19、1; (c)w入隊(duì); ,第六章 圖,鄰接表表示的圖的BFS算法,int visitedMAXVEX; int queueMAXVEX; void bfs(adjlist adj,int v) int front=0,rear=1,v; struct edgenode *p; visitedv=1; printf(“%d”,v); queuerear=v; /*初始頂點(diǎn)入隊(duì)*/ while(front!=rear) /*隊(duì)列不為空*/,第六章 圖,鄰接表表示的圖的BFS算法續(xù), front=front+1; v=queuefront; /*按訪(fǎng)問(wèn)次序出隊(duì)列*/ p=adjv-link; /*找v

20、的鄰接頂點(diǎn)*/ while(p!=NULL) if (visitedp-adjvex=0) visitedp-adjvex=1; printf(“%d”,p-adjvex);,第六章 圖,鄰接表表示的圖的BFS算法續(xù),rear=rear+1; queuerear=p-adjvex; p=p-next; ,第六章 圖,時(shí)間復(fù)雜性分析,一個(gè)有n個(gè)頂點(diǎn)、e條邊的圖，在廣度優(yōu)先搜索圖的過(guò)程中，每個(gè)頂點(diǎn)至多進(jìn)一次隊(duì)列，圖的搜索過(guò)程實(shí)質(zhì)上是通過(guò)邊來(lái)找頂點(diǎn)的過(guò)程，找鄰接點(diǎn)所需時(shí)間為O(e)。 對(duì)輔助數(shù)組初始化時(shí)間為O(n)。 因此，當(dāng)用鄰接表作為圖的存儲(chǔ)結(jié)構(gòu)時(shí)，廣度優(yōu)先搜索圖的時(shí)間復(fù)雜性為O(e+n)。,返

21、回,第六章 圖,7.4 最小生成樹(shù),在一個(gè)無(wú)向連通圖G中，如果取它的全部頂點(diǎn)和一部分邊構(gòu)成一個(gè)子圖G，若邊集E(G)中的邊剛好將圖的所有頂點(diǎn)連通但又不形成環(huán)路，我們就稱(chēng)子圖G是原圖G的生成樹(shù)（Spanning tree）。 生成樹(shù)有如下特點(diǎn)：任意兩個(gè)頂點(diǎn)之間有且僅有一條路徑；如果再增加一條邊就會(huì)出現(xiàn)環(huán)路；如果去掉一條邊此子圖就會(huì)變成非連通圖。 一個(gè)有n 個(gè)頂點(diǎn)的完全圖，一共存在n(n-2)種不同的生成樹(shù)。,第六章 圖,對(duì)于帶權(quán)的連通圖（連通網(wǎng)）G，其生成樹(shù)也是帶權(quán)的。我們把生成樹(shù)各邊的權(quán)值總和稱(chēng)為該生成樹(shù)的權(quán)。并且將權(quán)最小的生成樹(shù)稱(chēng)為最小生成樹(shù)（Minimum Spanning Tree）。

22、具有n個(gè)頂點(diǎn)的連通圖的生成樹(shù)具有n-1條邊（少于此邊數(shù)不可能將各頂點(diǎn)連通，多于此邊數(shù)則必然要出現(xiàn)環(huán)路） 。,第六章 圖,圖7.10 圖G 及其生成樹(shù),無(wú)向連通圖 G,生成樹(shù),第六章 圖,圖7.10 圖G 及其生成樹(shù),生成樹(shù),最小生成樹(shù),第六章 圖,7.4.1 普里姆(prim)算法,假設(shè)G=(V,E)是一個(gè)具有n 個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)，T=(U,TE)是G的最小生成樹(shù)，其中U是T的頂點(diǎn)集，TE是T的邊集，U和TE的初值均為空。 算法開(kāi)始時(shí)，首先從V中任取一個(gè)頂點(diǎn)（假定為V1），將此頂點(diǎn)并入U(xiǎn)中，此時(shí)最小生成樹(shù)頂點(diǎn)集U=V1； 然后從那些其一個(gè)端點(diǎn)已在U中，另一個(gè)端點(diǎn)仍在U外的所有邊中，找一條最短（

23、即權(quán)值最?。┑倪叄俣ㄔ撨厼?Vi,Vj),其中ViU，VjV-U,并把該邊(Vi,Vj)和頂點(diǎn)Vj分別并入T的邊集TE和頂點(diǎn)集U；,第六章 圖,如此進(jìn)行下去，每次往生成樹(shù)里并入一個(gè)頂點(diǎn)和一條邊，直到n-1次后，把所有n 個(gè)頂點(diǎn)都并入生成樹(shù)T的頂點(diǎn)集U中，此時(shí)U=V，TE中包含有（n-1）條邊； 這樣，T就是最后得到的最小生成樹(shù)。 普里姆算法中每次選取的邊兩端，總是一個(gè)已連通頂點(diǎn)（在U集合內(nèi)）和一個(gè)未連通頂點(diǎn)（在U集合外），故這個(gè)邊選取后一定能將未連通頂點(diǎn)連通而又保證不會(huì)形成環(huán)路。,第六章 圖,圖7.11 普里姆算法例子,第六章 圖,為了便于在頂點(diǎn)集合U和V-U之間選擇權(quán)最小的邊，建立兩個(gè)數(shù)組

24、closest和lowcost,closesti表示U中的一個(gè)頂點(diǎn)，該頂點(diǎn)與V-U中的一個(gè)頂點(diǎn)構(gòu)成的邊具有最小的權(quán)；lowcost表示該邊對(duì)應(yīng)的權(quán)值。 開(kāi)始，由于U的初值為1，所以，closesti的值為1，i=2,n,而lowcosti為V1到各頂點(diǎn)的邊中最小的權(quán)值。,第六章 圖,普里姆算法,void prim(int cMAXVEX, int n) /*c表示圖的鄰接矩陣，圖的頂點(diǎn)為1,2n*/ int lowcostn,closestn; int i,j k,min; for(i=2,i=n;i+) /*從頂點(diǎn)V1開(kāi)始*/ lowcosti=c1i; closesti=1; for(i=

25、2;i=n;i+) /* 從U之外求離U中某頂點(diǎn)最近的頂點(diǎn)*/,第六章 圖,普里姆算法續(xù), min=lowcosti; k=i; for(j=2;j=n;j+) if (lowcostjmin) min=lowcostj; k=j; printf(“(%d,%d)”,k,closestj); /* 打印生成樹(shù)的一條邊*/,第六章 圖,普里姆算法續(xù),lowcostk=32777; /* k加入 到U中 */ for(j=2;j=n;j+) if (ckjlowcostj ,第六章 圖,算法分析,該算法中每一步執(zhí)行都要掃描數(shù)組lowcost，在V-U頂點(diǎn)集中找出與U最近的頂點(diǎn)，令其為k，并打印邊（

26、k,closestk）。 然后將k加入U(xiǎn)頂點(diǎn)集合中，并修改數(shù)組lowcost和closest。 這里用c表示圖的鄰接矩陣，cij和cji是邊(i,j)的權(quán)。,第六章 圖,7.4.2 克魯斯卡爾（Kruskal）算法,假設(shè)G =（V，E）是一個(gè)具有n個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)，T=(U,TE)是G 的最小生成樹(shù)，U的初值等于V，即包含有G中的全部頂點(diǎn)，TE的初值為空集。 基本思想：將圖G中的邊按權(quán)值從小到大的順序依次選取，若選取的邊使生成樹(shù)T不形成環(huán)路，則把它并入TE中，保留作為生成樹(shù)T的一條邊，若選取的邊使生成樹(shù)T形成環(huán)路，則將其舍棄，如此進(jìn)行下去，直到TE中包含n-1條邊為止。此時(shí)的T即為最小生成樹(shù)。

27、,第六章 圖,現(xiàn)以圖7.12中(a)圖為例說(shuō)明此算法。 設(shè)此圖是用邊集數(shù)組表示的，邊集數(shù)組是一個(gè)結(jié)構(gòu)數(shù)組，數(shù)組中的每個(gè)元素表示一條邊，組成每條邊的是三元組序列（邊的起始頂點(diǎn)、邊的終止頂點(diǎn)、邊的權(quán)值）。 將每條邊的數(shù)據(jù)輸入之后，按權(quán)值的大小進(jìn)行了排序，如圖7.12(b) 所示。這樣，按權(quán)值由小到大選取各邊就是在數(shù)組中按下標(biāo)由1到e(圖中邊的數(shù)目)的次序選取。,第六章 圖,圖7.12 克魯斯卡爾算法例子,(a)帶權(quán)圖,第六章 圖,(b)邊集數(shù)組,第六章 圖,(c)最小生成樹(shù),第六章 圖,在選取某邊時(shí)如何判斷是否與已保留的邊形成環(huán)路？克魯斯卡爾算法是通過(guò)將各頂點(diǎn)劃分為集合的辦法來(lái)解決的。 開(kāi)始時(shí)假定

28、n 個(gè)頂點(diǎn)分屬于n 個(gè)集合，即每個(gè)集合中有一個(gè)頂點(diǎn)，當(dāng)確定某條邊保留作為生成樹(shù)的一條邊時(shí)，就將該邊兩端點(diǎn)所屬的兩集合合并為一個(gè)，表示原來(lái)屬于兩個(gè)集合的各個(gè)頂點(diǎn)已被這條新的邊連通。如果取到某條邊，發(fā)現(xiàn)它的兩個(gè)端點(diǎn)已屬于同一集合時(shí)，此邊則應(yīng)當(dāng)舍去。因?yàn)閮蓚€(gè)頂點(diǎn)屬于同一集合說(shuō)明它們已連通，若再添上這條邊就會(huì)出現(xiàn)環(huán)路。,第六章 圖,如此進(jìn)行下去，到所有的頂點(diǎn)均已屬于一個(gè)集合時(shí)，此最小生成樹(shù)就構(gòu)成了。 用一個(gè)set 數(shù)組來(lái)表示頂點(diǎn)，set的初值為si=0(i=1,2,n),表示各頂點(diǎn)自成一個(gè)分量。當(dāng)從邊集數(shù)組中按次序選取一條邊時(shí)，查找它的兩個(gè)頂點(diǎn)所屬的分量，當(dāng)這兩個(gè)分量不相等，則表明所選的這條邊的兩個(gè)頂

29、點(diǎn)分屬不同的集合，該邊加入到生成樹(shù)中不會(huì)形成環(huán)路，應(yīng)作為生成樹(shù)的一條邊，同時(shí)合并這兩個(gè)分量為一個(gè)連通分量。若這兩個(gè)分量相等，則表明這條邊的兩個(gè)頂點(diǎn)同屬一個(gè)集合，將此邊加入到生成樹(shù)必產(chǎn)生環(huán)路，應(yīng)予放棄。,第六章 圖,利用克魯斯卡爾構(gòu)造最小生成樹(shù)的邊集數(shù)組結(jié)構(gòu)定義如下： # define MAXE 100 struct edges /* 邊集類(lèi)型，存儲(chǔ)一邊條的起始頂點(diǎn)為bv,終止頂點(diǎn)為tv和權(quán)w */ int bv,tv,w; typedef struct edges edgesetMAXE;,第六章 圖,查找一個(gè)頂點(diǎn)所屬的分量函數(shù)如下： int seeks(int set,int v) int

30、i=v; while(seti0) i=seti; return(i); ,第六章 圖,克魯斯卡爾算法,void kruskal (edgeset ge, int n, int e) /* ge為權(quán)按從小到大排序的邊集數(shù)組 */ int setMAXE, v1, v2, i, j; for (i=1;i=n;i+) seti=0; /*給set中每個(gè)元素賦初值*/ i=1; /* i表示獲取的生成樹(shù)中的邊數(shù)，初值為1*/ j=1; /* j表示ge中的下標(biāo)，初始值為1*/ while (jn ,第六章 圖,克魯斯卡爾算法續(xù),v2=seeks(set,gei.tv); if (v1!=v2) /

31、* 當(dāng) v1,v2不在同一集合，該邊加入生成樹(shù)*/ printf(“(%d,%d)”,gei.bv,gei.tv); setv1=v2; j+; i+; ,返回,第六章 圖,7.5 最短路徑,所謂最短路徑（shortest path）問(wèn)題指的是：如果從圖中某頂點(diǎn)出發(fā)（此點(diǎn)稱(chēng)為源點(diǎn)），經(jīng)圖的邊到達(dá)另一頂點(diǎn)（稱(chēng)為終點(diǎn)）的路徑不止一條，如何找到一條路徑使沿此路徑上各邊的權(quán)值之和為最小。 設(shè)一有向網(wǎng)絡(luò)G =（V,E），已知各邊的權(quán)值，并設(shè)每邊的權(quán)均大于零，以某指定V0為源點(diǎn)，求從V0到圖的其余各點(diǎn)的最短路徑。 以圖 7.13為例，若指定以頂點(diǎn)V7為源點(diǎn)V0，該圖比較簡(jiǎn)單，通過(guò)觀(guān)察可得到從V7到其余各點(diǎn)

32、的最短路徑。,第六章 圖,圖7.13 最短路徑例子,第六章 圖,狄克斯特拉算法,狄克斯特拉于1959年提出了一個(gè)按路徑“長(zhǎng)度”遞增的次序，逐步得到由給定源點(diǎn)到圖的其余各點(diǎn)間的最短路徑的算法。 假設(shè)我們以鄰接矩陣cost表示所研究的有向圖，costij表示有向邊對(duì)應(yīng)權(quán)值，如果兩點(diǎn)之間無(wú)相應(yīng)方向的邊，則該元素取為無(wú)窮大。在計(jì)算機(jī)中此矩陣用一個(gè)（nn）二維數(shù)組表示（n為圖的頂點(diǎn)數(shù)），無(wú)窮大元素則可用某很大的有限值（如32777）代替。,第六章 圖,圖7.13對(duì)應(yīng)的鄰接矩陣,第六章 圖,狄克斯特拉算法需要一個(gè)頂點(diǎn)集合，初始時(shí)集合內(nèi)只有一個(gè)源點(diǎn)V0 ，以后陸續(xù)將已求得最短路徑的頂點(diǎn)加入到集合中，到全部頂

33、點(diǎn)都進(jìn)入集合了，過(guò)程就結(jié)束了。 集合可用一維數(shù)組來(lái)表示，設(shè)此數(shù)組為S，凡在集合S以外的頂點(diǎn)，其相應(yīng)的數(shù)組元素Si為0，否則為1。 還需要另一個(gè)一維數(shù)組dist，每個(gè)頂點(diǎn)對(duì)應(yīng)數(shù)組的一個(gè)單元，記錄從源點(diǎn)到其他各頂點(diǎn)當(dāng)前的最短路徑長(zhǎng)度，其初值為disti=costV0i，i=2n。數(shù)組dist中的數(shù)據(jù)隨著算法的逐步進(jìn)行要不斷地修改。,第六章 圖,定義了S集合和dist數(shù)組并對(duì)其初始化后，狄克斯特拉算法在進(jìn)行中，都是從S之外的頂點(diǎn)集合中選出一個(gè)頂點(diǎn)w，使distw的值最小。于是從源點(diǎn)到達(dá)w只通過(guò)S中的頂點(diǎn)，把w加入集合S中，并調(diào)整dist中記錄的從源點(diǎn)到集合中每個(gè)頂點(diǎn)v的距離：從原來(lái)的distv和di

34、stw+costwv中，選擇較小的值作為新的distv。 重復(fù)上述過(guò)程，直到S中包含V中其余各頂點(diǎn)的最短路徑。,第六章 圖,狄克斯特拉算法,#define MAXVEX 100 /* 定義最多頂點(diǎn)數(shù) */ void shortpath ( int costMAXVEXMAXVEX, distMAXVEX, n, v0) int sMAXVEX, u, vnum, w, wm; for(w=1;w=n;w+) /*最短路徑初始化*/ distw=costv0w; for(w=1;w=n;w+) sw=0; sv0=1; /*S中頂點(diǎn)個(gè)數(shù)的初值*/ vnum=1;,第六章 圖,狄克斯特拉算法續(xù),w

35、hile(vnumn-1) /*最后一個(gè)頂點(diǎn)已無(wú)選擇余地*/ wm=32777; u=v0; for(w=1;w=n;w+) if (sw=0 ,第六章 圖,狄克斯特拉算法續(xù),for(w=1;w=n;w+) if (sw=0 /* 輸出結(jié)果 */,第六章 圖,狄克斯特拉算法例子,以圖7.13所示的圖為例來(lái)說(shuō)明當(dāng)指定以V7為源點(diǎn)V0后，用狄克斯特拉算法求最短路徑的動(dòng)態(tài)執(zhí)行情況，其表示集合的數(shù)組S和表示距離的數(shù)組dist元素值的變化如圖7.14所示。,第六章 圖,圖7.14 算法動(dòng)態(tài)執(zhí)行情況,第六章 圖,返回,第六章 圖,7.7 拓?fù)渑判?在工程實(shí)踐中，一個(gè)工程項(xiàng)目往往由若干個(gè)子項(xiàng)目組成，這些子項(xiàng)

36、目間往往有多種關(guān)系： 先后關(guān)系，即必須在一子項(xiàng)目完成后，才能開(kāi)始實(shí)施另一個(gè)子項(xiàng)目； 子項(xiàng)目之間無(wú)次序要求，即兩個(gè)子項(xiàng)目可以同時(shí)進(jìn)行，互不影響。 在工廠(chǎng)中，一件設(shè)備的生產(chǎn)包括許多工序，各工序之間也存在這兩種關(guān)系。 學(xué)校里某個(gè)專(zhuān)業(yè)的課程學(xué)習(xí)，有些課程是基礎(chǔ)課，它們可以獨(dú)立于其它課程，即無(wú)前導(dǎo)課程；有些課程必須在一些課程學(xué)完后才能開(kāi)始學(xué)。,第六章 圖,這些類(lèi)似的問(wèn)題都可以用有向圖來(lái)表示，我們把這些子項(xiàng)目、工序、課程看成一個(gè)個(gè)頂點(diǎn)稱(chēng)之為活動(dòng)(Activity)。 如果從頂點(diǎn)Vi到Vj之間存在有向邊,則表示活動(dòng)i必須先于活動(dòng)j進(jìn)行。這種圖稱(chēng)做頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(Activity On Vertex ne

37、twork,簡(jiǎn)稱(chēng)AOV網(wǎng)絡(luò))。 例如圖7.15是某校計(jì)算機(jī)專(zhuān)業(yè)的課程及其相互之間的關(guān)系，它對(duì)應(yīng)的AOV網(wǎng)絡(luò)如圖7.17所示。,第六章 圖,圖7.15 某專(zhuān)業(yè)課程設(shè)置,第六章 圖,圖7.17 AOV網(wǎng)絡(luò),第六章 圖,在A(yíng)OV網(wǎng)絡(luò)中，如果頂點(diǎn)Vi的活動(dòng)必須在頂點(diǎn)Vj的活動(dòng)以前進(jìn)行，則稱(chēng)Vi為Vj的前趨頂點(diǎn)，而稱(chēng)Vj為Vi的后繼頂點(diǎn)。這種前趨后繼關(guān)系有傳遞性。 AOV網(wǎng)絡(luò)中一定不能有有向環(huán)路。例如在圖7.17那樣的有向環(huán)路中，V2是V3的前趨頂點(diǎn)，V1是V2的前趨頂點(diǎn)，V3又是V1的前趨頂點(diǎn)，環(huán)路表示頂點(diǎn)之間的先后關(guān)系進(jìn)入了死循環(huán)。 因此，對(duì)給定的AOV網(wǎng)絡(luò)首先要判定網(wǎng)絡(luò)中是否存在環(huán)路，只有有向無(wú)環(huán)

38、路網(wǎng)絡(luò)在應(yīng)用中才有實(shí)際意義。,第六章 圖,圖7.17 有向環(huán)路,第六章 圖,拓?fù)渑判?所謂“拓?fù)渑判颉本褪菍OV網(wǎng)絡(luò)中的各個(gè)頂點(diǎn)(各個(gè)活動(dòng))排列成一個(gè)線(xiàn)性有序序列，使得所有要求的前趨、后繼關(guān)系都能得到滿(mǎn)足。 由于A(yíng)OV網(wǎng)絡(luò)中有些頂點(diǎn)之間沒(méi)有次序要求，它們?cè)谕負(fù)溆行蛐蛄兄械奈恢每梢匀我忸嵉?，所以拓?fù)渑判虻慕Y(jié)果一般并不是唯一的。 通過(guò)拓?fù)渑判蜻€可以判斷出此AOV網(wǎng)絡(luò)是否包含有有向環(huán)路，若有向圖G所有頂點(diǎn)都在拓?fù)渑判蛐蛄兄?，則AOV網(wǎng)絡(luò)必定不包含有有向環(huán)路。,第六章 圖,拓?fù)渑判蚍椒?(1) 在網(wǎng)絡(luò)中選擇一個(gè)沒(méi)有前趨的頂點(diǎn)，并把它輸出； (2) 從網(wǎng)絡(luò)中刪去該頂點(diǎn)和從該頂點(diǎn)發(fā)出的所有有向邊； (3

39、) 重復(fù)執(zhí)行上述兩步，直到網(wǎng)中所有的頂點(diǎn)都被輸出 (此時(shí)，原AOV網(wǎng)絡(luò)中的所有頂點(diǎn)和邊就都被刪除掉了)。 如果進(jìn)行到某一步，無(wú)法找到無(wú)前趨的頂點(diǎn)，則說(shuō)明此AOV網(wǎng)絡(luò)中存在有向環(huán)路，遇到這種情況，拓?fù)渑判蚓蜔o(wú)法進(jìn)行了。,第六章 圖,圖7.18 拓?fù)渑判蜻^(guò)程,AOV網(wǎng)絡(luò),輸出V3后,第六章 圖,輸出V4后,輸出V2后,輸出V1后,輸出V5后,第六章 圖,為了實(shí)現(xiàn)拓?fù)渑判虻乃惴?，?duì)于給定的有向圖，假定采用鄰接表作為它的存儲(chǔ)結(jié)構(gòu)，每個(gè)頂點(diǎn)在鄰接表中對(duì)應(yīng)一個(gè)單鏈表，表示該頂點(diǎn)的各直接后繼頂點(diǎn)。 規(guī)定將每個(gè)結(jié)點(diǎn)的Data域改為int型，并將每個(gè)鏈表的表頭結(jié)點(diǎn)構(gòu)成一個(gè)順序表，各表頭結(jié)點(diǎn)的Data域存放相應(yīng)頂

40、點(diǎn)的入度值。每個(gè)頂點(diǎn)入度初值可隨鄰接表動(dòng)態(tài)生成過(guò)程中累計(jì)得到。 例如圖7.18有向圖生成的鄰接表如圖7.19所示。,第六章 圖,圖7.19 AOV網(wǎng)絡(luò)的鄰接表,第六章 圖,在拓?fù)渑判蜻^(guò)程中，凡入度為零的頂點(diǎn)即是沒(méi)有前趨的頂點(diǎn)，可將其取出列入有序序列中，同時(shí)將該頂點(diǎn)從圖中刪除掉不再考慮。 刪去一個(gè)頂點(diǎn)時(shí)，所有它的直接后繼頂點(diǎn)入度均減1，表示相應(yīng)的有向邊也被刪除掉。 設(shè)置一個(gè)堆棧，將已檢驗(yàn)到的入度為零的頂點(diǎn)標(biāo)號(hào)進(jìn)棧，當(dāng)再出現(xiàn)新的無(wú)前趨頂點(diǎn)時(shí)，也陸續(xù)將其進(jìn)棧。每次選入度為零的頂點(diǎn)時(shí)，只要取棧頂頂點(diǎn)即可。,第六章 圖,設(shè)計(jì)算法時(shí)，可借用表頭結(jié)點(diǎn)的Data域構(gòu)成一個(gè)鏈接堆棧。用該數(shù)據(jù)域存放下一個(gè)入度為零

41、的頂點(diǎn)標(biāo)號(hào)，將堆棧中的各個(gè)單元鏈接起來(lái)，再設(shè)置一個(gè)棧頂指針top即可。 右圖為表示圖7.19的鏈接堆棧。,第六章 圖,用鄰接表存儲(chǔ)AOV網(wǎng)絡(luò)，實(shí)現(xiàn)拓?fù)渑判虻牟襟E可描述如下： (1) 把鄰接表中所有入度為零的頂點(diǎn)進(jìn)棧； (2) 在棧不空時(shí)： 退棧并輸出棧頂?shù)捻旤c(diǎn)j； 在鄰接表的第i個(gè)單鏈表中，查找頂點(diǎn)為j的所有直接后繼頂點(diǎn)k，并將頂點(diǎn)k的入度減1。若頂點(diǎn)k的入度為零，則頂點(diǎn)k進(jìn)棧； 若棧空時(shí)輸出的頂點(diǎn)個(gè)數(shù)不是n,則有向圖中有環(huán)路，否則拓?fù)渑判蛲戤叀?第六章 圖,拓?fù)渑判蛩惴?void topsort(adjlist adj, int n) /*adj為鄰接表*/ int num,i,j,top;

42、 struct vexnode *q; top=0; num=0; /*num指示輸出頂點(diǎn)個(gè)數(shù)*/ for(i=1;idata=0) adji-data=top; top=i; ,第六章 圖,拓?fù)渑判蛩惴ɡm(xù),while(top0) i=top; top=adji-data; /*在鏈表中刪除入度為0的頂點(diǎn)，頂點(diǎn)序號(hào)為i*/ q=adji-link; printf(“%d”,i); /*輸出頂點(diǎn)Vi并計(jì)數(shù)*/ num+; while(q!=NULL) j=q-adjvex; adjj-data-; /*將后繼結(jié)點(diǎn)j的入度減1*/,第六章 圖,拓?fù)渑判蛩惴ɡm(xù),if(adjj-data=0) adj

43、j-data=top; top=j; q=p-next; /*找下一個(gè)后繼結(jié)點(diǎn)*/ if(numn) printf(“網(wǎng)絡(luò)中有環(huán)路! ”n); /*因輸出的頂點(diǎn)數(shù)小于n*/ ,返回,第六章 圖,7.7 關(guān)鍵路徑法,關(guān)鍵路徑法是采用邊表示活動(dòng)(Activity On Edge)的網(wǎng)絡(luò)，簡(jiǎn)稱(chēng)為AOE網(wǎng)絡(luò)。 AOE網(wǎng)絡(luò)是一個(gè)帶權(quán)的有向無(wú)環(huán)路圖，其中，每個(gè)頂點(diǎn)代表一個(gè)事件(Event)，事件說(shuō)明某些活動(dòng)或某一項(xiàng)活動(dòng)的完成，即階段性的結(jié)果。 離開(kāi)某頂點(diǎn)的各條邊所代表的活動(dòng)，只有在該頂點(diǎn)對(duì)應(yīng)的事件出現(xiàn)后才能開(kāi)始。 權(quán)值表示活動(dòng)持續(xù)的時(shí)間。,第六章 圖,圖7.20 一個(gè)AOE網(wǎng)絡(luò),第六章 圖,AOE網(wǎng)絡(luò),通

44、常利用AOE網(wǎng)絡(luò)可以研究以下兩個(gè)問(wèn)題： (1) 完成整個(gè)工程至少需要多少時(shí)間？ (2) 哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？,第六章 圖,關(guān)鍵路徑,完成工程所需的時(shí)間就是從開(kāi)始點(diǎn)起進(jìn)行到結(jié)束點(diǎn)止所需的時(shí)間。 路徑長(zhǎng)度是指沿路徑各邊的權(quán)值之和，也就是這些邊所代表的活動(dòng)所需時(shí)間之和。 完成整個(gè)工程所需的時(shí)間取決于從開(kāi)始點(diǎn)到結(jié)束點(diǎn)的最長(zhǎng)路徑長(zhǎng)度，此長(zhǎng)度最大的路徑叫做關(guān)鍵路徑。 分析關(guān)鍵路徑的目的是辨別哪些是關(guān)鍵活動(dòng)，以便爭(zhēng)取提高關(guān)鍵活動(dòng)的效率，縮短整個(gè)工期。,第六章 圖,在描述關(guān)鍵路徑的算法時(shí)，設(shè)活動(dòng)ai由弧表示，要確定如下幾個(gè)相關(guān)的量： (1) 事件Vj的最早出現(xiàn)時(shí)間和活動(dòng)的最早開(kāi)始時(shí)間：從源點(diǎn)V1到某

45、頂點(diǎn)Vj的最長(zhǎng)路徑長(zhǎng)度叫作事件j的最早出現(xiàn)時(shí)間，表示成evj。頂點(diǎn)Vj的最早出現(xiàn)時(shí)間evj決定了從Vj指出的各條邊所代表活動(dòng)的最早開(kāi)始時(shí)間，因?yàn)槭录不出現(xiàn)，它后面的各項(xiàng)活動(dòng)就不能開(kāi)始。我們以ei表示活動(dòng)ai的最早開(kāi)始時(shí)間。顯然ei= evj 。,第六章 圖,(2) 活動(dòng)ai的最遲開(kāi)始時(shí)間：在不影響整個(gè)工程按時(shí)完成的前提下，此項(xiàng)活動(dòng)最遲的必須開(kāi)始時(shí)間，表示成Li。 只要某活動(dòng)ai有Li=ei的關(guān)系，我們就稱(chēng)ai為關(guān)鍵活動(dòng)。關(guān)鍵活動(dòng)只允許在一個(gè)確定的時(shí)間開(kāi)始，再早，它前面的事件還沒(méi)出現(xiàn)，尚不能開(kāi)始；再晚，又會(huì)延誤整個(gè)工程的按時(shí)完成。由于完成整個(gè)工程所需的時(shí)間是由關(guān)鍵路徑上各邊權(quán)值之和所決定的，顯

46、然關(guān)鍵路徑上各條邊所對(duì)應(yīng)的活動(dòng)都是關(guān)鍵活動(dòng)。,第六章 圖,(3) 事件j的最遲出現(xiàn)時(shí)間：即事件j在不延誤整個(gè)工程的前提下允許發(fā)生的最遲時(shí)間，表示為L(zhǎng)vj。對(duì)某條指向頂點(diǎn)Vj的邊所代表的活動(dòng)ai可得到： Li= Lvj-(活動(dòng)ai所需時(shí)間) 也就是活動(dòng)ai必須先于它后面事件的最遲出現(xiàn)時(shí)間開(kāi)始，提前的時(shí)間為進(jìn)行此活動(dòng)所需的時(shí)間。 圖7.21所示為活動(dòng)開(kāi)始時(shí)間與事件出現(xiàn)時(shí)間的關(guān)系。,第六章 圖,圖7.21 活動(dòng)開(kāi)始時(shí)間與事件出現(xiàn)時(shí)間的關(guān)系,第六章 圖,確定關(guān)鍵路徑的方法就是要確定ei=Li的關(guān)鍵活動(dòng)。 假設(shè)以wj,k表示有向邊的權(quán)，即此邊對(duì)應(yīng)的活動(dòng)所需的時(shí)間，為了求AOE網(wǎng)絡(luò)中活動(dòng)ai的最早開(kāi)始時(shí)間

47、ei和活動(dòng)ai的最遲開(kāi)始時(shí)間Li，先要求得頂點(diǎn)Vk的事件Vk的最早出現(xiàn)時(shí)間evk和最遲出現(xiàn)時(shí)間Lvk 。,第六章 圖,evk和Lvk可以采用下面的遞推公式計(jì)算： (1) 向匯點(diǎn)遞推 由源點(diǎn)的ev1=0開(kāi)始，利用公式： 向匯點(diǎn)的方向遞推，可逐個(gè)求出各頂點(diǎn)的ev 。式中p表示所有指向頂點(diǎn)的邊的集合，如圖7.22所示。,第六章 圖,圖7.22 集合p,此式的意義為：從指向頂點(diǎn)Vk的各邊的活動(dòng)中取最晚完成的一個(gè)活動(dòng)的完成時(shí)間作為Vk的最早出現(xiàn)時(shí)間evk。,第六章 圖,(2) 向源點(diǎn)遞推 由上一步的遞推，最后總可求出匯點(diǎn)的最早出現(xiàn)時(shí)間evn。因匯點(diǎn)就是結(jié)束點(diǎn)，最遲出現(xiàn)時(shí)間與最早出現(xiàn)時(shí)間相同，即Lvn=e

48、vn。從匯點(diǎn)的最遲出現(xiàn)時(shí)間Lvn開(kāi)始，利用下面公式： 向源點(diǎn)的方向往回遞推，可逐個(gè)求出各頂點(diǎn)的最遲出現(xiàn)時(shí)間Lv。式中s表示所有由Vj點(diǎn)指出的邊的集合，如圖7.23所示。,第六章 圖,圖7.23 集合s,此公式的意義為：由從Vj頂點(diǎn)指出的各邊所代表的活動(dòng)中取需最早開(kāi)始的一個(gè)開(kāi)始時(shí)間作為Vj的最遲出現(xiàn)時(shí)間。,第六章 圖,無(wú)論是向匯點(diǎn)遞推還是向源點(diǎn)遞推，都必須按一定的頂點(diǎn)順序進(jìn)行。 對(duì)所有的有向邊，向匯點(diǎn)遞推是先求出尾頂點(diǎn)的ev值，再求頭頂點(diǎn)的ev值；向源點(diǎn)遞推則相反，先求頭頂點(diǎn)的Lv值，再求尾頂點(diǎn)的Lv值。 為此，可利用上節(jié)介紹的拓?fù)渑判虻玫降捻旤c(diǎn)次序進(jìn)行向匯點(diǎn)的遞推，向源點(diǎn)的遞推按相反的順序進(jìn)行

49、即可，不必再重新排序。,第六章 圖,關(guān)鍵路徑算法,(1) 輸入e條有向邊，建立AOE網(wǎng)絡(luò)的存儲(chǔ)結(jié)構(gòu)； (2) 從源點(diǎn)出發(fā)，令ev1 =0，按拓?fù)渑判虻男蛄星笃溆喔黜旤c(diǎn)的最早出現(xiàn)時(shí)間evi(2in)。若拓?fù)渑判蛐蛄兄械捻旤c(diǎn)個(gè)數(shù)小于網(wǎng)絡(luò)中的頂點(diǎn)數(shù)n，則說(shuō)明網(wǎng)絡(luò)中存在環(huán)路，算法中止執(zhí)行；否則執(zhí)行(3)；,第六章 圖,(3) 從匯點(diǎn)Vn出發(fā)，令Lvn=evn，按逆拓?fù)渑判虻男蛄星笃溆喔黜旤c(diǎn)的最遲出現(xiàn)時(shí)間 Lvi(n-1i1)； (4) 根據(jù)各頂點(diǎn)的ev和Lv值求每條有向邊ai的最早開(kāi)始時(shí)間ei和最遲開(kāi)始時(shí)間Li。若某有向邊ai滿(mǎn)足ei=Li,則為關(guān)鍵活動(dòng)。 對(duì)圖7.20例子中的AOE網(wǎng)絡(luò)，各事件的最早出現(xiàn)時(shí)間和最遲出現(xiàn)時(shí)間及各活動(dòng)的最早開(kāi)始時(shí)間和最遲開(kāi)始時(shí)間計(jì)算結(jié)果如表7.1所示。,第六章 圖,表7.1 AOE網(wǎng)絡(luò)中的關(guān)鍵活動(dòng),第六章 圖,由表7.1可知時(shí)間余量為零的活動(dòng)都是關(guān)鍵活動(dòng)，即為a1，a4，a7