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

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

2、{, , , }其中表示從x到y(tǒng)的一條弧（arc），A為弧集合，x為弧尾（tail），y為弧頭（head),7.1 圖的定義和術(shù)語,無向圖（Undigraph） G=(V,{E}) 其中，V同有向圖，{E}為頂點(diǎn)之間的關(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為頂點(diǎn)數(shù)，e為邊或弧的條數(shù) 對(duì)無向圖有：0<=e<=n(n-1)/2 有向圖有：0<=e<=n(n-1),證明：每個(gè)頂點(diǎn)至多有n-1條邊與其它的n-1個(gè)頂點(diǎn)相 連，則n個(gè)頂點(diǎn)至多有n(n-1)條邊。但每條邊連 接2個(gè)頂點(diǎn)，

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

5、 為ID（V））與以頂點(diǎn)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ù)為依附于頂點(diǎn)v的邊數(shù)；有向圖的度數(shù)等于以頂點(diǎn)v 為弧頭的弧數(shù)與以頂點(diǎn)v為弧尾的弧數(shù)之和,7.1 圖的定義和術(shù)語,4. 路徑 無向圖：頂點(diǎn)v到v’的路徑是一個(gè)頂點(diǎn)序列（v=

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

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

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

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

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

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

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

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

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

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

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

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

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

20、先搜索（depth-first-search),1. 深度優(yōu)先搜索法遍歷圖的過程為：,訪問指定的某頂點(diǎn)V，將V作為當(dāng)前頂點(diǎn)將該頂點(diǎn)作為當(dāng)前頂點(diǎn)，訪問當(dāng)前頂點(diǎn)的下一未被訪問過的鄰接點(diǎn)重復(fù)2，直到當(dāng)前頂點(diǎn)的所有鄰接點(diǎn)都被訪問點(diǎn)。沿搜索路徑回退，退到尚有鄰接點(diǎn)未被訪問過的某結(jié)點(diǎn)，將該結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)，重復(fù)以上步驟，直到所有頂點(diǎn)被訪問過的為止,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ā)點(diǎn)，遍歷一個(gè)連通分量}ENDP; {traver}PROC dfs(g:Graph;V0:vtxptr); visit(V0); visited[V0]:=true; w:=FIRSTADJ(g,V0); {找V0 的第一個(gè)鄰接點(diǎn)} WHILE w0 DO [ IF NOT visited[w] THEN dfs(g,w); w:=NEXTADJ(g,V0,w)

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

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

25、WHILE pNIL AND p↑.adjvexw DO p:= p↑.nextarc; {將移動(dòng)指針定位到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ā)點(diǎn)，遍歷一個(gè)連通分量}ENDP; {traver}PROC dfs(g:Gr

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

28、數(shù)由什么決定？圖若采用鄰接矩陣存儲(chǔ),編寫相應(yīng)的FIRSTADJ(g,V0)和NEXTADJ(g,V0,w),7.3 圖的遍歷,二、廣度優(yōu)先搜索（breadth-first-search),首先訪問指定頂點(diǎn)v0，將v0作為當(dāng)前頂點(diǎn); 訪問當(dāng)前頂點(diǎn)的所有未訪問過的鄰接點(diǎn)， 并依次將訪問的這些鄰接點(diǎn)作為當(dāng)前頂點(diǎn); 重復(fù)2， 直到所有頂點(diǎn)被訪問為止。,對(duì)右圖廣度優(yōu)先搜索，訪問頂點(diǎn)序列為： 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è)頂點(diǎn)② G’是連通的③ G’中無回路則G’是G的生成樹,7.4 最小生成樹,具有n個(gè)頂點(diǎn)的無向連通圖G 其任一生成G’恰好含n-1條邊 生成樹不一定唯一，如,4個(gè)頂點(diǎn)選擇3條邊有如下5種形狀(5×4= 20種):其中16種為生成樹,（保證了連通

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

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

34、V-U，若邊（u，v）是連接這兩個(gè)頂點(diǎn)集的最小權(quán)值邊，則邊（u，v）必然是某最小生成樹的邊。,三、普里姆（Prim）最小生成樹算法,設(shè) N=（V，{E}）是一個(gè)連通網(wǎng)，V=[1，2，…，n}是N的頂點(diǎn)集合，輔助集合U，初值為{Uo}，用來存放當(dāng)前所得到的最小生成樹的頂點(diǎn)；輔助集合TE，初值為{}，用來存放當(dāng)前所得到的最小生成樹的邊。,Prim算法步驟,1. TE=Ф,U={u0}2. 當(dāng)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}，頂點(diǎn)V0 并入U(xiǎn),特點(diǎn): 以連通為主選代價(jià)最小的鄰接邊,Prim算法實(shí)現(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; {頂點(diǎn)k并入U(xiǎn)} 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] {新頂點(diǎn)并入U(xiǎn)后，重選最小代價(jià)邊} ]ENDP； {minispantree_PRIM},算法minispantree_PRIM的幾點(diǎn)說明:1. gn為 網(wǎng)的鄰接矩陣 即 gn[i, j]=wij 或 為無窮大2. 輔助數(shù)組closedge[1..n] 有兩個(gè)分量: closedge[k].vex存放邊(k, j)依附的另一頂點(diǎn)j( j∈U) c

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

41、M的幾點(diǎn)說明: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)成回路的當(dāng)前最小代價(jià)邊。特點(diǎn): 以最小代價(jià)邊主。設(shè)N=（V，{E}）是個(gè)連通網(wǎng), 算法步驟為：1. 置生成樹T的初始狀態(tài)為T=（V，{Ф}）2. 當(dāng)T中邊數(shù)<n-1時(shí), 重復(fù)下列步驟: 從E

43、中選取代價(jià)最小的邊（v, u）, 并刪除之; 若（v, u）依附的頂點(diǎn)v和u落在T中不同的連同分量上，則將邊（v, u）并入到T的邊集中；否則，舍去該邊，選擇下一條代價(jià)最小的邊.,四、克魯斯卡爾（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代價(jià)=(1+2+3+4+5)=

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

47、有向圖為頂點(diǎn)表示活動(dòng)的網(wǎng)（AOV網(wǎng)）。,7.5 拓?fù)渑判?topological sort),AOV網(wǎng)可解決如下兩個(gè)問題：（1）判定工程的可行性。顯然，有回路，整個(gè)工程就無法結(jié)束（2）確定各項(xiàng)活動(dòng)在整個(gè)工程執(zhí)行中的先后順序。 稱這種先后順序?yàn)橥負(fù)溆行蛐蛄小?如圖有如下拓?fù)溆行蛐蛄校?a1 a2 a3a4 a6 a5 a7 a8 a9

48、 a2 a6 a1 a3 a4 a5 a7 a9 a8,二、拓?fù)渑判蛩惴?1. 算法步驟(1) 在AOV網(wǎng)中，選取一個(gè)沒有前驅(qū)的頂點(diǎn)輸出；(2) 刪除該頂點(diǎn)和所有以它為弧尾的弧；(3) 重復(fù)以上兩步，直到AOV網(wǎng)中全部頂點(diǎn)都已輸出（得到拓?fù)溆行蛐蛄校┗蛘?，圖中再無沒有前驅(qū)的頂點(diǎn)（AOV網(wǎng)中有環(huán)）,二、拓?fù)渑判蛩惴?如何實(shí)現(xiàn)算法中的(1)和(2)？對(duì)于(1)，

49、沒有前驅(qū)的頂點(diǎn)即入度為0的頂點(diǎn)；對(duì)于(2)，刪除以它為弧尾的所有弧，即讓該頂點(diǎn)的所有直接后繼的入度減1。,由此分析知：拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)與頂點(diǎn)的入度有密切關(guān)系，因此，在選取存儲(chǔ)結(jié)構(gòu)時(shí)，應(yīng)考慮： 能容易得到各頂點(diǎn)的入度； 有利于尋找任一頂點(diǎn)的所有直接后繼。為此，采用鄰接表作為AOV網(wǎng)的存儲(chǔ)結(jié)構(gòu)，并在頭結(jié)點(diǎn)中增加一個(gè)存放頂點(diǎn)入度的域（indegree）,二、拓?fù)渑判蛩惴?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;{計(jì)數(shù)變量初值為0} WHILE

51、 NOT EMPTY(top) DO [ j:=POP(top); write(dig[j].vexdata); m:=m+1; q:=dig[j].firstare;{設(shè)置移動(dòng)指針} 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的頂點(diǎn)入棧} 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、 若有向圖中，頂點(diǎn)表示事件，弧表示活動(dòng)，弧上的權(quán)表示完成該活動(dòng)所需的時(shí)間，則稱這類有向圖為邊表示活動(dòng)的網(wǎng)（AOE網(wǎng)） AOE網(wǎng)中僅有一個(gè)入度為0的事件，稱為源點(diǎn)，它表示工程的開始；網(wǎng)中也僅有一個(gè)出度為0的事件，稱為匯點(diǎn)，它表示工程的結(jié)束。 每一事件V表示以它為弧頭的所有活動(dòng)已經(jīng)完成，同時(shí)，也表示以它為弧尾的所有活動(dòng)可以開始。,7.6 關(guān)鍵路徑,AOE網(wǎng)可解決如下問題

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

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

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

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

58、面遞推公式，計(jì)算出各時(shí)間的最遲發(fā)生時(shí)間：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è)活動(dòng)ai由弧表示，其持續(xù)時(shí)間為dut()，則利用下面公式，計(jì)算出各活動(dòng)的最早、最遲開始時(shí)間：e(i)=ve(j)l(i)=vl(k)-dut()4. 找出e(i)=l(i)的活動(dòng)，即為關(guān)鍵活動(dòng)，諸關(guān)鍵活動(dòng)組成的從源點(diǎn)到匯點(diǎn)的路徑即為關(guān)鍵路徑。,7.6 關(guān)鍵路徑,四、例子,7.6 關(guān)鍵路徑,關(guān)鍵路徑上的活動(dòng)都是關(guān)鍵活動(dòng)?？s短非關(guān)鍵活動(dòng)都不能縮短整個(gè)工期 如a6縮短為1，則整個(gè)工期仍為8。

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

61、:Boolean; {求得各頂點(diǎn)事件的最早發(fā)生時(shí)間于ve[1..n], 逆拓?fù)溆行蛐蛄杏跅op2} 建立入度為0的頂點(diǎn)棧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)鍵活動(dòng)}

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 最短路徑在有向圖中，尋找從某個(gè)源點(diǎn)到其余各個(gè)頂點(diǎn)或者每一對(duì)頂點(diǎn)之間的最短帶權(quán)路徑的運(yùn)算，稱為最短路徑問題,一、某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑算法迪杰特拉（Dijkstr

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