數(shù)據(jù)結(jié)構(gòu)：第七章 圖

1、1第七章 圖本章目標(biāo)熟練掌握圖中常用的術(shù)語和概念。 熟練掌握圖的鄰接矩陣和鄰接表的存儲方式。熟練掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的方法和算法。熟練掌握最小生成樹的概念和算法。掌握拓?fù)渑判虿⒛芮蟪鐾負(fù)湫蛄?。掌握關(guān)鍵路徑算法并能求出關(guān)鍵路徑。7.1 圖的抽象數(shù)據(jù)類型定義7.2 圖的存儲表示7.3 圖的遍歷7.4 最小生成樹7.7 兩點(diǎn)之間的最短路徑問題7.5 拓?fù)渑判?.6 關(guān)鍵路徑7.1 圖的抽象數(shù)據(jù)類型定義 7.1.1 圖的結(jié)構(gòu)定義7.1.2 名詞和術(shù)語7.1.3 圖的基本操作 圖是由一個頂點(diǎn)集 V 和一個弧集 VR構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。 Graph = (V, VR )其中，VR| v,wV 且

2、 P(v,w) 表示從 v 到 w 的一條?。ㄒ粭l單向通路），并稱 v 為弧尾，w 為弧頭。 謂詞 P(v,w) 定義了弧 的意義或信息。7.1.1 圖的結(jié)構(gòu)定義（V是頂點(diǎn)的有窮非空集合，VR是兩頂點(diǎn)間關(guān)系的集合。）vw數(shù)據(jù)元素沒有數(shù)據(jù)元素元素之間的關(guān)系線性表元素空表線性關(guān)系樹結(jié)點(diǎn)空樹層次關(guān)系圖頂點(diǎn)不能為空任意頂點(diǎn)都可能存在關(guān)系，用邊來表示 如“弧”是有方向的，因此稱由頂點(diǎn)集和弧集構(gòu)成的圖為有向圖。EACBD例如:G1 = (V1, VR1)其中V1=A, B, C, D, EVR1=, , , , , , 7.1.2 名詞和術(shù)語1.有向圖： 若VR 必有VR, 即VR是對稱的，則以無序?qū)?v

3、,w)代替這兩個有序?qū)ΓQ頂點(diǎn) v 和頂點(diǎn) w 之間存在一條邊(v,w) 。BCAFED由頂點(diǎn)集和邊集構(gòu)成的圖稱作無向圖。例如: G2=(V2,VR2)V2=A, B, C, D, E, FVR2=(A, B), (A, E), (B, E), (B, F), (C, D), (C, F) (D, F)3.邊：2.無向圖：ABECFAEFBBC設(shè)圖G=(V, VR) 和 圖 G=(V, VR),且 VV, VRVR,則稱 G 為 G 的子圖。1597211132 弧或邊帶權(quán)的圖分別稱作有向網(wǎng)或無向網(wǎng)。4. 子圖：5. 有向網(wǎng)，無向網(wǎng)：完全圖 假設(shè)圖中有 n 個頂點(diǎn)，e 條邊，如果e=n(n-1

4、)/2 ，則該無向圖為完全圖。有向完全圖 將含有 e=n(n-1) 條弧的有向圖稱作有向完全圖。稀疏圖： 如果邊或弧的個數(shù)很少（如滿足 e n log n），則稱作稀疏圖，否則稱作稠密圖。6. 完全圖、稀疏圖、稠密圖：鄰接點(diǎn)：假若頂點(diǎn)v 和頂點(diǎn)w 之間存在一條邊， 則稱頂點(diǎn) v 和 w 互為鄰接點(diǎn)。例如:TD(B) = 3TD(A) = 2度：與頂點(diǎn)v 關(guān)聯(lián)的邊的數(shù)目,記為TD(v)。ACDFEB7.鄰接點(diǎn)、度對無向圖來說，頂點(diǎn)的出度: 以頂點(diǎn)v 為弧尾的弧的數(shù)目,記為OD(v);ABECF對有向圖來說，頂點(diǎn)的入度: 以頂點(diǎn)v為弧頭的弧的數(shù)目,記為ID(v)。有向圖中頂點(diǎn)的:度(TD)=出度(

5、OD)+入度(ID)例如:I D(B) = 2OD(B) = 1TD(B) = 3由于弧有方向性，則有入度和出度之分8.入度、出度設(shè)圖G=(V,VR)中的一個頂點(diǎn)序列 u=vi,0,vi,1, , vi,m=w中，(vi,j-1,vi,j)VR ,1jm,則稱從頂點(diǎn)u 到頂點(diǎn)w 之間存在一條路徑。路徑上邊的數(shù)目稱作路徑長度。ABECF 如:從A到F長度為3的路徑：簡單路徑:指序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。簡單回路:指序列中第一個頂點(diǎn)和最后一個頂點(diǎn)相同，且除此之外序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。9. 路徑、路徑長度、簡單路徑、簡單回路ABC ABCFA,B,C,F和 A,E,C,F BCFB練習(xí)：24

6、5136路徑：1，2，3，5，6，3路徑長度：5簡單路徑：1，2，3，5回路：1，2，3，5，6，3，1簡單回路：3，5，6，3157324G26路徑：1，2，5，7，6，5，2，3路徑長度：7簡單路徑：1，2，5，7，6回路：1，2，5，7，6，5，2，1簡單回路：1，2，3，1若無向圖中任意兩個頂點(diǎn)之間都有路徑相通，則稱此圖為連通圖;若無向圖為非連通圖，則圖中各個極大連通子圖稱作此圖的連通分量。10. 連通圖、連通分量BACDFEG1BACDFEG2 若任意兩個頂點(diǎn)之間都存在一條有向路徑，則稱此有向圖為強(qiáng)連通圖。ABECFABECF對有向圖， 否則，其各個極大強(qiáng)連通子圖稱作它的強(qiáng)連通分量。

7、11. 強(qiáng)連通圖、強(qiáng)連通分量 假設(shè)一個連通圖有 n 個頂點(diǎn)和 e 條邊，其中 n 個頂點(diǎn)和n-1 條邊 構(gòu)成一個極小連通子圖，稱該極小連通子圖為此連通圖的生成樹。BACDFE12. 生成樹 BACDFEBACDFEBACDFE若在一棵生成樹上添加一條邊，則？。 則必定構(gòu)成一個環(huán)，因?yàn)樾绿砑拥倪叡厥沟靡栏接谶@條邊的兩個頂點(diǎn)之間有了第二條路經(jīng)。一棵有n個頂點(diǎn)的生成樹有且僅有？邊若少于n-1條邊，則非連通；若多于n-1條邊，則必有環(huán)。 對非連通圖，則稱各個連通分量生成樹的集合為此非連通圖的生成森林。13. 生成森林BAEECDF非連通圖BAEECDF生成森林1. 結(jié)構(gòu)的建立和銷毀3. 插入或刪除頂點(diǎn)

8、5. 對鄰接點(diǎn)的操作2. 對頂點(diǎn)的訪問操作6. 遍歷4. 插入或刪除弧7.1.3 圖的基本操作CreatGraph(&G, V, VR): / 按定義(V, VR) 構(gòu)造圖DestroyGraph(&G): / 銷毀圖1. 結(jié)構(gòu)的建立和銷毀2. 對頂點(diǎn)的訪問操作LocateVex(G, u); / 若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在 / 圖中“位置” ；否則返回其它信息。GetVex(G, v); / 返回 v 的值。PutVex(&G, v, value); / 對 v 賦值value。3. 對鄰接點(diǎn)的操作FirstAdjVex(G, v); / 返回 v 的“第一個鄰接點(diǎn)” 。若該頂點(diǎn)/在

9、G 中沒有鄰接點(diǎn)，則返回“空”。NextAdjVex(G, v, w); / 返回 v 的（相對于 w 的） “下一個鄰接/ 點(diǎn)”。若 w 是 v 的最后一個鄰接點(diǎn)，則/ 返回“空”。例NextAdjVex(G, B, E)？FirstAdjVex(G, B) ？鄰接點(diǎn)操作與存儲表示有關(guān) BACDFEG1234554321AF4. 插入或刪除頂點(diǎn)InsertVex(&G, v); /在圖G中增添新頂點(diǎn)v。DeleteVex(&G, v); / 刪除G中頂點(diǎn)v及其相關(guān)的弧。5. 插入或刪除弧InsertArc(&G, v, w); / 在G中增添弧，若G是無向的， /則還增添對稱弧。Delete

10、Arc(&G, v, w); /在G中刪除弧，若G是無向的， /則還刪除對稱弧。6. 遍 歷DFSTraverse(G, v, Visit(); /從頂點(diǎn)v起深度優(yōu)先遍歷圖G，并對每個頂點(diǎn)調(diào)/用函數(shù)Visit一次且僅一次。一旦Visit（）失敗，/則操作失敗。BFSTraverse(G, v, Visit(); /從頂點(diǎn)v起廣度優(yōu)先遍歷圖G，并對每個頂點(diǎn)調(diào)/用函數(shù)Visit一次且僅一次。一旦Visit（）失敗，/則操作失敗。7.1 圖的抽象數(shù)據(jù)類型定義7.2 圖的存儲表示7.3 圖的遍歷7.4 最小生成樹7.7 兩點(diǎn)之間的最短路徑問題7.5 拓?fù)渑判?.6 關(guān)鍵路徑7.2 圖的存儲表示圖的存儲

11、結(jié)構(gòu)必須反映出圖的一些基本特征： * 圖的種類（有向圖、有向網(wǎng)、無向圖、無向網(wǎng)） * 圖的頂點(diǎn)數(shù)和圖的邊數(shù) * 邊的信息 （鄰接點(diǎn)、權(quán)、含義） * 頂點(diǎn)的信息 （編號、名稱、含義）因此，設(shè)計(jì)圖的存儲結(jié)構(gòu)必須對上述各項(xiàng)進(jìn)行描述。 7.2 圖的存儲表示7.2.1 圖的數(shù)組(鄰接矩陣)存儲表示7.2.2 圖的鄰接表存儲表示7.2.3 有向圖的十字鏈表存儲表示 圖的存儲表示的特點(diǎn)： 圖結(jié)構(gòu)中任意兩個頂點(diǎn)之間都可能存在“關(guān)系”，因此無法以順序存儲映象表示這種關(guān)系，即圖沒有順序存儲結(jié)構(gòu) 。 7.2 圖的存儲表示頂點(diǎn)表: 一個記錄各個頂點(diǎn)信息的一維數(shù)組，鄰接矩陣：一個表示各個頂點(diǎn)之間的關(guān)系（邊或弧）的二維數(shù)

12、組。設(shè)圖 G = (V, E)是一個有 n 個頂點(diǎn)的圖，則圖的鄰接矩陣G.arcsnn 定義為：G.arcsij= 1 若 或(Vi,Vj)E 0 反之7.2.1鄰接矩陣 (Adjacency Matrix)表示法（數(shù)組表示法）Aij= 0 , (vi,vj)VR 1 , (vi,vj)VR7.2.1 圖的數(shù)組(鄰接矩陣)存儲表示定義: nn矩陣的元素為 1 2 3 4 5 6123456V1V2V3V4V5V6無向圖網(wǎng)的鄰接矩陣存儲表示定義: nn矩陣的元素為無向網(wǎng)V1V2V3V4V5V615671122512 1 2 3 4 5 6123456888888888888888888888 A

13、ij= wi,j ,(vi,vj) VR ,(vi,vj) VR8顯然，無向圖和無向網(wǎng)的鄰接矩陣是對稱矩陣。有向圖的鄰接矩陣為非對稱矩陣V1V2V4V3V5 1 2 3 4 512345出度？入度？出度入度 typedef struct / 圖的定義 MGraph;typedef struct ArcCell / 弧的定義 VRType adj; / VRType是頂點(diǎn)關(guān)系類型。 / 對無權(quán)圖，用1或0表示相鄰否； / 對帶權(quán)圖，則為權(quán)值類型。 InfoType *info; / 該弧相關(guān)信息的指針 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;

14、 VertexType vexsMAX_VERTEX_NUM; / 頂點(diǎn)向量，頂點(diǎn)信息 AdjMatrix arcs; / 鄰接矩陣 ，弧信息 int vexnum, arcnum; / 頂點(diǎn)數(shù)，弧數(shù) GraphKind kind; / 圖的種類標(biāo)志 (DG,UDG,DN,UDN) 采用鄰接矩陣構(gòu)造無向圖輸入：圖的頂點(diǎn)數(shù)vexnum, 邊數(shù)arcnum，邊信息指針info圖的頂點(diǎn)向量（V1, V2, , Vn )圖的邊信息（V1, V2 ) 及權(quán)值W輸出： 鄰接矩陣AdjMatrixvexnumvexnum 頂點(diǎn)向量 vexsvexnumStatus CreateUDN (Mgraph &G)

15、 /構(gòu)造無向圖 scanf(&G.vexnum,&G.arcnum,&IncInfo) /輸入頂點(diǎn)數(shù)，邊數(shù) for(i=0;i G.vexnum;+i) scanf(&G.vexsi); /輸入頂點(diǎn)向量 for(i=0;i G.vexnum;+i) /初始化鄰接矩陣 for(j=0;j G.vexnum;+j) G.arcsij=0,NULL; for(k=0;k G.arcnum;+k) /構(gòu)造鄰接矩陣 scanf(&v1,&v2); /輸入一條邊依附的頂點(diǎn) i=LocateVex(G,v1); j= LocateVex(G,v2); /定位v1, v2 G.arcsij.adj=1; /弧

16、的鄰接關(guān)系 if(IncInfo) Input (*G.); 輸入邊相關(guān)信息 G.arcsji= G.arcsij; /置鄰接矩陣對稱值 /IncInfo為0表示各弧不含其它信息7.2.2鄰接表及其實(shí)現(xiàn) 用鄰接矩陣表示法存儲圖，占用的存儲單元個數(shù)只與圖中頂點(diǎn)的個數(shù)有關(guān)，而與邊的數(shù)目無關(guān)。一個含有n個頂點(diǎn)的圖，如果其邊數(shù)比n2少得多，那么它的鄰接矩陣就會有很多空元素，浪費(fèi)了存儲空間。 鄰接表 對于圖G中的每個頂點(diǎn)vi，該方法把所有鄰接于vi的頂點(diǎn)vj鏈成一個帶頭結(jié)點(diǎn)的單鏈表，這個單鏈表就稱為頂點(diǎn)vi的鄰接表。單鏈表中的每個結(jié)點(diǎn)至少包含兩個域，一個為鄰接點(diǎn)域（adjvex），

17、它指示與頂點(diǎn)vi鄰接的頂點(diǎn)在圖中的位序，另一個為鏈域（next），它指示與頂點(diǎn)vi鄰接的下一個結(jié)點(diǎn)。 adjvex nextarc data firstarc 為了便于隨機(jī)訪問任一頂點(diǎn)的鄰接表，可將所有頭結(jié)點(diǎn)順序存儲在一個向量中就構(gòu)成了圖的鄰接表存儲。最后將圖的頂點(diǎn)數(shù)及邊數(shù)等信息與鄰接表放在一起來描述圖的存儲結(jié)構(gòu)。 v0v1v3v2 無向圖1 2 3 0 2 0 1 3 0 2 V0V1V2V3鄰接表表頭結(jié)點(diǎn)結(jié)構(gòu)邊結(jié)點(diǎn)結(jié)構(gòu) 對于無向圖，vi的鄰接表中每個表結(jié)點(diǎn)都對應(yīng)于與vi相關(guān)聯(lián)的一條邊；對于有向圖來說，如果每一頂點(diǎn)vi的鄰接表中每個表結(jié)點(diǎn)都存儲以vi的為始點(diǎn)射出的一條邊，則稱這種表為有向圖的

18、出邊表（有向圖的鄰接表），反之，若每一頂點(diǎn)vi的鄰接表中每個表結(jié)點(diǎn)都對應(yīng)于以vi為終點(diǎn)的邊（即射入vi的邊），則稱這種表為有向圖的入邊表（又稱逆鄰接表）。 v0v1v2v31 0 2 0 1 1 出邊表v0v1v2v3 1 2 0 2 1 3 入邊表v3v1v0v2 有向圖 在無向圖的鄰接表中，頂點(diǎn)vi的度為第i個鏈表中結(jié)點(diǎn)的個數(shù)；而在有向圖的出邊表中，第i個鏈表中的結(jié)點(diǎn)個數(shù)是頂點(diǎn)vi的出度；為了求入度，必須對整個鄰接表掃描一遍，所有鏈表中其鄰接點(diǎn)域的值為i的結(jié)點(diǎn)的個數(shù)是頂點(diǎn)vi的入度。 1 2 3 0 2 0 1 3 0 2 V0V1V2V3V0的度為3v0v1v2v31 0 2 0 1 1

19、 有向圖出邊表V0的出度為1，入度為2 無向圖網(wǎng)絡(luò) (帶權(quán)圖) 的鄰接表typedef struct AdjList vertices; /頂點(diǎn)向量 int vexnum, arcnum; / 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) int kind; / 圖的種類標(biāo)志 ALGraph;圖的結(jié)構(gòu)定義(鄰接表)typedef struct VNode VertexType data; / 頂點(diǎn)信息 ArcNode *firstarc; / 指向第一條依附該頂點(diǎn)的弧 VNode, AdjListMAX_VERTEX_NUM; data firstarc頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)typedef struct ArcNode in

20、t adjvex; / 該弧所指向的頂點(diǎn)的位置 struct ArcNode *nextarc; / 指向下一條弧的指針 InfoType *info; / 該弧相關(guān)信息的指針 ArcNode;adjvex nextarc info弧的結(jié)點(diǎn)結(jié)構(gòu)ABECD構(gòu)造有向圖的鄰接表算法230 12 A B C D E4 輸入頂點(diǎn)數(shù)和弧數(shù)輸入頂點(diǎn)表頭向量輸入弧產(chǎn)生一個新的弧結(jié)點(diǎn)定位弧的頂點(diǎn)v1和v2對新弧結(jié)點(diǎn)賦值插入弧結(jié)點(diǎn)到單鏈表0, 1114 01234練習(xí)：1.畫出有向圖G的鄰接矩陣、鄰接表、逆鄰接表。V1V3V4V5V6V2G鄰接表 逆鄰接表 1 50 42 31 v1 v2 v3 v4 v5 v6

21、01234552 50 31 35 v1 v2 v3 v4 v5 v62012345課堂練習(xí)：1 對于下列無向圖，試給出（1）圖中每個頂點(diǎn)的度；（2）該圖的鄰接矩陣；（4）該圖的連通分量。v0v3v4v2v1v5v62 給定有向圖，試給出（1）頂點(diǎn)D的入度與出度；（2）該圖的鄰接表(出邊表)與逆鄰接表(入邊表)；（3）該圖的強(qiáng)連通分量。 ABCDE將有向圖的鄰接表和逆鄰接表合起來將有向圖的鄰接表和逆鄰接表合起來三部分：頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)弧的結(jié)點(diǎn)結(jié)構(gòu)圖的結(jié)構(gòu)定義7.2.3 有向圖的十字鏈表存儲表示 ABECD1 4230 120 1 2 3 4 A B C D E 鄰接表 逆鄰接表 A B C D

22、E 3 0 3 4 2 0012341頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)頂點(diǎn)信息數(shù)據(jù) 指向該頂點(diǎn)的第一條入弧指向該頂點(diǎn)的第一條出弧typedef struct VexNode / 頂點(diǎn)的結(jié)構(gòu)表示 VertexType data; ArcBox *firstin, *firstout; VexNode;datafirstinfirstout弧的結(jié)點(diǎn)結(jié)構(gòu)弧尾頂點(diǎn)位置 弧頭頂點(diǎn)位置 弧的相關(guān)信息指向下一個有相同弧尾的結(jié)點(diǎn)指向下一個有相同弧頭的結(jié)點(diǎn)typedef struct ArcBox / 弧的結(jié)構(gòu)表示 int tailvex, headvex; InfoType *info; struct ArcBox *hlin

23、k, *tlink; ArcBox ;hlinktlinktailvexheadvexinfotypedef struct VexNode xlistMAX_VERTEX_NUM; / 頂點(diǎn)結(jié)點(diǎn)(表頭向量) int vexnum, arcnum; /有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) OLGraph;圖的結(jié)構(gòu)定義2 33 13 03 22 00 10 2V1V2V3V40123例如： v1v4v2v301231 0若增加一條邊練習(xí)：畫出有向圖G的十字鏈表。V1V3V5V4V2G2 13 00 1V1V2V3V4V5012341 21 32 33 4出鏈入鏈7.3 圖的遍歷樹的遍歷： 從根開始遍歷； 遍歷

24、可以從左到右，從上到下； 存儲結(jié)構(gòu)不改變遍歷結(jié)果；深度優(yōu)先搜索DFS (Depth_First Search)廣度優(yōu)先搜索BFS(Breadth_First Search)圖的遍歷: 從圖中某一頂點(diǎn)出發(fā)遍歷圖中其余頂點(diǎn)， 使得每個結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。 從圖中某個頂點(diǎn)V0 出發(fā)，訪問此頂點(diǎn)，然后依次從V0的各個未被訪問的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到。7.3.1、深度優(yōu)先搜索連通圖的深度優(yōu)先搜索遍歷1. 訪問頂點(diǎn) V ;2. for (W1、W2、W3 ) 若該鄰接點(diǎn)Wi未被訪問， 則深度優(yōu)先搜索遍歷該子圖。1. 訪問根結(jié)點(diǎn)；2. 先序

25、遍歷左子樹；3. 先序遍歷右子樹。二叉樹的先根遍歷圖的深度優(yōu)先遍歷根左子樹右子樹根左子樹右子樹子圖3子圖1子圖2Vw1w3w2w1w2w3深度優(yōu)先搜索DFS ( Depth First Search )深度優(yōu)先搜索的示例 DFS 的思路（1）從圖中的某個頂點(diǎn)V出發(fā)，訪問之；（2）依次從頂點(diǎn)V的未被訪問過的鄰接點(diǎn)出發(fā)， 深度優(yōu)先遍歷圖，直到圖中所有和頂點(diǎn)V 有路徑相通的頂點(diǎn)都被訪問到；（3）若此時圖中尚有頂點(diǎn)未被訪問到，則另選 一個未被訪問過的頂點(diǎn)作起始點(diǎn)，重復(fù)上 述（1）（2）的操作，直到圖中所有的頂 點(diǎn)都被訪問到為止。深度優(yōu)先搜索舉例:BACDFE從B點(diǎn)開始遍歷BAEFDC深度優(yōu)先搜索舉例:

26、BACDFE從B點(diǎn)開始遍歷.BEAFCDBAEFDC由于沒有規(guī)定訪問鄰接點(diǎn)的順序，深度優(yōu)先序列不是唯一的c0c1c3c2c4c5c0c1c3c2c4c5DFS序列：c0 c1 c3 c4 c5 c2 但是，在存儲結(jié)構(gòu)和源點(diǎn)已確定的情況下，遍歷的結(jié)果將是確定的。深度優(yōu)先搜索遍歷歸納:深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷;3. 解決的辦法是:為每個頂點(diǎn)設(shè)立一個 “訪問標(biāo)志 visitedw”;2. 遍歷過程需要判別V的鄰接點(diǎn)是否被訪問？void DFS(Graph G, int v) / 從頂點(diǎn)v出發(fā)，深度優(yōu)先搜索遍歷連通圖 G visitedv = TRUE; VisitFunc(v)

27、; for(w=FirstAdjVex(G, v); w=0;w=NextAdjVex(G,v,w) if (!visitedw) DFS(G, w); / 對v的尚未訪問的鄰接頂點(diǎn)w / 遞歸調(diào)用DFS / DFS深度優(yōu)先搜索遍歷算法: 1 2 3 4 5 6123456基于鄰接矩陣的深度優(yōu)先搜索舉例從B點(diǎn)開始遍歷 visited 0, 0, 0, 0, 0, 0 鄰接矩陣DBACFEBAEFCD頂點(diǎn)向量 A, B, C, D, E, F void DFS_M(MGraph G, int i, int n) / 從頂點(diǎn)Vi出發(fā)，深度優(yōu)先搜索遍歷鄰接矩陣圖 G visitedi = TRUE;

28、 /標(biāo)記Vi已被訪問過 printf(G.vexsi) ; /輸出Vi for(j=0; jadjvex； if (! visitedj ) /若Vj未被訪問過，則遞歸調(diào)用 DFS _AL(G, j, n); p=p- nextarc; /使p指向vi單鏈表的下一個鄰接點(diǎn) /while / DFS _AL基于鄰接表的深度優(yōu)先搜索算法 首先將圖中每個頂點(diǎn)的訪問標(biāo)志設(shè)為 FALSE，之后搜索圖中每個頂點(diǎn)，如果未被訪問，則以該頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點(diǎn)。非連通圖的深度優(yōu)先搜索遍歷F F F F F F F F F0 1 2 3 4 5 6 7 8abchdekfgTTT

29、TTTTTTachdkfe bgachkfedbg訪問標(biāo)志:訪問次序:例如:812345670 從圖中的某個頂點(diǎn)V0出發(fā)，并在訪問此頂點(diǎn)之后依次訪問V0的所有未被訪問過的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到。7.3.2 廣度優(yōu)先搜索廣度優(yōu)先搜索的示例 廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹 廣度優(yōu)先搜索算法的思路（1）從圖中的某個頂點(diǎn)V出發(fā)，訪問之；（2）依次訪問頂點(diǎn)V的各個未被訪問過的鄰接 點(diǎn)，將V的全部鄰接點(diǎn)都訪問到；（3）分別從這些鄰接點(diǎn)出發(fā)，依次訪問它們的 未被訪問過的鄰接點(diǎn)，并使“先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂

30、點(diǎn)的鄰接點(diǎn)”被訪問，直到圖中所有已被訪問過的頂點(diǎn)的鄰接點(diǎn)都被訪問到。廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有往回退的情況。因此，廣度優(yōu)先搜索不是一個遞歸的過程，其算法也不是遞歸的。為了實(shí)現(xiàn)逐層訪問，算法中使用了一個隊(duì)列，以記憶正在訪問的這一層和上一層的頂點(diǎn)，以便于向下一層訪問。QUEUEV0V1V2V3V4V5V6V7V1V2V3V0V4V5V6V7 V0 V7 V6 V5 V4 V3 V2 V1AB FF C I GC I G EI G E DG E DE D HD HH入列出列void BFSTraverse(Graph G, int v )

31、for (v=0;vG.vexnum;+v) visitedv=FALSE; InitQueue(Q); for (v=0;v=0; w=NextAdjVex(G,u,w) if ( ! visitedw) visitedw=TRUE; printf(w); EnQueue(Q, w); / 訪問的頂點(diǎn)w入隊(duì)列 / if / while /if /BFSTraverse7.4 最小生成樹7.4.1 連通圖的生成樹7.4.2 連通網(wǎng)的最小生成樹 對于一個連通圖G=（V，E），設(shè)G是它的一個子圖，如果G中包含了G中所有的頂點(diǎn)（即V（G）=V（G）且G是無回路的連通圖，則稱G為G一棵的生成樹。 7.

32、4.1 連通圖的生成樹 一個連通圖可以有多棵生成樹：從不同的頂點(diǎn)出發(fā)得到不同的生成樹； 采用不同的搜索方法得到不同的生成樹；采用不同的存儲結(jié)構(gòu)得到不同的生成樹；深度優(yōu)先生成樹（DFS生成樹） 由深度優(yōu)先搜索得到的生成樹；廣度優(yōu)先生成樹（BFS生成樹） 由廣度優(yōu)先搜索得到的生成樹。例7.4.1:畫出下面有向圖從頂點(diǎn)v1開始的DFS生成樹與BFS生成樹。V2V4V5V3V7V6V1V2V4V5V3V7V6V1V2V4V5V3V7V6V1DFS生成樹BFS生成樹練習(xí)：畫出下面非連通圖從頂點(diǎn)v1開始的DFS與BFS生成森林。V2V4V5V3V7V6V1V8V2V4V5V3V7V6V1V8DFS生成森林

33、V2V4V5V3V7V6V1V8BFS生成森林 假設(shè)要在 n 個城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通 n 個城市只需要修建 n-1條線路，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個通訊網(wǎng)？問題：7.4.2 連通網(wǎng)的最小代價生成樹北京濟(jì)南鄭州青島廣州大連7131791812752410頂點(diǎn)表示城市權(quán)值城市間建立通信線路所需花費(fèi)代價 希望找到一棵生成樹，它的每條邊上的權(quán)值之和（即建立該通信網(wǎng)所需花費(fèi)的總代價）最小-最小代價生成樹。 構(gòu)造網(wǎng)的一棵最小代價生成樹，即：在 e 條帶權(quán)的邊中選取 n-1 條邊（不構(gòu)成回路），使“權(quán)值之和”最小。算法二：克魯斯卡爾(Kruskal)算法該問題等價于：算法一：普里姆(Prim

34、)算法 構(gòu)造最小生成樹可以有多種算法，其中大多數(shù)算法都是利用了最小生成樹的下述性質(zhì)： 設(shè)G(V，E)是一個連通網(wǎng)，U是頂點(diǎn)集V的一個非空真子集。若(u，v)是滿足uU，vV-U的邊（稱這種邊為兩棲邊）且(u，v)在所有兩棲邊中具有最小權(quán)值，則一定存在G的一棵最小生成樹包含此邊(u，v)。這個性質(zhì)稱為MST性質(zhì)。 (Minimum Cost Spanning Tree)abcdegf195141827168213127U= , abV-U= , , , , efdcg一、普里姆(Prim)算法的基本思想是： 首先從V中任取一個頂點(diǎn)u0，將生成樹T置為僅有一個結(jié)點(diǎn)u0的樹，即置Uu0；然后只要U是

35、V的真子集，就在所有兩棲邊中，找一條權(quán)值最小的邊(u，v)，并把該條邊(u，v)并入T的邊集、其不在T中的頂點(diǎn)v并入頂點(diǎn)集U中。如此進(jìn)行下去，每次往生成樹里并入一個頂點(diǎn)和一條邊，直到把所有頂點(diǎn)都包括進(jìn)生成樹T為止。此時，必有UV，TE中有n-1條邊。MST性質(zhì)保證上述過程求得的T(U，TE)是G的一棵最小生成樹。 v1v2v3vkvnv0原圖頂點(diǎn)集合V-Uv0v196156915720vk7最小生成樹頂點(diǎn)集合U92025普里姆(Prim)算法：利用普里姆算法建立最小生成樹ABCDEF10101512128765 （a）無向網(wǎng)5ABCDEF107610（e）選?。˙、F）ABCDEF101512

36、（b）初始狀態(tài)5ABCDEF101576（c）選?。ˋ、B）5ABCDEF101576（d）選取（B、D） 5ABCDEF107610（f）選?。˙、C）5ABCDEF107610（g）選?。‥、F）16abcdegf195141827168213127例如:aedcbgf148531621所得生成樹權(quán)值和= 14+8+3+5+16+21 = 67 假設(shè)在生成樹的構(gòu)造過程中，圖中 n 個頂點(diǎn)分屬兩個集合：落在生成樹上的頂點(diǎn)集 U 和尚未落在生成樹上的頂點(diǎn)集 V-U 。 下一步應(yīng)該在所有連通U中和V-U中的頂點(diǎn)的邊（兩棲邊）中，選取權(quán)值最小的邊。V-U U普里姆算法的關(guān)鍵:struct Vert

37、exType adjvex; / 頂點(diǎn) VRType lowcost; / 權(quán)值 closedgeMAX_VERTEX_NUM; 設(shè)置一個輔助數(shù)組，以記錄從U到VU具有最小代價的邊。對每個頂點(diǎn)vi VU在輔助數(shù)組存在一個相應(yīng)的分量closedgei-1，它包括兩個域：普里姆算法的實(shí)現(xiàn)：每個頂點(diǎn)有一個closedgei值，其分量.lowcost：從U中任一頂點(diǎn)到該頂點(diǎn)(由i確定)權(quán)值的最小值；.adjvex：依附于這條最小代價邊的另一個頂點(diǎn)。.lowcost= 0 表示頂點(diǎn)i已在U中； 0 表示頂點(diǎn)i還在V-U中。 所以，每次循環(huán)須在.lowcost 0(在集合V-U中)的那些頂點(diǎn)中選擇.low

38、cost 最小的頂點(diǎn)加入到集合U中，同時將相關(guān)頂點(diǎn)的closedge作相應(yīng)的調(diào)整。普里姆算法的實(shí)現(xiàn)：abcdegf195141827168213127aedb基于鄰接矩陣的 普里姆算法0 1 2 3 4 5 6ca19aaaaaa141888800gf12e8e16e03d21d7d5c0000191418195712537382114128162127181627a b c d e f gabcdefg 普里姆算法歸納(基于鄰接矩陣存儲結(jié)構(gòu))： 1. 根據(jù)起始頂點(diǎn)初始化輔助數(shù)組；2. 起始頂點(diǎn)lowcost值置0 ；3.循環(huán)處理其余n-1個頂點(diǎn)； 求剩余頂點(diǎn)中l(wèi)owcost值最小的頂點(diǎn)k;

39、輸出頂點(diǎn)k和邊作為生成樹的一個結(jié)點(diǎn)和邊； 將第k 個頂點(diǎn)的lowcost置0，表示加入U(xiǎn)集； 循環(huán)將新頂點(diǎn)并入U(xiǎn)集后重新選擇最小邊；void MiniSpanTree_P(MGraph G, VertexType u) /用普里姆算法從頂點(diǎn)u出發(fā)構(gòu)造網(wǎng)G的最小生成樹 k = LocateVex ( G, u ); for ( j=0; jG.vexnum; +j ) / 輔助數(shù)組初始化 if (j!=k) closedgej = u, G.arcskj.adj ; closedgek.lowcost = 0; / 初始化，Uu for (i=1; iG.vexnum; +i) ?繼續(xù)向生成樹上

40、添加頂點(diǎn);見下頁。 k = minimum(closedge); / 求出加入生成樹的下一個頂點(diǎn)(k) printf(closedgek.adjvex, G.vexsk); / 輸出生成樹上一條邊 closedgek.lowcost = 0;/將第k 頂點(diǎn)置0，表示加入U(xiǎn)集； for (j=0; jG.vexnum; +j) /循環(huán)將新頂點(diǎn)并入U(xiǎn)集以便重新選擇最小邊； if (G.arcskj closedgej.lowcost) closedgej = G.vexsk, G.arcskj ; 考慮問題的出發(fā)點(diǎn): 為使生成樹上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹中每一條邊的權(quán)值盡可能地小。二、克

41、魯斯卡爾(Kruskal)算法的基本思想：克魯斯卡爾(Kruskal)算法具體做法: 假設(shè)圖G（V，E）是一個連通圖； 先構(gòu)造一個只含 n 個頂點(diǎn)且無邊的非連通圖T（V， ），圖中每個頂點(diǎn)自成一個連通分量； 從圖G中選擇權(quán)值最小的邊，如果該邊的兩個頂點(diǎn)落在圖T的不同連通分量上，則將該邊加入到T中，否則選擇下一條邊； 如此重復(fù)，直至加上 n-1 條邊為止。251234192646381725ABEDCFABEDCF連通分量A, B, C, D, E, F最小生成樹算法 Kruskal算法251234192646381725ABEDCFABEDCF連通分量A, B, C, D, E, F12連通分

42、量A, B, E, C, D, F 最小生成樹算法 Kruskal算法251234192646381725ABEDCFABEDCF連通分量A, B, E, C, D, F12連通分量A, B, E, C, D,F174 最小生成樹算法 Kruskal算法251234192646381725ABEDCFABEDCF連通分量A, B, E, C, D, F12連通分量A, F, B, E, C, D1917最小生成樹算法 Kruskal算法251234192646381725ABEDCFABEDCF連通分量A, F, B, E, C, D12連通分量A, F, C, D, B, E191725最小

43、生成樹算法 Kruskal算法251234192646381725ABEDCFABEDCF連通分量A, F, C, D, B, E12連通分量A, F, C, D, B, E19172526最小生成樹算法 Kruskal算法1. 初始化：U=V； TE= ； 2. 循環(huán)直到T中的連通分量個數(shù)為1 2.1 在E中尋找最短邊(u，v); 2.2 如果頂點(diǎn)u、v位于T的兩個不同連通分量，則 2.2.1 將邊(u，v)并入TE； 2.2.2 將這兩個連通分量合為一個； 2.3 在E中標(biāo)記邊(u，v)，使得(u，v)不參加后續(xù)最短邊的選取；Kruskal算法的基本步驟如下：應(yīng)用克魯斯卡爾算法構(gòu)造最小生成

44、樹的過程例:5148213aedcbgfabcdegf19514627168213ae12dcbgf76 Prim 算法：初始值為某個頂點(diǎn)(即1個連通分量)，在一個連通分量上添加邊和頂點(diǎn)。 Kruskal 算法：初始值為n個頂點(diǎn)(即n個連通分量)，每次使連通分量的個數(shù)減一。 用一句話描述兩種算法練習(xí)：利用Prim算法、Kruskal算法構(gòu)造最小生成樹。gde afcbh21112221234gde afcbh2111221結(jié)果：7.1 圖的抽象數(shù)據(jù)類型定義7.2 圖的存儲表示7.3 圖的遍歷7.4 最小生成樹7.7 兩點(diǎn)之間的最短路徑問題7.5 .1拓?fù)渑判?.5.2關(guān)鍵路徑7.5 有向無環(huán)圖

45、及其應(yīng)用 有向無環(huán)圖（directed acycline graph）：無環(huán)的有向圖，簡稱DAG圖。DAG圖是一類較有向樹更一般的特殊有向圖。 圖7.21 有向樹、DAG圖和有向圖一例例如，圖7.21示例了有向樹、DAG圖和有向圖的例子。有向無環(huán)圖是描述含有公共子式的表達(dá)式的有效工具 例如，下述表達(dá)式(a +b ) * (b * (c + d) + (c + d) * e) * (c + d) * e)，用二叉樹表示如圖7.22所示，用有向無環(huán)圖表示如圖7.23所示。 圖7.22 用二叉樹描述表達(dá)式*+*+e+*abbcc d dec d圖7.23 描述表達(dá)式的有向無環(huán)圖*+eabc d*+*

46、+*表達(dá)式(a +b ) * (b * (c + d) + (c + d) * e) * (c + d) * e)有向無環(huán)圖也是描述一項(xiàng)工程或系統(tǒng)進(jìn)行過程的有效工具對整個工程和系統(tǒng)，人們關(guān)心的是兩個方面的問題：（1）工程能否順利進(jìn)行；（2）估算整個工程完成所必須的最短時間 ；對應(yīng)于有向圖，即為進(jìn)行拓?fù)渑判蚝颓箨P(guān)鍵路徑的操作。 7.5.1 AOV網(wǎng)與拓?fù)渑判蚴裁词茿OV網(wǎng)？AOV網(wǎng)：在一個表示工程的有向圖中，用頂點(diǎn)表示活動，用弧表示活動之間的優(yōu)先關(guān)系，稱這樣的有向圖為頂點(diǎn)表示活動的網(wǎng)，簡稱AOV網(wǎng)。編號課程名稱先修課C1高等數(shù)學(xué)無C2計(jì)算機(jī)導(dǎo)論無C3離散數(shù)學(xué)C1C4程序設(shè)計(jì)C1, C2C5數(shù)據(jù)結(jié)

47、構(gòu)C3，C4C6計(jì)算機(jī)原理C2，C4C7數(shù)據(jù)庫原理C4，C5，C6C1C2C3C4C6C5C7AOV網(wǎng)圖1 軟件專業(yè)的學(xué)生必須學(xué)習(xí)的課程圖 2 表示課程之間優(yōu)先關(guān)系的有向圖AOV網(wǎng)特點(diǎn)：1.AOV網(wǎng)中的弧表示活動之間存在的某種制約關(guān)系。2.AOV網(wǎng)中不能出現(xiàn)回路 。拓?fù)渑判蛲負(fù)湫蛄校涸O(shè)G=(V，E)是一個具有n個頂點(diǎn)的有向圖，V中的頂點(diǎn)序列v1, v2, , vn稱為一個拓?fù)湫蛄?，?dāng)且僅當(dāng)滿足下列條件：若從頂點(diǎn)vi到vj有一條路徑，則在頂點(diǎn)序列中頂點(diǎn)vi必在頂點(diǎn)vj之前。拓?fù)渑判颍簩σ粋€有向圖構(gòu)造拓?fù)湫蛄械倪^程稱為拓?fù)渑判?。拓?fù)渑判蚧舅枷耄?從AOV網(wǎng)中選擇一個沒有前驅(qū)的頂點(diǎn)并且輸出； 從

48、AOV網(wǎng)中刪去該頂點(diǎn)，并且刪去所有以該頂點(diǎn)為尾的弧； 重復(fù)上述兩步，直到全部頂點(diǎn)都被輸出，或AOV網(wǎng)中不存在沒有前驅(qū)的頂點(diǎn)。C1C2C3C4C6C5C7拓?fù)湫蛄校篊1, 拓?fù)渑判駽2C3C4C6C5C7拓?fù)湫蛄校篊1, C2, 拓?fù)渑判駽3C4C6C5C7拓?fù)湫蛄校篊1, C2, C3, 拓?fù)渑判駽4C6C5C7拓?fù)湫蛄校篊1, C2, C3, C4, 拓?fù)渑判駽6C5C7拓?fù)湫蛄校篊1, C2, C3, C4, C5, 拓?fù)渑判駽6C7拓?fù)湫蛄校篊1, C2, C3, C4, C5, C6, 拓?fù)渑判駽7拓?fù)湫蛄校篊1, C2, C3, C4, C5, C6, C7, 拓?fù)渑判蛟O(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)1

49、. 圖的存儲結(jié)構(gòu)：（刪除頂點(diǎn)）宜采用鄰接表存儲 。2. 為便于算法執(zhí)行過程中考察的入度為0的頂點(diǎn)，可引入一個存放各頂點(diǎn)入度的數(shù)組indegree。3. 為了避免每一步選入度為0的頂點(diǎn)時重復(fù)掃描數(shù)組indegree，可設(shè)置一個棧（或隊(duì)列）來存儲所有入度為0的頂點(diǎn)。在進(jìn)行拓?fù)渑判蛑?，只要對頂點(diǎn)表掃描一遍，將所有入度為0 的頂點(diǎn)都推入棧中，一旦排序過程中出現(xiàn)新的入度為0的頂點(diǎn)，也同樣將其推入棧中。 (a) 一個AOV網(wǎng) (b) AOV網(wǎng)的鄰接表存儲 012345 in vertex firstedge3 A 0 B1 C3 D0 E2 F 0 3 0 0 5 2 3 3 5 ABCDEF拓?fù)渑判?

50、12345 in vertex firstedge 3 A 0 B 1 C 3 D 0 E 2 F 0 3 0 0 5 2 3 3 5 ABCDEFBE拓?fù)渑判?12345 in vertex firstedge 3 A 0 B 1 C 3 D 0 E 2 F 0 3 0 0 5 2 3 3 5 ABCDEFBE0C21拓?fù)渑判?12345 in vertex firstedge 3 A 0 B 0 C 2 D 0 E 1 F 0 3 0 0 5 2 3 3 5 ABCDFBC21拓?fù)渑判?12345 in vertex firstedge 2 A 0 B 0 C 1 D 0 E 1 F 0

51、3 0 0 5 2 3 3 5 ABDFBD01拓?fù)渑判?12345 in vertex firstedge 1 A 0 B 0 C 0 D 0 E 1 F 0 3 0 0 5 2 3 3 5 ADF00AF拓?fù)渑判?12345 in vertex firstedge 0 A 0 B 0 C 0 D 0 E 0 F 0 3 0 0 5 2 3 3 5 AFAF拓?fù)渑判?. 棧S初始化；累加器count初始化；2. 掃描頂點(diǎn)表，將沒有前驅(qū)的頂點(diǎn)壓棧；3. 當(dāng)棧S非空時循環(huán) 3.1 vj=退出棧頂元素；輸出vj；累加器加1； 3.2 將頂點(diǎn)vj的各個鄰接點(diǎn)的入度減1； 3.3 將新的入度為0的頂點(diǎn)

52、入棧；4. if (countvertexNum) 輸出有回路信息；拓?fù)渑判蛩惴▊未a拓?fù)渑判蚪鉀Q的是工程能否順利完成，但有時候需要解決最短時間完成7.1 圖的抽象數(shù)據(jù)類型定義7.2 圖的存儲表示7.3 圖的遍歷7.4 最小生成樹7.6 兩點(diǎn)之間的最短路徑問題7.5.1 拓?fù)渑判?.5.2 關(guān)鍵路徑7.5.2 AOE網(wǎng)與關(guān)鍵路徑 AOE-網(wǎng)（Activity On Edge）：即邊表示活動的網(wǎng)。AOE-網(wǎng)是一個帶權(quán)的有向無環(huán)圖。其中，頂點(diǎn)表示事件（Event），弧表示活動，權(quán)表示活動持續(xù)的時間。（1）AOE-網(wǎng)事件 事件含義 v1 開工 v2 活動a1完成，活動a4可以開始 v3 活動a2完成

53、，活動a5可以開始 v9 活動a10 和a11完成，整個工程完成v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=47.5.2 AOE網(wǎng)與關(guān)鍵路徑 圖7.29源點(diǎn)匯點(diǎn)AOE網(wǎng)可以回答下列問題：1. 完成整個工程至少需要多少時間?2. 為縮短完成工程所需的時間, 應(yīng)當(dāng)加快哪些活動?從始點(diǎn)到終點(diǎn)的路徑可能不止一條，只有各條路徑上所有活動都完成了，整個工程才算完成。因此，完成整個工程所需的最短時間取決于從始點(diǎn)到終點(diǎn)的最長路徑長度，即這條路徑上所有活動的持續(xù)時間之和。這條路徑長度最長的路徑就叫做關(guān)鍵路徑。7.5.2 AOE網(wǎng)與

54、關(guān)鍵路徑 （2）關(guān)鍵路徑：在AOE網(wǎng)中，從始點(diǎn)到終點(diǎn)具有最大路徑長度（該路徑上的各個活動所持續(xù)的時間之和）的路徑稱為關(guān)鍵路徑。關(guān)鍵活動：關(guān)鍵路徑上的活動稱為關(guān)鍵活動。由于AOE網(wǎng)中的某些活動能夠同時進(jìn)行，故完成整個工程所必須花費(fèi)的時間應(yīng)該為始點(diǎn)到終點(diǎn)的最大路徑長度。關(guān)鍵路徑長度是整個工程所需的最短工期。7.5.2 AOE網(wǎng)與關(guān)鍵路徑 要找出關(guān)鍵路徑，必須找出關(guān)鍵活動, 即不按期完成就會影響整個工程完成的活動。首先計(jì)算以下與關(guān)鍵活動有關(guān)的量：事件（頂點(diǎn)）的最早發(fā)生時間vek 事件（頂點(diǎn)）的最遲發(fā)生時間vlk 活動（?。┑淖钤玳_始時間ei 活動（?。┑淖钔黹_始時間li最后計(jì)算各個活動的時間余量 l

55、k - ek，時間余量為0者即為關(guān)鍵活動。7.5.2 AOE網(wǎng)與關(guān)鍵路徑 vek是指從始點(diǎn)開始到頂點(diǎn)vk的最大路徑長度。這個長度決定了所有從頂點(diǎn)vk發(fā)出的活動能夠開工的最早時間。 ve1=0vek=maxvej+len (pk) pk表示所有到達(dá)vk的有向邊的集合 事件的最早發(fā)生時間vek vjvkv2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4v2v7v6v5v4v1v3v9v8vek064577161418vek=maxvej+len應(yīng)用舉例關(guān)鍵路徑 vlk是指在不推遲整個工期的前提下,事件vk允許的最晚發(fā)生時

56、間。 事件的最遲發(fā)生時間vlk vjvjvkvln=venvlk=minvlj-len（sk）sk為所有從vk發(fā)出的有向邊的集合v2v7v6v5v4v1v3v9v8vekvlk0645771614181814161078660v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4應(yīng)用舉例關(guān)鍵路徑vlk=minvlj-len 活動的最早開始時間ei 若活動ai是由弧表示，則活動ai的最早開始時間應(yīng)等于事件vk的最早發(fā)生時間。因此，有： ei=vek v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a1

57、1=4a8=7a9=4a5=1a6=2a3=5a2=4v2v7v6v5v4v1v3v9v8vek064577161418a2a7a6a5a4a1a3a9a8ei000645777a10a111614ei=vek 應(yīng)用舉例關(guān)鍵路徑 活動ai的最晚開始時間是指，在不推遲整個工期的前提下， ai必須開始的最晚時間。 若ai由弧表示，則ai的最晚開始時間要保證事件vj的最遲發(fā)生時間不拖后。因此，有： li=vlj-len 活動的最晚開始時間lili10778663201614v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4

58、a2a7a6a5a4a1a3a9a8a10a11v2v7v6v5v4v1v3v9v8vlk1814161078660li=vlj-len 應(yīng)用舉例關(guān)鍵路徑a2a7a6a5a4a1a3a9a8eili0006457771077866320a10a1116141614v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4關(guān)鍵活動：li=ei的活動應(yīng)用舉例關(guān)鍵路徑求關(guān)鍵路徑步驟求ve(i)求vl(j)求 e(i)求 l(i)計(jì)算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9

59、a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9頂點(diǎn) ve vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動 e l l-e00002266046258377077071031616014140033abcdefghp6452118724400000000064571157151418181818181818181818161486610807拓?fù)溆行蛐蛄? a - d - f - c - b - e - h - g - pp算法的執(zhí)行過程 算法的實(shí)現(xiàn)要點(diǎn):顯然，求ve的順序應(yīng)該是按拓?fù)湫蛄械捻樞?而求vl的順序應(yīng)該是按

60、拓?fù)湫蛄械哪嫘?因此應(yīng)該在拓?fù)渑判虻倪^程中， 另設(shè)一個“?！庇浵峦?fù)湫蛄?。例：對如下AOE網(wǎng)，求出各活動的最早開始時間e(i)和最遲開始時間l(i)。問：工程完成的最短時間是多少？哪些活動是關(guān)鍵活動？并畫出關(guān)鍵路徑。v1v2v10v9v8v7v6v5v4v3a1=5a2=6a8=5a3=3a5=3a4=6a9=1a12=5a10=4a13 =2a11=4a7=4a6 =3a14=2v1v2v10v9v8v7v6v5v4v3a1=5a2=6a8=5a3=3a5=3a4=6a9=1a12=5a10=4a13 =2a11=4a7=4a6 =3a14=2答：v1v10v9v7v4v3活動a1a2a3a