考研數(shù)據(jù)結(jié)構(gòu)chapt7

1、第七章 圖,圖的定義 圖的存儲結(jié)構(gòu) 圖的遍歷 圖的應(yīng)用,7.1 圖的定義和術(shù)語,1. 圖 有向圖（Digragh） 無向圖（Undigraph）,7.1 圖的定義和術(shù)語,有向圖（Digragh） G=（V，{A}） 其中，V為頂點的有窮非空集合 {A}為頂點之間的關(guān)系集合,G1=（V，{A}） V={v1, v2, v3, v4}A=

2、{, , , }其中表示從x到y(tǒng)的一條?。╝rc），A為弧集合，x為弧尾（tail），y為弧頭（head),7.1 圖的定義和術(shù)語,無向圖（Undigraph） G=(V,{E}) 其中，V同有向圖，{E}為頂點之間的關(guān)系集合， E為邊集合,G2=（V，{A}） V={v1, v2, v3, v4, v5}E={(v1, v2), (v1, v4), (v2, v3), (v3, v4), (v

3、2,v5), (v3,v5)}其中，(x, y)表示x與y之間的一條連線，稱為邊（edge）,7.1 圖的定義和術(shù)語,設(shè)n為頂點數(shù)，e為邊或弧的條數(shù) 對無向圖有：0<=e<=n(n-1)/2 有向圖有：0<=e<=n(n-1),證明：每個頂點至多有n-1條邊與其它的n-1個頂點相 連，則n個頂點至多有n(n-1)條邊。但每條邊連 接2個頂點，

4、故最多為n(n-1)/2,7.1 圖的定義和術(shù)語,2. 完全圖 邊達到最大的圖,無向完全圖：邊數(shù)為n(n-1)/2的無向圖 有向完全圖：弧數(shù)為n(n-1)的有向圖,權(quán)：與圖的邊或弧相關(guān)的數(shù)網(wǎng)：邊或弧上帶有權(quán)值的圖,7.1 圖的定義和術(shù)語,3. 頂點的度 TD（V） 無向圖：為依附于頂點V的邊數(shù) 有向圖：等于以頂點V為弧頭的弧數(shù)（稱為V的 入度，記

5、 為ID（V））與以頂點V為弧尾的弧數(shù)（稱為V 的出度，記為OD（V））之和。即： TD（V）=ID（V）+OD（V）,無向圖 n e= 1/2（∑TD(vi)） i=1,結(jié)論：,有向圖

6、 n n e= ∑ID(vi)=∑OD(vi) i=1 i=1,無向圖的度數(shù)為依附于頂點v的邊數(shù)；有向圖的度數(shù)等于以頂點v 為弧頭的弧數(shù)與以頂點v為弧尾的弧數(shù)之和,7.1 圖的定義和術(shù)語,4. 路徑 無向圖：頂點v到v’的路徑是一個頂點序列（v=

7、vi0, vi1, … , vim=v’） 其中，（vij-1,vij ）∈E, 1<=j<=m 有向圖： 頂點v 到v’的路徑是有向的頂點序列（v=vi0, vi1, … , vim=v’） 其中，（vij-1,vij ）∈A, 1<=j<=m,幾個概念：路徑長度：路徑上邊或弧的數(shù)目回路

8、或環(huán)：首尾頂點相同的路徑，稱為回路或環(huán)。即： （v=vi0, vi1, … , vim=v’=v）簡單路徑：路徑中不含相同頂點的路徑簡單回路：除首尾頂點外，路徑中不含相同頂點的回路,7.1 圖的定義和術(shù)語,5. 連通 頂點連通：若頂點v到頂點v’有路徑，則稱頂點v與v’是連通的 連 通 圖 ：包括無向連通圖和有向連通圖 無向圖：若圖中任意兩個頂點

9、vi,vj都是連通的，則稱該圖 是連通圖(vivj) 有向圖：若圖中任意兩個頂點vi,vj，都存在從vi到vj和從 vj到vi的路徑，則稱該有向圖為強連通圖(vivj) 連通分量： 無向圖：無向圖中極大連通子圖，稱為連通分量

10、 有向圖：有向圖中極大強連通子圖，稱為強連通分量,7.1 圖的定義和術(shù)語,5. 連通連通分量：,G1有兩個強連通分量,7.1 圖的定義和術(shù)語,6. 生成樹 定義：設(shè)無向圖G是含有n個頂點的連通圖， 則圖G的生成樹是 含有n個頂點，且只有n-1條邊的連通子圖 三要素： n個頂點

11、 n-1條邊 連通,極小連通子圖，若再加一條邊，必構(gòu)成環(huán),7.2 圖的存儲結(jié)構(gòu),圖有數(shù)組、鄰接表、鄰接多重表和十字鏈表等表示方法,一、數(shù)組表示法（鄰接矩陣）,設(shè)圖G=（V，{E}）有n個頂點，則G的鄰接矩陣定義為n階方陣A。其中：A[i，j]= 1 若（ vi，vj）或 ∈E，i≠j

12、 0 其它,,,,無向圖的鄰接矩陣為對稱矩陣,7.2 圖的存儲結(jié)構(gòu),特點：判定兩個頂點Vi與Vj是否關(guān)聯(lián),只需判A[i,j]是否為1 頂點的度容易求得:,7.2 圖的存儲結(jié)構(gòu),網(wǎng)的鄰接矩陣 定義為： A[i，j]= Wij，若（Vi，Vj）或∈E ，其它,如圖

13、：,7.2 圖的存儲結(jié)構(gòu),二、鄰接表（adjacency list）,1. 無向圖鄰接表,對圖中每個頂點Vi建立一個單鏈表，鏈表中的結(jié)點表示依附于頂點Vi的邊，每個鏈表結(jié)點為兩個域：,其中：鄰接點域（adjvex）記載與頂點Vi鄰接的頂點信息； 鏈域（nextarc）指向下一個與頂點Vi鄰接的鄰接的鏈表p結(jié)點,每個鏈表附設(shè)一個頭結(jié)點，頭結(jié)點結(jié)構(gòu)為：,其中：vexdata存放頂點信息（姓名、編號等）；

14、 fristarc指向鏈表的第一個結(jié)點。,7.2 圖的存儲結(jié)構(gòu),二、鄰接表（adjacency list）,如圖G2的鄰接表為：,特點：設(shè)無向圖中頂點數(shù)為n，邊數(shù)為e， 則它的鄰接表需要n個頭結(jié)點和2e個表結(jié)點。 頂點Vi的度 TD（Vi）=鏈表i中的表結(jié)點數(shù)。,7.2 圖的存儲結(jié)構(gòu),二、鄰接表（adjacency list）,2. 有向圖鄰接表,與無向圖的鄰接表結(jié)構(gòu)一

15、樣。只是在第i條鏈表上的結(jié)點是以Vi為弧尾的各個弧頭頂點,特點：1. n個頂點，e條弧的有向圖，需n個表頭結(jié)點，e 個表結(jié)點 2. 第i條鏈表上的結(jié)點數(shù)，為Vi的出度 （求頂點的出度易，求入度難）,如圖G1的鄰接表為：,7.2 圖的存儲結(jié)構(gòu),二、鄰接表（adjacency list）,3. 有向圖逆鄰接表,與無向圖的鄰接表結(jié)構(gòu)一樣。只是在第i條鏈表上的結(jié)點是以Vi為弧頭的各個弧尾頂點,此時，第i

16、條鏈表上的結(jié)點數(shù)，為Vi的入度,如圖G1的逆鄰接表為：,7.2 圖的存儲結(jié)構(gòu),三、十字鏈表（orthogonal list）,十字鏈表是將有向圖的鄰接表和逆鄰接表結(jié)合起來的一種有向圖鏈式存儲結(jié)構(gòu),1. 結(jié)點結(jié)構(gòu),有向圖的每一條弧有一個弧結(jié)點，每一個頂點必有一個頂點結(jié)點，其結(jié)構(gòu)為：,7.2 圖的存儲結(jié)構(gòu),2. 整體結(jié)構(gòu),通過hlink將弧頭相同的弧連在一個鏈表上； 通過tlink將弧尾相同的弧連在一個鏈表上 而h

17、link鏈和tlink鏈的頭結(jié)點就是頂點結(jié)點,3. 例 G1的十字鏈表為：,7.2 圖的存儲結(jié)構(gòu),4. 特點：,① 頂點結(jié)點數(shù)=頂點數(shù) 弧結(jié)點數(shù)=弧的條數(shù)② 求入度：從頂點Vi的firstin出發(fā)，沿著弧結(jié)點中的hlink所經(jīng)過的弧結(jié)點數(shù)。 求出度：從頂點Vi的firstout出發(fā)，沿著弧結(jié)點中的tlink所經(jīng)過的弧結(jié)點數(shù)。,7.2 圖的存儲結(jié)構(gòu),四、鄰接多重表,鄰接多重表是無向圖的另一種鏈式存儲結(jié)構(gòu)。,圖的每一

18、條邊有一個邊結(jié)點，邊結(jié)點的結(jié)構(gòu)為：,每一個頂點有一個頂點結(jié)點，頂點結(jié)點結(jié)構(gòu)為：,其中：ivex 和jvex為該邊所依附的兩個頂點。 ilink指向下一條依附于頂點ivex的邊。 jlink指向下一條依附于頂點jvex 的邊。 data存放頂點的信息。 firstedge指向第一條依附于該頂點的邊結(jié)點。,7.2 圖的存儲結(jié)構(gòu),四、鄰接多重表,

19、如圖G2的鄰接多重表:,7.2 圖的存儲結(jié)構(gòu),四、鄰接多重表,如圖G2的鄰接多重表:,特點：頂點結(jié)點數(shù)為n，邊結(jié)點數(shù)為e； 對需要得到邊的兩個頂點的一類操作很方便 （如刪除一條邊，判一條邊是否已訪問）。,7.3 圖的遍歷,從圖中某個頂點出發(fā)，沿路徑使圖中每個頂點被訪問且僅被訪問一次的過程，稱為遍歷圖。,兩種常用遍歷圖的方法,,深度優(yōu)先搜索,廣度優(yōu)先搜索,7.3 圖的遍歷,一、深度優(yōu)

20、先搜索（depth-first-search),1. 深度優(yōu)先搜索法遍歷圖的過程為：,訪問指定的某頂點V，將V作為當前頂點將該頂點作為當前頂點，訪問當前頂點的下一未被訪問過的鄰接點重復(fù)2，直到當前頂點的所有鄰接點都被訪問點。沿搜索路徑回退，退到尚有鄰接點未被訪問過的某結(jié)點，將該結(jié)點作為當前結(jié)點，重復(fù)以上步驟，直到所有頂點被訪問過的為止,7.3 圖的遍歷,一、深度優(yōu)先搜索（depth-first-search),如圖G4：,7

21、.3 圖的遍歷,一、深度優(yōu)先搜索（depth-first-search),2. 深度優(yōu)先搜索遞歸過程：,PROC traver(g:Graph; VAR visited:ARRAY[vtxptr] OF Boolean);FOR Vi:=1 TO vexmum DO visited[Vi]:=false;FOR Vi:=1 TO vexnum DO IF NOT visited[Vi] THEN dfs(g,Vi)

22、 {dfs是以Vi 為出發(fā)點，遍歷一個連通分量}ENDP; {traver}PROC dfs(g:Graph;V0:vtxptr); visit(V0); visited[V0]:=true; w:=FIRSTADJ(g,V0); {找V0 的第一個鄰接點} WHILE w0 DO [ IF NOT visited[w] THEN dfs(g,w); w:=NEXTADJ(g,V0,w)

23、 {找V0 的w之后的下一鄰接點} ]ENDP;{dfs},7.3 圖的遍歷,一、深度優(yōu)先搜索（depth-first-search),2. 深度優(yōu)先搜索遞歸過程：,幾點說明：,FIRSTADJ(g,V0)和NEXTADJ（g,V0,w）函數(shù)的實現(xiàn)與圖的 具體存儲結(jié)構(gòu)有關(guān),7.3 圖的遍歷,2. 深度優(yōu)先搜索遞歸過程：圖若采用鄰接表存儲,FUNC FIRSTADJ(g,vo):integer; {找與vo

24、鄰接的第一個頂點,不存在返回0} p:=adjlist[v0].firstarc; IF p=NIL THEN RETURN(0) ELSE RETURN (p↑.adjvex)ENDF;{FIRSTADJ}FUNC NEXTADJ(g,vo,w);{找V0 的w之后的下一鄰接點,不存在返回0} p:=adjlist[vo].firstarc;

25、WHILE pNIL AND p↑.adjvexw DO p:= p↑.nextarc; {將移動指針定位到w} IF p=NIL COR p↑.nextarc=NIL THEN RETURN(0) ELSE RETURN(p↑.nextarc↑.adjvex)ENDP; {NEXTADJ},7.3 圖的遍歷,2. 深度優(yōu)先搜索遞歸過程：,

26、PROC traver(g:Graph; VAR visited:ARRAY[vtxptr] OF Boolean);FOR Vi:=1 TO vexmum DO visited[Vi]:=false;FOR Vi:=1 TO vexnum DO IF NOT visited[Vi] THEN dfs(g,Vi) {dfs是以Vi 為出發(fā)點，遍歷一個連通分量}ENDP; {traver}PROC dfs(g:Gr

27、aph;V0:vtxptr); visit(V0); visited[V0]:=true; w:=FIRSTADJ(g,V0); {找V0 的第一個鄰接點} WHILE w0 DO [ IF NOT visited[w] THEN dfs(g,w); w:=NEXTADJ(g,V0,w) {找V0 的w之后的下一鄰接點} ]ENDP;{dfs},思考：traver調(diào)用 dfs的次

28、數(shù)由什么決定？圖若采用鄰接矩陣存儲,編寫相應(yīng)的FIRSTADJ(g,V0)和NEXTADJ(g,V0,w),7.3 圖的遍歷,二、廣度優(yōu)先搜索（breadth-first-search),首先訪問指定頂點v0，將v0作為當前頂點; 訪問當前頂點的所有未訪問過的鄰接點， 并依次將訪問的這些鄰接點作為當前頂點; 重復(fù)2， 直到所有頂點被訪問為止。,對右圖廣度優(yōu)先搜索，訪問頂點序列為： V1 V2 V3 V4 V

29、5 V6 V7 V8,7.3 圖的遍歷,廣度優(yōu)先搜索算法：,PROC bfs(g,vo); visit(vo); visited[vo]:=true; INIQUEUE(Q); ENQUEUE(Q,vo); WHILE NOT EMPTY(Q) DO [ v:=DLQUEUE(Q); w:=FIRSTADJ(g,v);

30、 WHILE w0 DO [IF NOT visited[w] THEN [ visit(w); visited[w]:=true; ENQUEWE(Q,w)]； w:=NEXTADJ(g,v,w) ] ]ENDP; {bfs}

31、,7.4 最小生成樹,一、最小生成樹概念1. 設(shè)無向連通圖G=（V，{E}）， 其子圖G’=（V，{T}）滿足：① V(G’)=V(G) n個頂點② G’是連通的③ G’中無回路則G’是G的生成樹,7.4 最小生成樹,具有n個頂點的無向連通圖G 其任一生成G’恰好含n-1條邊 生成樹不一定唯一，如,4個頂點選擇3條邊有如下5種形狀(5×4= 20種):其中16種為生成樹,（保證了連通

32、）,生成樹代價,對圖中每條邊賦于一個權(quán)值（代價），則構(gòu)成一個網(wǎng)，網(wǎng)的生成樹G’=(V，{T})的代價是T中各邊的權(quán)值之和，最小生成樹就是網(wǎng)上所有可能的生成樹中，代價最小的一類生成樹。最小生成樹也不一定唯一。,7.4 最小生成樹,最小生成樹的實用例子很多,例1：,N臺計算機之間建立通訊網(wǎng),,頂點表示computer,邊表示通訊線,權(quán)值表示通訊線的代價（通訊線長度，computer間距離等）,要求：,① n臺計算機中的任何兩

33、臺能通過網(wǎng)進行通訊；② 使總的代價最小。-------求最小生成樹[T],7.4 最小生成樹,最小生成樹的實用例子,7.4 最小生成樹,二、最小生成樹性質(zhì)MST,設(shè)N=（V，{E}）是一個連通網(wǎng)，U是頂點集V的一個非空子集。若（u，v）是一條具有最小權(quán)值的邊，其中u∈U,v∈V-U,即（u，v）=Min{cost(x,y)|x∈U,y∈V-U}則必存在一棵包含邊（u，v）的最小生成樹。,含義：將頂點分為兩個不相交的集合U和

34、V-U，若邊（u，v）是連接這兩個頂點集的最小權(quán)值邊，則邊（u，v）必然是某最小生成樹的邊。,三、普里姆（Prim）最小生成樹算法,設(shè) N=（V，{E}）是一個連通網(wǎng)，V=[1，2，…，n}是N的頂點集合，輔助集合U，初值為{Uo}，用來存放當前所得到的最小生成樹的頂點；輔助集合TE，初值為{}，用來存放當前所得到的最小生成樹的邊。,Prim算法步驟,1. TE=Ф,U={u0}2. 當U≠V，重復(fù)下列步驟：(1)

35、選?。╱0,v0)=min{cost(u,v)|u∈U,v∈V-U}，保證不形成回路(2)TE=TE+（u0,v0), 邊（u0,v0)并入TE(3)U=U+{V0}，頂點V0 并入U,特點: 以連通為主選代價最小的鄰接邊,Prim算法實現(xiàn):PROC minispantree_PRIM(gn: adjmatrix; u0: vtxptr); {從u0出發(fā)構(gòu)造網(wǎng) gn的最小生成樹} FOR v :=1

36、 TO vtxnum DO IF v≠ u0 THEN WITH closedge[v] DO [vex:= u0 ; lowcost:=gn[u0 , v] ]; closedge[u0 ].lowcost:=0; {輔助數(shù)組初始化} FOR i:=1 TO vtxnum-1

37、 DO [ k:=minimum(closedge); {closedge[k].lowcost=MIN( closedge[v].lowcost | v ∈V-U and closedge[v].lowcost>0)} write(closedge[k].vex, k); {輸出生成樹的邊} closedge[k].lowcost:=

38、0; {頂點k并入U} FOR v:=1 TO vtxnum DO IF gn[k, v]<closedge[v].lowcost THEN [closedge[v].lowcost:=gn[k,v]; closedge[v].v

39、ex:=k] {新頂點并入U后，重選最小代價邊} ]ENDP； {minispantree_PRIM},算法minispantree_PRIM的幾點說明:1. gn為 網(wǎng)的鄰接矩陣 即 gn[i, j]=wij 或 為無窮大2. 輔助數(shù)組closedge[1..n] 有兩個分量: closedge[k].vex存放邊(k, j)依附的另一頂點j( j∈U) c

40、losedge[k].lowcost存放邊(k, j)的權(quán)值，當值為0時，表示頂點k已加入到集合U中。 區(qū)別頂點 ∈U或∈V-U，是根據(jù)， .lowcost=0 ∈U .lowcost〉0 ∈V-U closedge[k].vex ∈U 而 k ∈V-U,算法minispantree_PRI

41、M的幾點說明:3. FUNC minimum(closedge):integer; min:=∞; h:=1; FOR k:=1 TO vtxnum DO IF closedge[k].lowcost0 AND closedge[k].lowcost<min THEN [ min:=closedge[k

42、].lowcost; h:=k] RETURN(h)ENDF； {minimum},例子：,四、克魯斯卡爾（Kruskal）最小生成樹算法,Kruskal 算法是逐步給生成樹T中添加不和T中的邊構(gòu)成回路的當前最小代價邊。特點: 以最小代價邊主。設(shè)N=（V，{E}）是個連通網(wǎng), 算法步驟為：1. 置生成樹T的初始狀態(tài)為T=（V，{Ф}）2. 當T中邊數(shù)<n-1時, 重復(fù)下列步驟: 從E

43、中選取代價最小的邊（v, u）, 并刪除之; 若（v, u）依附的頂點v和u落在T中不同的連同分量上，則將邊（v, u）并入到T的邊集中；否則，舍去該邊，選擇下一條代價最小的邊.,四、克魯斯卡爾（Kruskal）最小生成樹算法,步驟 (v, u) E T,1 (1, 3),0,1

44、,四、克魯斯卡爾（Kruskal）最小生成樹算法,步驟 (v, u) E T,3 (2, 5),2 (4, 6),⑥,四、克魯斯卡爾（Kruskal）最小生成樹算法,步驟 (v, u) E

45、 T,5 (1, 4),4 (3, 6),⑥,⑥,四、克魯斯卡爾（Kruskal）最小生成樹算法,步驟 (v, u) E T,6 (2, 3),,,,邊數(shù)=n-1=5代價=(1+2+3+4+5)=

46、15,7.5 拓撲排序(topological sort) 拓撲排序是一種對非線性結(jié)構(gòu)的有向圖進行線性化的重要手段一、AOV網(wǎng)(Activity on vertex network) 一個有向圖可用來表示一個施工流程圖、一個產(chǎn)品生產(chǎn)流程圖、或一個程序框圖等。如圖：,課程安排,施工從活動 a1、 a2開始，到達活動 a8和 a9時，整個施工結(jié)束。有向圖中，頂點表示活動，弧表示活動 ai優(yōu)先于活動 aj ，稱這類

47、有向圖為頂點表示活動的網(wǎng)（AOV網(wǎng)）。,7.5 拓撲排序(topological sort),AOV網(wǎng)可解決如下兩個問題：（1）判定工程的可行性。顯然，有回路，整個工程就無法結(jié)束（2）確定各項活動在整個工程執(zhí)行中的先后順序。 稱這種先后順序為拓撲有序序列。,如圖有如下拓撲有序序列： a1 a2 a3a4 a6 a5 a7 a8 a9

48、 a2 a6 a1 a3 a4 a5 a7 a9 a8,二、拓撲排序算法,1. 算法步驟(1) 在AOV網(wǎng)中，選取一個沒有前驅(qū)的頂點輸出；(2) 刪除該頂點和所有以它為弧尾的??；(3) 重復(fù)以上兩步，直到AOV網(wǎng)中全部頂點都已輸出（得到拓撲有序序列）或者，圖中再無沒有前驅(qū)的頂點（AOV網(wǎng)中有環(huán)）,二、拓撲排序算法,如何實現(xiàn)算法中的(1)和(2)？對于(1)，

49、沒有前驅(qū)的頂點即入度為0的頂點；對于(2)，刪除以它為弧尾的所有弧，即讓該頂點的所有直接后繼的入度減1。,由此分析知：拓撲排序算法的實現(xiàn)與頂點的入度有密切關(guān)系，因此，在選取存儲結(jié)構(gòu)時，應(yīng)考慮： 能容易得到各頂點的入度； 有利于尋找任一頂點的所有直接后繼。為此，采用鄰接表作為AOV網(wǎng)的存儲結(jié)構(gòu)，并在頭結(jié)點中增加一個存放頂點入度的域（indegree）,二、拓撲排序算法,FUNC toposort(VAR dig: adjlis

50、ttp; n, e: integer): Boolean; crt_adjlist(dig); {建鄰接表} INIT(top); FOR i:=1 TO n DO IF dig[i].indegree=0 THEN PUSH(top，i); {所有入度為0的入top棧} m:=0;{計數(shù)變量初值為0} WHILE

51、 NOT EMPTY(top) DO [ j:=POP(top); write(dig[j].vexdata); m:=m+1; q:=dig[j].firstare;{設(shè)置移動指針} WHILE q NIL DO [ k:=q↑. adjvex; dig[k]. indegree:=dig[k].indegree-1;

52、 IF dig[k].indegree=0 THEN PUSH(top, k); {入度減為0的頂點入棧} q:=q↑.nextarc ] ]; IF m<n THEN RETURN(false) ELSE RETURN(true)ENDF; {toposort},7.6 關(guān)鍵路徑,一、AOE網(wǎng)（activity on edge）

53、 若有向圖中，頂點表示事件，弧表示活動，弧上的權(quán)表示完成該活動所需的時間，則稱這類有向圖為邊表示活動的網(wǎng)（AOE網(wǎng)） AOE網(wǎng)中僅有一個入度為0的事件，稱為源點，它表示工程的開始；網(wǎng)中也僅有一個出度為0的事件，稱為匯點，它表示工程的結(jié)束。 每一事件V表示以它為弧頭的所有活動已經(jīng)完成，同時，也表示以它為弧尾的所有活動可以開始。,7.6 關(guān)鍵路徑,AOE網(wǎng)可解決如下問題

54、：估算工程的最短工期（從源點到 匯點至少需要多少時間）找出哪些活動是影響整個工程進展的關(guān)鍵,有4個事件：V1， V2， V3， V5 V1為源點，V5為匯點有4個活動：a1, a2, a4, a5 V3表示：a2已完成，a5可以開始,7.6 關(guān)鍵路徑,二、幾個術(shù)語路徑長度：路徑上各活動持續(xù)時間的總和 （即：路徑上所有弧的權(quán)

55、值之和）關(guān)鍵路徑：從源點到匯點之間路徑長度最長的路徑， （不一定唯一）事件V i的最早發(fā)生時間ve(i)：從源點到V i的最長路徑長度活動 ai的最早開始時間e(i)：等于該活動的弧尾事件V j的最早發(fā)生時間 即若表示活動ai ，則有e(i)=ve(j),ai,7.6 關(guān)鍵路徑,事件 vk 的最遲發(fā)生時間 vl(k)：是在不推遲整個工期的前提下，該事件最遲必須發(fā)

56、生的時間活動ai的最遲開始時間l(i)：是該活動的弧頭事件的最遲發(fā)生時間與該活動的持續(xù)時間之差， 即l(i)=vl(k)- ai 的持續(xù)時間關(guān)鍵活動：l(i)=e(i)的活動,由此可見：在AOE網(wǎng)中找關(guān)鍵活動問題可轉(zhuǎn)化為求 l(i)=e(i)，而e(i)=ve(j) l(i)=vl(k) - ai 的持續(xù)時間因此，需先求出事件的最早、最遲發(fā)生時間,7.6 關(guān)鍵路徑,三、關(guān)鍵路徑算法思想1. 從ve(1)=0

57、開始利用下面遞推公式，計算出各事件的最早發(fā)生時間ve(j)=Max{ve(i)+dut()}， j=2,……, n， ∈T其中：T是所有以j為頭的弧集合，dut()表示活動的持續(xù)時間前例中，ve(5)=Max{ve(2)+dut()， ve(3)+dut()} =Max{6+1,4+1}=7,2. 從vl(n)=ve(n)開始，利用下

58、面遞推公式，計算出各時間的最遲發(fā)生時間：vl(i)=Min{vl(j)-dut()} i=n-1 ,……, 2, 1 , ∈S其中：S是所有以i為尾的弧集合,7.6 關(guān)鍵路徑,前例中，vl(5)=ve(5)=7 vl(2)=vl(5)-1=6 vl(3)=vl(5)-1=6vl(1)=Min{vl(2)-dut()，vl(3)-dut()} =Min{6-6,6-4}=0,7.6

59、關(guān)鍵路徑,3. 設(shè)活動ai由弧表示，其持續(xù)時間為dut()，則利用下面公式，計算出各活動的最早、最遲開始時間：e(i)=ve(j)l(i)=vl(k)-dut()4. 找出e(i)=l(i)的活動，即為關(guān)鍵活動，諸關(guān)鍵活動組成的從源點到匯點的路徑即為關(guān)鍵路徑。,7.6 關(guān)鍵路徑,四、例子,7.6 關(guān)鍵路徑,關(guān)鍵路徑上的活動都是關(guān)鍵活動?？s短非關(guān)鍵活動都不能縮短整個工期 如a6縮短為1，則整個工期仍為8。

60、 又如a6推遲3天開始，或拖延3天完成 （a6=6）均不影響整個工期分析關(guān)鍵路徑的目的是找出影響整個工期的關(guān)鍵活動，縮短關(guān)鍵活動的持續(xù)時間，?？梢钥s短整個工期。 如a7縮短為1，則整個工期為7。 此時，再縮短任一關(guān)鍵活動均不能縮短整個工期。 即在有多條關(guān)鍵路徑時，縮短那些在所有關(guān)鍵路上的關(guān)鍵活動，才能縮短整個工期,五、關(guān)鍵路徑算法,FUNC toporder(dig: adjlisttp)

61、:Boolean; {求得各頂點事件的最早發(fā)生時間于ve[1..n], 逆拓撲有序序列于棧top2} 建立入度為0的頂點棧top1; INIT(top2); m:=0; ve[1..n]:=0; WHILE NOT EMPTY(top1) DO [ j:=POP(top1); PUSH(top2, j); m:=m+1; k:=FIRS

62、TADJ(dig, j); WHILE k0 DO [ 入度(k):=入度(k)-1; IF入度(K)=0 THEN PUSH(top1, k); IF ve[j]+dut() > ve[k ] THEN ve[k]:=ve[j]+dut();

63、 k:=NEXTADJ(dig, j, k) ] ] IF m<n THEN RETURN(false) ELSE RETURN(true)ENDF; {toporder},五、關(guān)鍵路徑算法,PROC critical_path(VAR dig: adjlisttp); crt_adjlist(dig); IF NOT topord

64、er(dig) THEN write(“有回路”) ELSE [ vl[1..n]:=ve[n]; WHILE NOT empty(top2) DO [ j:=pop(top2); k:=FIRSTADJ(dig, j); WHILE

65、 k0 DO [ IF vl[k]-dut()); k:=NEXTADJ(dig, j, k) ] ] FOR j:=1 TO n DO {求ee 和 el，及關(guān)鍵活動}

66、 [ k:=FIRSTADJ(j); WHILE k0 DO [ ee:=ve[j]; el:=vl[k]-dut(); IF ee=el THEN tag:=‘*’ ELSE tag:=‘ ’;

67、 writeln(j, k, dut(), ee, el, tag); k:=NEXTADJ(dig, j, k) ] ] ] ENDP; {critical_path},7.7 最短路徑在有向圖中，尋找從某個源點到其余各個頂點或者每一對頂點之間的最短帶權(quán)路徑的運算，稱為最短路徑問題,一、某個源點到其余各頂點的最短路徑算法迪杰特拉（Dijkstr

68、a） 算法：算法思想：按路徑長度遞增的次序產(chǎn)生到各頂點的最短路徑使用DS：利用帶權(quán)鄰接矩陣cost表示當前找到的從源點V0到每個終點Vi的最短路徑長度的輔助向量dist[i]存儲最短路徑的向量path[i]表示已找到從V0出發(fā)的最短路徑的終點的集合S,7.7 最短路徑,算法步驟：1. 用cost 初始化dist；置S={V0}；2. 選擇Vj,使得：dist[j]=Min{dist[i]|Vi∈V-S} Vj 就是當