第七章——圖及其應(yīng)用.ppt

1、1,第七章 圖,2,7.1 抽象數(shù)據(jù)類型圖的定義,7.2 圖的存儲(chǔ)表示,7.3 圖的遍歷,7.4 最小生成樹,7.6 最短路徑問題,7.5 拓?fù)渑判?、關(guān)鍵路徑,3,熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法，了解實(shí)際問題的求解效率與采用何種存儲(chǔ)結(jié)構(gòu)和算法有密切聯(lián)系。 2. 熟練掌握?qǐng)D的兩種搜索路徑的遍歷：深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。 3. 圖的算法應(yīng)用。,學(xué)習(xí)提要,4,圖(Graph)：圖G是由兩個(gè)集合V(G)和E(G)組成的,記為G=(V,E)。 其中：V(G)是頂點(diǎn)的非空有限集，E(G)是邊的有限集合，邊是頂點(diǎn)的無序?qū)蛴行驅(qū)Α?有向圖：有向圖G是由兩個(gè)集合V(G)和E(G)組成。 其中：V

2、(G)是頂點(diǎn)的非空有限集E(G)是有向邊（也稱弧）的有限集合，弧是頂點(diǎn)的有序?qū)?，記為，v,w是頂點(diǎn)，v為弧尾，w為弧頭。 無向圖：無向圖G是由兩個(gè)集合V(G)和E(G)組成的。 其中：V(G)是頂點(diǎn)的非空有限集，E(G)是邊的有限集合，邊是頂點(diǎn)的無序?qū)?，記為（v,w）或（w,v），并且（v,w)=(w,v),圖的定義和術(shù)語,5,圖G1中：V(G1)=1,2,3,4,5,6 E(G1)=, , , , , , ,圖G2中：V(G2)=1,2,3,4,5,6,7 E(G1)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7),6,有向完備圖：n個(gè)頂點(diǎn)的有向

3、圖最大邊數(shù)是n(n-1)。 無向完備圖：n個(gè)頂點(diǎn)的無向圖最大邊數(shù)是n(n-1)/2。,7,權(quán)：與圖的邊或弧相關(guān)的數(shù)。 網(wǎng)：帶權(quán)的圖,8,子圖：如果圖G(V,E)和圖G(V,E),滿足： VV，E E，則稱G為G的子圖。,9,頂點(diǎn)的度 無向圖中，頂點(diǎn)的度為與每個(gè)頂點(diǎn)相連的邊數(shù)。 有向圖中，頂點(diǎn)的度分成入度與出度。 入度：以該頂點(diǎn)為頭的弧的數(shù)目。 出度：以該頂點(diǎn)為尾的弧的數(shù)目。,10,路徑：路徑是頂點(diǎn)的序列V=Vi,0,Vi,1,Vi,n，滿足 (Vi,j-1,Vi,j)E 或 E，(1j n)。 路徑長度：沿路徑邊的數(shù)目或沿路徑各邊權(quán)值之和。 回路：第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。 簡(jiǎn)單路徑

4、：序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑叫 簡(jiǎn)單回路：除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余 頂點(diǎn)不重復(fù)出現(xiàn)的回路。,路徑：1，2，3，5，6，3 路徑長度：5 簡(jiǎn)單路徑：1，2，3，5 回路：1，2，3，5，6，3，1 簡(jiǎn)單回路：3，5，6，3,11,路徑：1，2，5，7，6，5，2，3 路徑長度：7 簡(jiǎn)單路徑：1，2，5，7，6 回路：1，2，5，7，6，5，2，1 簡(jiǎn)單回路：1，2，3，1,12,連通：從頂點(diǎn)V到頂點(diǎn)W有路徑，則說V和W是連通的。 連通圖：圖中任意兩個(gè)頂點(diǎn)都是連通的圖。,13,連通分量：非連通圖的每一個(gè)連通部分。 強(qiáng)連通圖：有向圖中，如果對(duì)每一對(duì)Vi,Vj V, ViVj,從Vi到Vj

5、 和從Vj到 Vi都存在路徑，則稱G是強(qiáng)連通圖。,14,7.2 圖的存儲(chǔ)表示,一、圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示,二、圖的鄰接表存儲(chǔ)表示,三、有向圖的十字鏈表存儲(chǔ)表示,四、無向圖的鄰接多重表存儲(chǔ)表示,15,Aij=,0 (i,j)VR,1 (i,j)VR,圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示,定義:矩陣的元素為,特點(diǎn)：對(duì)稱矩陣,頂點(diǎn)的度數(shù),FirstAdjVex(G, v);,NextAdjVex(G, v, w);,如何求?,A B C D E F,A B C D E F,16,從無向圖的鄰接矩陣可以得出如下結(jié)論,（1）矩陣是對(duì)稱的，可壓縮存儲(chǔ)（上（下）三角）; （2）第i行或第i 列中1的個(gè)數(shù)為頂點(diǎn)

6、i 的度; （3）矩陣中1的個(gè)數(shù)的一半為圖中邊的數(shù)目; （4）很容易判斷頂點(diǎn)i 和頂點(diǎn)j之間是否有邊相連(看矩陣中i行j列值是否為1)。,17,有向圖的鄰接矩陣,從有向圖的鄰接矩陣可以得出如下結(jié)論,（1） 矩陣不一定是對(duì)稱的; （2） 第i 行中1的個(gè)數(shù)為頂點(diǎn)i 的出度; （3） 第i列中1的個(gè)數(shù)為頂點(diǎn) i的入度; （4） 矩陣中1的個(gè)數(shù)為圖中弧的數(shù)目; （5） 很容易判斷頂點(diǎn)i 和頂點(diǎn)j 是否有弧相連.,A B C D E,A B C D E,18,網(wǎng)的鄰接矩陣表示,類似地可以定義網(wǎng)的鄰接矩陣為： wij 若（i,j）E(G)或i,jE(G) 其它情形,Aij=,1 2 3 4 5,1 2

7、3 4 5,19,const MAX_VERTEX_NUM = 20;/ 最大頂點(diǎn)個(gè)數(shù)typedef enum DG, DN, AG, AN GraphKind; / 類型標(biāo)志有向圖,有向網(wǎng),無向圖,無向網(wǎng)typedef struct ArcCell / 弧的定義 VRType adj; / VRType是頂點(diǎn)關(guān)系類型。/ 對(duì)無權(quán)圖，用1或0表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類型。InfoType *info; / 該弧相關(guān)信息的指針 AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct / 圖的定義VertexType vexsMAX_VERT

8、EX_NUM; / 頂點(diǎn)信息AdjMatrix arcs; / 表示頂點(diǎn)之間關(guān)系的二維數(shù)組int vexnum, arcnum; / 圖的當(dāng)前頂點(diǎn)數(shù)和弧(邊)數(shù)GraphKind kind; / 圖的種類標(biāo)志 MGraph;,圖的C語言描述,20,容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（弧）、找頂點(diǎn)的鄰接點(diǎn)等等。 n個(gè)頂點(diǎn)需要n*n個(gè)單元存儲(chǔ)邊(弧);空間效率為O(n2)。,鄰接矩陣存儲(chǔ)方式的優(yōu)點(diǎn)：,鄰接矩陣存儲(chǔ)方式缺點(diǎn)：,21,圖的鄰接表存儲(chǔ)表示,頂點(diǎn)的度數(shù),FirstAdjVex(G, v);,NextAdjVex(G, v, w);,如何求?,例,1,2,3,4,a,c

9、,d,b,data,firstarc,adjvex,next,5,e,22,有向圖的鄰接表,頂點(diǎn)的出度和入度,FirstAdjVex(G, v);,NextAdjVex(G, v, w);,如何求?,23,有向圖的逆鄰接表,在有向圖的鄰接表中，對(duì)每個(gè)頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧。,24,typedef struct ArcNode int adjvex; / 該弧所指向的頂點(diǎn)的下標(biāo) struct ArcNode *nextarc; / 指向下一條弧的指針 InfoType *info; / 該弧相關(guān)信息的指針 ArcNode;,adjvex nextarc info,弧的結(jié)點(diǎn)結(jié)構(gòu),typede

10、f struct VNode VertexType data; / 頂點(diǎn)信息 ArcNode *firstarc; / 指向第一條依附該頂點(diǎn)的弧 VNode, AdjListMAX_VERTEX_NUM;,data firstarc,頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu),25,typedef struct AdjList vertices; int vexnum, arcnum; int kind; / 圖的種類標(biāo)志 ALGraph;,圖的結(jié)構(gòu)定義,26,已知某網(wǎng)的鄰接（出邊）表，請(qǐng)畫出該網(wǎng)絡(luò)。,80,64,1,2,5,當(dāng)鄰接表的存儲(chǔ)結(jié)構(gòu)形成后，圖便唯一確定！,27,討論：鄰接表與鄰接矩陣有什么異同之處？,1. 聯(lián)

11、系：鄰接表中每個(gè)鏈表對(duì)應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。 2. 區(qū)別： 對(duì)于任一確定的無向圖，鄰接矩陣是唯一的（行列號(hào)與頂點(diǎn)編號(hào)一致），但鄰接表不唯一（鏈接次序與頂點(diǎn)編號(hào)無關(guān)）。 鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。 3. 用途：鄰接矩陣多用于稠密圖的存儲(chǔ)（e接近n(n-1)/2)；而鄰接表多用于稀疏圖的存儲(chǔ)（en2),28,有向圖的十字鏈表表示法,29,typedef struct / 十字鏈表結(jié)構(gòu)定義VexNode xlistMAX_VERTEX_NUM; / 表頭向量int vexnum, arcnum; / 有向圖的當(dāng)前頂點(diǎn)

12、數(shù)和弧數(shù)GraphKind kind; / 圖的種類標(biāo)志 OLGraph;,30,31,頂點(diǎn)結(jié)點(diǎn)： typedef struct dnode int data; /存與頂點(diǎn)有關(guān)的信息 struct node *firstedge; /指向第一條依附于該頂點(diǎn)的邊 vexnode;,邊結(jié)點(diǎn)： typedef struct node int mark; / 訪問標(biāo)記域 int ivex, jvex; /該邊依附的兩個(gè)頂點(diǎn)在表頭數(shù)組中位置 struct node *ilink, *jlink; /分別指向依附于ivex和jvex的下一條邊 EgeNode;,無向圖的鄰接多重表表示法,32,typede

13、f struct / 多重鏈表結(jié)構(gòu)定義VexNode adjmulistMAX_VERTEX_NUM;int vexnum, edgenum; / 無向圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù)GraphKind kind; / 圖的種類標(biāo)志 AMLGraph;,33,34,各種存儲(chǔ)結(jié)構(gòu)的適用類型,數(shù)組： 有向圖和無向圖 鄰接表（逆鄰接表）：有向圖和無向圖 十字鏈表： 有向圖 鄰接多重表： 無向圖,35,7.3 圖的遍歷,從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪問一次的過程。,深度優(yōu)先搜索,廣度優(yōu)先搜索,遍歷應(yīng)用舉例,36,1、深度優(yōu)先遍歷(DFS) 方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問

14、此頂點(diǎn)；然后依次從V0的未被訪問的鄰接點(diǎn)出發(fā)，深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止。,37,38,深度遍歷：V1,V3 ,V7 ,V6 ,V2 ,V5 ,V8 ,V4,39,深度優(yōu)先遍歷算法：遞歸算法,40,深度遍歷：V1,V3 ,V7 ,V6 ,V2 ,V4 ,V8 ,V5,void DFS(Graph G, int v) / 從頂點(diǎn)v出發(fā)，深度優(yōu)先搜索遍歷圖 G visitedv = TRUE; VisitFunc (v); for(w=FirstAdjVex(G,

15、 v); w!=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS(G, w); / 對(duì)v的尚未訪問的鄰接頂點(diǎn)w / 遞歸調(diào)用DFS / DFS,問題？,按該存儲(chǔ)結(jié)構(gòu)得到的遍歷次序是否唯一？,41,void DFSTraverse(ALGraph G) / 對(duì)以鄰接表表示的圖G作深度優(yōu)先遍歷bool visitedG.vexnum; / 附設(shè)訪問標(biāo)識(shí)數(shù)組for (v=0; vG.vexnum; +v)visitedv = FALSE; / 訪問標(biāo)識(shí)數(shù)組初始化for (v=0; vG.vexnum; +v) if (!visitedv) DFS(G, v); /

16、對(duì)尚未訪問的頂點(diǎn)調(diào)用DFS,42,廣度優(yōu)先搜索遍歷圖,方法：從圖的某一頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)后，依次訪問V0的各個(gè)未曾訪問過的鄰接點(diǎn)；然后分別從這些鄰接點(diǎn)出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到；若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未被訪問的頂點(diǎn)作起點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問為止,廣度遍歷： V1 V2 V3 V4 V5 V6 V7 V8,43,廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8,廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8,廣度遍歷：V1 V2 V3 V4 V6 V7 V8 V5,44,45,46,47,vo

17、id BFSTraverse(Graph G, Status (*Visit)(int v) for (v=0; vG.vexnum; +v) visitedv = FALSE; /初始化訪問標(biāo)志 InitQueue(Q); / 置空的輔助隊(duì)列Q for ( v=0; vG.vexnum; +v ) if ( !visitedv) / v 尚未訪問 visitedu = TRUE; Visit(u); / 訪問u EnQueue(Q, v); / v入隊(duì)列 / BFSTraverse,while (!QueueEmpty(Q) DeQueue(Q, u); / 隊(duì)頭元素出隊(duì)并置為u for(w

18、=FirstAdjVex(G, u); w!=0; w=NextAdjVex(G,u,w) if ( ! visitedw) visitedw=TRUE; Visit(w); EnQueue(Q, w); / 訪問的頂點(diǎn)w入隊(duì)列 / if / while ,48,定義:所有頂點(diǎn)均由邊連接在一起，但不存在回路的圖。 深度優(yōu)先 生成樹與廣度優(yōu)先 生成樹。 生成森林：非連通圖每個(gè)連通分量的生成樹一起組成非連通圖的生成森林。 說明 （1）一個(gè)圖可以有許多棵不同的生成樹 （2）所有生成樹具有以下共同特點(diǎn)： 生成樹的頂點(diǎn)個(gè)數(shù)與圖的頂點(diǎn)個(gè)數(shù)相同 生成樹是圖的極小連通子圖 一個(gè)有n個(gè)頂點(diǎn)的連通圖的生成樹有n-

19、1條邊 生成樹中任意兩個(gè)頂點(diǎn)間的路徑是唯一的 在生成樹中再加一條邊必然形成回路 含n個(gè)頂點(diǎn)n-1條邊的圖不一定是生成樹,生成樹,49,深度遍歷：V1 V2 V4 V8 V5 V3 V6 V7,廣度遍歷：V1 V2 V3 V4 V5 V6 V7 V8,深度優(yōu)先生成樹,廣度優(yōu)先生成樹,50,51,問題提出： 要在n個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)，頂點(diǎn)表示城市，權(quán)表示城市間建立通信線路所需花費(fèi)代價(jià)。希望找到一棵生成樹，它的每條邊上的權(quán)值之和（即建立該通信網(wǎng)所需花費(fèi)的總代價(jià)）最小。 問題分析： n個(gè)城市間，最多可設(shè)置n(n-1)/2條線路 n個(gè)城市間建立通信網(wǎng)，只需n-1條線路 問題轉(zhuǎn)化為： 如何在可能的線路

20、中選擇n-1條，能把所有城市（頂點(diǎn)）均連起來，且總耗費(fèi)（各邊權(quán)值之和）最小。,最小生成樹,52,方法一：普里姆(Prim)算法 算法思想：設(shè)N=(V,E)是連通網(wǎng)，TE是N上最小生成樹中邊的集合。 (1)初始令U=u0,(u0V), TE= ; (2)在所有uU,vV-U的邊(u,v)E中，找一條代價(jià)最小的邊(u0,v0)并入集合TE，同時(shí)v0并入U(xiǎn); (3)重復(fù)上述操作直至U=V為止，則T=(V,TE)為N的最小生成樹。 算法實(shí)現(xiàn)：圖用鄰接矩陣表示 算法評(píng)價(jià)：T(n)=O(n),構(gòu)造最小生成樹方法,53,1,從V1開始構(gòu)造，即U=V1,54,struct VertexType adjvex;

21、 / U集合中的頂點(diǎn)序號(hào) VRType lowcost; /和頂點(diǎn)集U中頂點(diǎn)相連接的最小代價(jià) closedgeMAX_VERTEX_NUM;,設(shè)置一個(gè)輔助數(shù)組，對(duì)當(dāng)前VU集中的每個(gè)頂點(diǎn)，記錄和頂點(diǎn)集U中頂點(diǎn)相連接的代價(jià)最小的邊：,55,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,7,a,a,a,19,14,18,14,例如:,e,12,e,e,8,16,8,d,3,d,d,7,21,3,c,5,5,a,b,c,d,e,f,g,a,e,b,c,d,f,g,a,e,d,b,c, f,g,a,e,d,c,b, f,g,a,e,d,c,b,f,

22、g,a b c d e f g,g,f,56,const MAX_VERTEX_NUM = 20;/ 最大頂點(diǎn)個(gè)數(shù)typedef enum DG, DN, AG, AN GraphKind; / 類型標(biāo)志有向圖,有向網(wǎng),無向圖,無向網(wǎng)typedef struct ArcCell / 弧的定義 VRType adj; / VRType是頂點(diǎn)關(guān)系類型。/ 對(duì)無權(quán)圖，用1或0表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類型。InfoType *info; / 該弧相關(guān)信息的指針 AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct / 圖的定義VertexTyp

23、e vexsMAX_VERTEX_NUM; / 頂點(diǎn)信息AdjMatrix arcs; / 表示頂點(diǎn)之間關(guān)系的二維數(shù)組int vexnum, arcnum; / 圖的當(dāng)前頂點(diǎn)數(shù)和弧(邊)數(shù)GraphKind kind; / 圖的種類標(biāo)志 MGraph;,圖的鄰接矩陣存儲(chǔ)表示的C語言描述,57,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,

24、 G.arcskj.adj ; closedgek.lowcost = 0; / 初始，Uu for (i=1; iG.vexnum; +i) k = minimum(closedge); / 求出加入生成樹的下一個(gè)頂點(diǎn)(k) printf(closedgek.adjvex, G.vexsk); / 輸出生成樹上一條邊 closedgek.lowcost = 0; / 第k頂點(diǎn)并入U(xiǎn)集 for (j=0; jG.vexnum; +j) /修改closedge數(shù)組 if (G.arcskj.adj closedgej.lowcost) closedgej = G.vexsk, G.arcskj.

25、adj ; ,58,方法二：克魯斯卡爾(Kruskal)算法 算法思想：設(shè)連通網(wǎng)N=(V,E)，令最小生成樹 （1）初始狀態(tài)為只有n個(gè)頂點(diǎn)而無邊的非連通圖T=(V,)，每個(gè)頂點(diǎn)自成一個(gè)連通分量； （2）在E中選取代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中；否則，舍去此邊，選取下一條代價(jià)最小的邊； （3）依此類推，直至T中所有頂點(diǎn)都在同一連通分量上為止。,59,（0）用頂點(diǎn)數(shù)組和邊數(shù)組存放頂點(diǎn)和邊信息 （1）初始時(shí)，令每個(gè)頂點(diǎn)的jihe互不相同；每個(gè)邊的flag為0 （2）選出權(quán)值最小且flag為0的邊 （3）若該邊依附的兩個(gè)頂點(diǎn)的jihe 值不同，即非連通，則令

26、 該邊的flag=1, 選中該邊；再令該邊依附的兩頂點(diǎn)的jihe 以及兩集合中所有頂點(diǎn)的jihe 相同 若該邊依附的兩個(gè)頂點(diǎn)的jihe 值相同，即連通，則令該 邊的flag=2, 即舍去該邊 （4）重復(fù)上述步驟，直到選出n-1條邊為止,頂點(diǎn)結(jié)點(diǎn)： typedef struct int data; /頂點(diǎn)信息 int jihe; VEX;,邊結(jié)點(diǎn)： typedef struct int vexh, vext; /邊依附的兩頂點(diǎn) int weight; /邊的權(quán)值 int flag; /標(biāo)志域 EDGE;,算法實(shí)現(xiàn),60,1,1,1,1,1,4,2,1,1,1,2,2,2,2,2,算法描述,2,6

27、1,普里姆算法,克魯斯卡爾算法,時(shí)間復(fù)雜度,O(n2),O(eloge),稠密圖,稀疏圖,算法名,適應(yīng)范圍,兩種算法的比較,62,問題提出： 學(xué)生選修課程問題 頂點(diǎn)表示課程，有向弧表示先決條件，若課程i是課程j的先決條件，則圖中有弧，學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無矛盾、順利地完成學(xué)業(yè)，這就牽涉到拓?fù)渑判颉?拓?fù)渑判?63,定義 AOV網(wǎng)：用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)(Activity On Vertex network)，簡(jiǎn)稱AOV網(wǎng)。 若是圖中有向邊，則vi是vj的直接前驅(qū)；vj是vi的直接后繼。 AOV網(wǎng)中不允許有回路，否則意味著某項(xiàng)活動(dòng)以自己

28、為先決條件。 拓?fù)渑判颍喊袮OV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間的優(yōu)先關(guān)系排列成一個(gè)線性序列的過程。 檢測(cè)AOV網(wǎng)中是否存在環(huán)方法：對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄?，則該AOV網(wǎng)必定不存在環(huán)。,64,拓?fù)渑判虻姆椒?（1）在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之； （2）從圖中刪除該頂點(diǎn)和所有以它為尾的弧； （3）重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點(diǎn)為止,65,拓?fù)湫蛄校篊1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8 或 ：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8,注意

29、：一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏?66,（1）先選擇沒有前驅(qū)的頂點(diǎn)C1，刪除C1和所有以它為尾的弧。,67,（2）選擇沒有前驅(qū)的頂點(diǎn)C2，刪除C2和所有以它為尾的弧。 拓?fù)湫蛄校篊1-C2,（3）選擇沒有前驅(qū)的頂點(diǎn)C3，刪除C3和所有以它為尾的弧。 拓?fù)湫蛄校篊1-C2-C3,68,C4,C5,（4）選擇沒有前驅(qū)的頂點(diǎn)C4，刪除C4和所有以它為尾的弧。 拓?fù)湫蛄校篊1-C2-C3-C4,（5）選擇沒有前驅(qū)的頂點(diǎn)C5，刪除C5和所有以它為尾的弧。 拓?fù)湫蛄校篊1-C2-C3-C4C5,69,70,71,那么如何進(jìn)行拓?fù)渑判?？步驟如下： （1） 在AOV網(wǎng)中選擇一個(gè)沒有前驅(qū)的頂點(diǎn)并輸出；（2）

30、從AOV網(wǎng)中刪除該頂點(diǎn)以及從它出發(fā)的弧；重復(fù)以上兩步直至AOV網(wǎng)變空（即已輸出所有頂點(diǎn)） 或者剩余子圖中不存在沒有前驅(qū)的頂點(diǎn)。 后一種情況則說明該AOV網(wǎng)中含有向環(huán)。,如右所示AOV網(wǎng)的拓?fù)渑判虻倪^程如動(dòng)畫所示。,圖中存在一個(gè)有向環(huán)，則在拓?fù)渑判蜉敵鲰旤c(diǎn)c之后就 找不到?jīng)]有前驅(qū)的頂點(diǎn)了,沒有前驅(qū)的頂點(diǎn) 入度為零的頂點(diǎn),刪除頂點(diǎn)及以它為尾的弧 弧頭頂點(diǎn)的入度減1,72,算法實(shí)現(xiàn) （1）以鄰接表作存儲(chǔ)結(jié)構(gòu); （2）把鄰接表中所有入度為0的頂點(diǎn)進(jìn)棧,便于查詢; （3）棧非空時(shí)，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進(jìn)棧; (4)重復(fù)上述操作直至

31、棧空為止。若棧空時(shí)輸出的頂點(diǎn)個(gè)數(shù)不是n，則有向圖有環(huán)；否則，拓?fù)渑判蛲戤?73,算法描述,1,6,74,輸出序列：6,75,輸出序列：6,76,輸出序列：6,77,輸出序列：6,78,輸出序列：6,79,輸出序列：6,80,輸出序列：6 1,81,輸出序列：6 1,82,輸出序列：6 1,4,83,輸出序列：6 1,4,84,輸出序列：6 1,4,85,輸出序列：6 1,4,3,86,輸出序列：6 1,4,3,87,輸出序列：6 1,4,3,88,輸出序列：6 1,4,3,89,輸出序列：6 1,4,3,90,輸出序列：6 1 3,4,3,91,輸出序列：6 1 3,4,92,輸出序列：6 1

32、 3,4,93,輸出序列：6 1 3,4,94,輸出序列：6 1 3,4,2,95,輸出序列：6 1 3,4,2,96,輸出序列：6 1 3,4,2,97,輸出序列：6 1 3 2,4,2,98,輸出序列：6 1 3 2,4,99,輸出序列：6 1 3 2 4,4,100,輸出序列：6 1 3 2 4,101,輸出序列：6 1 3 2 4,5,102,輸出序列：6 1 3 2 4,5,103,輸出序列：6 1 3 2 4 5,5,104,輸出序列：6 1 3 2 4 5,105,CountInDegree(G,indegree); /對(duì)各頂點(diǎn)求入度 InitStack(S); for ( i=

33、0; iG.vexnum; +i) if (!indegreei) Push(S, i); /入度為零的頂點(diǎn)入棧 count=0; /對(duì)輸出頂點(diǎn)計(jì)數(shù) while (!EmptyStack(S) Pop(S, v); +count; printf(v); for (w=FirstAdj(G,v); w!=0; w=NextAdj(G,v,w) -indegree(w); / 弧頭頂點(diǎn)的入度減一 if (!indegreew) Push(S, w); /新產(chǎn)生的入度為零的頂點(diǎn)入棧 if (countG.vexnum) printf(“圖中有回路”) Else return OK,106,關(guān)鍵路徑

34、問題提出: 把工程計(jì)劃表示為有向圖，用頂點(diǎn)表示事件，弧表示活動(dòng)；每個(gè)事件表示在它之前的活動(dòng)已完成，在它之后的活動(dòng)可以開始。 例 設(shè)一個(gè)工程有11項(xiàng)活動(dòng)，9個(gè)事件。 事件 V1表示整個(gè)工程開始，事件V9表示整個(gè)工程結(jié)束。 問題：（1）完成整項(xiàng)工程至少需要多少時(shí)間？ （2）哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？,107,如何求關(guān)鍵活動(dòng)？,ve(j) =事件Vj的最早發(fā)生時(shí)間(從源點(diǎn)到頂點(diǎn)j的最長路徑長度),vl(j) =事件Vj的最遲發(fā)生時(shí)間 e(i)表示活動(dòng)ai的最早開始時(shí)間 l(i)表示活動(dòng)ai的最遲開始時(shí)間 關(guān)鍵活動(dòng)關(guān)鍵路徑上的活動(dòng)叫，即l(i)=e(i)的活動(dòng),源點(diǎn),匯點(diǎn),108,設(shè)活動(dòng)ai用弧表

35、示，其持續(xù)時(shí)間記為：dut() 則有： （1）e(i)=Ve(j) （2）l(i)=Vl(k)-dut(),如何求Ve(j)和Vl(j)？,(2)從Vl(n)=Ve(n)開始向后遞推,如何找e(i)=l(i)的關(guān)鍵活動(dòng)？,(1)從Ve(1)=0開始向前遞推,109,求關(guān)鍵路徑步驟 求Ve(i) 求Vl(j) 求e(i) (e(i)=Ve(j) 求l(i) (Vl(k)-dut() 計(jì)算l(i)-e(i),V1 V2 V3 V4 V5 V6 V7 V8 V9,0 6 4 5 7 7 16 14 18,0 6 6 8 7 10 16 14 18,a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11, ,110,問題：從某頂