《數(shù)據(jù)結(jié)構(gòu) 圖PPT課件》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結(jié)構(gòu) 圖PPT課件（142頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、7.1 圖的定義和術(shù)語1第1頁/共142頁2 7.1 圖的定義和術(shù)語 圖(Graph) 是一種較線性結(jié)構(gòu)和樹更為復雜的數(shù)據(jù)結(jié)構(gòu)。 線性表中，一個元素只能和其直接前驅(qū)或直接后繼相關； 在樹中，一個結(jié)點可以和其下一層的所有孩子結(jié)點相關，以及上一層的雙親結(jié)點相關，但不能和其他的任何結(jié)點直接相關； 而對于圖來說，圖中任意兩個結(jié)點之間都可以直接相關。BCADE姓 名學 號 性 別年 齡 健康情況王小林790631男 18 健康陳 紅790632女 20 一般劉建平790633男 21 健康張立立790634男 17 神經(jīng)衰弱 . . .第2頁/共142頁 圖的用途極其廣泛，已滲入到語言學、邏輯學、物理、

2、化學、電訊工程、計算機科學以及數(shù)學等其他分支學科當中。 在本課程當中，我們主要討論如何在計算機上實現(xiàn)圖的操作，因此主要學習圖的存儲結(jié)構(gòu)以及圖的若干操作的實現(xiàn)。3第3頁/共142頁47.1 圖的定義和術(shù)語 圖(graph) G由兩個集合V和E組成，記為G = (V, E) V是頂點的有窮非空集合； E是邊的集合，邊是V中頂點的偶對。 E可以是空集，若E為空，則G中只有頂點沒有邊。 在圖中，數(shù)據(jù)元素通常稱為頂點(vertex)。第4頁/共142頁57.1 圖的定義和術(shù)語 若頂點之間的偶對是有方向的，稱此圖為有向圖(digraph); 有方向偶對用尖括號括起來，并稱之為弧(arc)。如v, wV，E

3、，則是有向圖中從頂點v到頂點w的一條弧，v是弧尾(tail)(始點)，w是弧頭(head)(終點)。ABCD有向圖有向圖 G1第5頁/共142頁 若頂點之間的偶對是無方向的，稱此圖為無向圖(undigraph). 無方向偶對用圓括括起來，通常稱之為邊(edge)。如x, yV，(x, y)E，則(x, y)是無向圖中頂點x和頂點y之間的一條邊。6ABCDE無向圖無向圖 G2第6頁/共142頁7 7.1 圖的定義和術(shù)語ABCD有向圖有向圖 G1 結(jié)點結(jié)點 或或 頂點：頂點：AB 有向邊有向邊（弧）（?。?弧尾或初始結(jié)點、弧尾或初始結(jié)點、 弧頭或終止結(jié)點弧頭或終止結(jié)點AB 有向圖：有向圖：G1

4、=（V1，A1 ） V1 = A,B,C,D A1 = , , , ABCDE無向圖無向圖 G2 結(jié)點結(jié)點 或或 頂點：頂點：AB 無向圖：無向圖：G2 =（V2，A2 ） V2 = A,B,C,D,E A2 = (A,B), (A,C), (B,D), (B,E), (C,E), (D,E) 無向邊或無向邊或邊邊AB第7頁/共142頁8 7.1 圖的定義和術(shù)語 在以后的討論中，不考慮頂點到其自身的弧或邊，那么： 對于有n個頂點的無向圖，邊的最大數(shù)目為:n(n-1)/2 對于n個頂點的有向圖，弧的最大數(shù)目為:n(n-1)第8頁/共142頁97.1 圖的定義和術(shù)語幾種圖的定義：完全圖(Compl

5、eted Graph)：有n(n-1)/2條邊的無向圖。有向完全圖：有n(n-1)條弧的有向圖。稀疏圖(Sparse Graph)：有很少條邊或弧的圖(e=nlogn)第9頁/共142頁107.1 圖的定義和術(shù)語有時圖的邊或弧附有相關的數(shù)值，這種數(shù)值稱為權(quán)(weight)。這些權(quán)可以表示一個頂點到另一個頂點的距離，或時間耗費、開銷耗費等。所以，權(quán)是與圖的邊或弧相關的數(shù)。鄰接點：對于無向圖GG(V,E)(V,E)，如果邊(v, v) E，則稱頂點v和v互為鄰接點；邊(v, v)依附于頂點v和v，或者說，邊(v, v)和頂點v和v相關聯(lián)。第10頁/共142頁117.1 圖的定義和術(shù)語每條邊或弧都帶

6、權(quán)的圖又稱為網(wǎng)。第11頁/共142頁12 7.1 圖的定義和術(shù)語無向圖頂點的度(degree) ：和該頂點相關聯(lián)的邊的數(shù)目，記為TD(v)。有向圖頂點的出度( outdegree) ：以該頂點為弧尾(起點）的弧的數(shù)目，記為OD(v) 。有向圖頂點的入度（indegree）：以該頂點為弧頭（終點）的弧的數(shù)目，記為ID(v) 。有向圖頂點的度: TD(v)=ID(v)+OD(v)一般地，對于無向圖和有向圖，如果頂點vi的度記為TD(vi)，那么一個有n個項點，e條邊或弧的圖，niivTDe12/ )( 圖論中，有一個十分簡單但有很有用的關于頂點的度的定理，即握手定理：第12頁/共142頁137.1

7、 圖的定義和術(shù)語 路徑：在圖中從頂點v v到頂點v v所經(jīng)過的所有頂點的序列。有向圖的路徑也是有向的。 路徑長度：路徑上的邊或弧的數(shù)目。 簡單路徑：序列中頂點不重復出現(xiàn)的路徑。 回路或環(huán)：序列中第一個頂點和最后一個頂點相同的路徑。 簡單回路或環(huán)：除第一個頂點和最后一個頂點相同外，其余頂點不重復出現(xiàn)的路徑。第13頁/共142頁14 7.1 圖的定義和術(shù)語子圖：設兩個圖G(V, E)和G=(V,E)，如果V V且E E，則稱G為G的子圖(Subgraph)。AACDACABCD有向圖有向圖G1的子圖的子圖ABCD有向圖有向圖 G1無無向圖向圖 G2ABCDEABDEAABCDABCDE無向圖無向圖

8、G2的子圖的子圖第14頁/共142頁15 7.1 圖的定義和術(shù)語連通：在無向圖中，如果從v到v存在路徑，則稱v和v是連通的。連通圖：無向圖G中如果任意兩個頂點vi,vj之間都是連通的。連通分量：無向圖中的極大連通子圖。強連通圖：在有向圖G中，如果對于每一對vi,vj V, vi vj，從vi到vj和從vj到vi都存在路徑，則稱G是強連通圖。強連通分量：有向圖中的極大強連通子圖?！皹O大”是指在保證子圖和連通的條件下無法再擴大該子圖第15頁/共142頁167.1 圖的定義和術(shù)語ABCDEFGIJLHMK無向圖無向圖GABCDEHMFGIJLK無向圖無向圖GG的三個的三個連通分量連通分量( (無向圖

9、無向圖中的中的極大連通子圖極大連通子圖)第16頁/共142頁17第17頁/共142頁18 7.1 圖的定義和術(shù)語有向圖有向圖G的兩個強連通分量的兩個強連通分量有向圖有向圖GABCDBACD第18頁/共142頁197.1 圖的定義和術(shù)語u生成樹：圖的一個極小連通子圖，包含圖的所有 n 個結(jié)點，但只含圖的n-1n-1 條邊。在生成樹中添加一條邊之后，必定會形成回路或環(huán)，因為這條邊使得它依附的那兩個頂點之間有了第二條路徑。u區(qū)別概念：無向圖中的極大連通子圖稱為連通分量。ABCDEHM無向圖無向圖G ABCDEHM無向圖無向圖G的生成樹的生成樹 第19頁/共142頁20n一個連通圖的生成樹，是含有該連

10、通圖的全部頂點的一個極小連通子圖。若連通圖G的頂點個數(shù)為n，則G的生成樹的頂點個數(shù)也為n，邊數(shù)為n-1，邊數(shù)多于n-1就不是極小連通子圖，少于n-1則不連通了。下圖(a)是個連通圖，圖(b)和(c)是它的兩個生成樹。第20頁/共142頁21 7.1 圖的定義和術(shù)語u如果一個有向圖恰有一個頂點入度為0，其余頂點入度均為1，該圖必定是一棵有向樹。所有樹可以看成是圖的特例。u有向圖的生成森林：由若干棵有向樹組成，含有圖中全部頂點，但只有構(gòu)成若干棵不相交的有向樹的弧。有向圖有向圖G的的生成森林生成森林有向圖有向圖GABFECDAFBEDC第21頁/共142頁7.2 圖的存儲結(jié)構(gòu)22第22頁/共142頁

11、23 7.2 圖的存儲結(jié)構(gòu)圖存儲的特殊性： 頂點之間的關系無法用他們在內(nèi)存中的存儲位置來表示。 用多重鏈表來表示圖是自然的事情，它用一個由一個數(shù)據(jù)域和多個指針域組成的結(jié)點表示圖中的一個頂點。其中數(shù)據(jù)域存放該頂點的信息，指針域存放指向其鄰接點的地址。 常用的存儲方法有：鄰接矩陣表示法鄰接表表示法十字鏈表表示法鄰接多重表表示法第23頁/共142頁24 7.2 圖的存儲結(jié)構(gòu)7.2.1 數(shù)組表示法（鄰接矩陣表示法） 圖需要存儲的信息：頂點和弧（或邊）。 圖的數(shù)組表示法：用兩個數(shù)組分別存放圖中頂點的信息（數(shù)據(jù)元素）和圖中弧或邊的信息（數(shù)據(jù)元素之間的關系）。 頂點信息的存儲方法：一維數(shù)組頂點類型：整型、字

12、符型等 弧或邊信息的存儲方法：二維數(shù)組即鄰接矩陣弧或邊的信息類型：無權(quán)圖: 0或1；有權(quán)圖（網(wǎng)）: 權(quán)值類型第24頁/共142頁25 7.2 圖的存儲結(jié)構(gòu)7.2.1 數(shù)組表示法 有向圖的鄰接矩陣有向圖的鄰接矩陣 設有向圖具有設有向圖具有 n n 個頂點，則用個頂點，則用 n n 行行 n n 列的矩列的矩陣陣 A A 表示該有向圖；表示該有向圖； 并且并且 Aij = 1Aij = 1，如果頂點，如果頂點i i 至至 j j 有一條??；有一條弧； Aij = 0Aij = 0，如果頂點，如果頂點 i i 至至 j j 沒有一條弧。沒有一條弧。 注意注意：Aii = 0Aii = 0。頂點頂點

13、i i 的出度的出度: : 第第i i 行之和行之和。 頂點頂點 j j 的入度的入度: : 第第j j 列之和列之和。ABCD0 1 1 00 0 0 00 0 0 11 0 0 0表示成右圖矩陣第25頁/共142頁26 7.2 圖的存儲結(jié)構(gòu)7.2.1 數(shù)組表示法 無向圖的鄰接矩陣無向圖的鄰接矩陣 設無向圖具有設無向圖具有 n n 個頂點，則用個頂點，則用 n n 行行 n n 列的矩陣列的矩陣 A A 表示該無向圖；表示該無向圖； 并且并且 Aij = 1Aij = 1，如果頂點，如果頂點i i 至至 j j 有一條邊；有一條邊； Aij = 0Aij = 0，如果頂點，如果頂點i i 至

14、至 j j 沒有一條邊。沒有一條邊。 0 1 1 0 01 0 0 1 11 0 0 0 10 1 0 0 10 1 1 1 0ABCDE表示成右圖矩陣無向圖的鄰接矩陣是對稱矩陣，有向圖的鄰接矩陣不一定是對稱矩陣。第26頁/共142頁277.2 圖的存儲結(jié)構(gòu)7.2.1 數(shù)組表示法：無向圖的鄰接矩陣無向圖的鄰接矩陣 注意注意: : Aii = 0Aii = 0 無向圖無向圖頂點頂點i i 的度的度: : 第第i i行或行或i i列之和列之和( (因為是對稱矩陣因為是對稱矩陣) )。 TD(v TD(vi i) )= 無向圖的總邊數(shù)無向圖的總邊數(shù)等于該矩陣上三角或下三角元素之和。等于該矩陣上三角或

15、下三角元素之和。第27頁/共142頁28 7.2 圖的存儲結(jié)構(gòu)7.2.1 數(shù)組表示法 有向網(wǎng)有向網(wǎng)的鄰接矩陣的鄰接矩陣設網(wǎng)具有設網(wǎng)具有 n n 個頂點，則用個頂點，則用 n n 行行 n n 列的矩陣列的矩陣 A A 表示表示該網(wǎng)；并且該網(wǎng)；并且 Aij = a Aij = a ，如果，如果i i 至至 j j 有一條弧且它的權(quán)值為有一條弧且它的權(quán)值為a a； Aij = Aij = 空空 或其它標或其它標 志，如果志，如果 i i 至至 j j 沒有一條沒有一條弧?；?。 $ a b $ $ $ $ b $ $ $ ba $ a $ ABCDaabbba表示成右圖矩陣第28頁/共142頁29

16、7.2 圖的存儲結(jié)構(gòu)7.2.1 數(shù)組表示法 鄰接矩陣的數(shù)據(jù)結(jié)構(gòu)#define INFINITY INT_MAX/用整型最大值代替用整型最大值代替#define MAX_VERTEX_NUM 20typedef enum DG, DN, UDG, UDN GraphKind;typedef struct ArcCellVRType adj; InfoType *info;/該弧相關信息的指針（可無）該弧相關信息的指針（可無） ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;VRType是頂點關系類型。對無權(quán)圖，用1或表示相鄰否；對帶權(quán)圖，則為權(quán)值類型

17、。VRType，InfoType都是要在主函數(shù)中定義的。有向圖，有向網(wǎng)，無向圖，無向網(wǎng)第29頁/共142頁30 7.2 圖的存儲結(jié)構(gòu)7.2.1 數(shù)組表示法typedef structVertexType vexsMAX_VERTEX_NUM;/頂點頂點向量向量AdjMatrix arcs;/鄰接矩陣int vexnum, arcnum; /圖的當前頂點數(shù)和弧數(shù)GraphKind kind;/圖的種類標志 MGraph; /鄰接矩陣表示的圖鄰接矩陣表示的圖 鄰接矩陣表示法的優(yōu)缺點： 優(yōu)點：各種基本操作都易于實現(xiàn)，很容易確定圖中任意兩個頂點之間是否有邊相連。 缺點：空間浪費嚴重。某些算法時間效率低

18、。有向圖， Kind = 0；有向網(wǎng)， Kind = 1；無向圖，Kind = 2；無向網(wǎng)， Kind = 3。第30頁/共142頁31 7.2 圖的存儲結(jié)構(gòu)7.2.1 數(shù)組表示法Status CreateUDN(MGraph &G) / 創(chuàng)建無向網(wǎng)G scanf(&G.vexnum, &G.arcnum, &IncInfo); / IncInfo為0則各邊不含其它信息for (i = 0; i G.vexnum; +i) scanf(&G.vexsi); / 輸入所有的頂點信息for (i = 0; i G.vexnum; +i)/ 初始化鄰接矩陣 for ( j = 0; jG.vexnu

19、m; +j) G.arcsi j = ( INFINITY, NULL ) ; / ( adj, info )for (k=0; kG.arcnum; +k)/ 輸入所有的邊 scanf(&v1, &v2, &w); / 輸入一條邊依附的兩個頂點和邊上的權(quán)值 i=LocateVex(G, v1); j=LocateVex(G, v2); / 查詢兩個頂點在圖中存儲的位置 G.arcsi j.adj = w; /弧的權(quán)值 if (IncInfo) Input(*G.arcsi j.info); / 輸入邊的相關信息 G.arcs ji = G.arcsi j; / 根據(jù)無向網(wǎng)的對稱性填充矩陣的對

20、稱部分return OK;第31頁/共142頁32 7.2.2 鄰接表表示法 鄰接表（Adjacency List）是圖的一種鏈式存儲結(jié)構(gòu)。對圖中的每個頂點建立一個單鏈表，第i個單鏈表中的結(jié)點表示依附于頂點vi的邊（對有向圖是以頂點vi為尾的弧）。 鄰接表中的每個結(jié)點由三個域組成： 數(shù)據(jù)域info指向存儲和弧或邊相關的信息，如權(quán)值等。 鄰接點域adjvex指示與本條弧或邊依附的另一個頂點的位置 鏈域nextarc指向下一條弧或邊的結(jié)點adjvexnextarcinfo弧或邊結(jié)點弧或邊結(jié)點第32頁/共142頁337.2.2 鄰接表表示法datafirstarc頭結(jié)點頭結(jié)點每個鏈表附設一個每個鏈表

21、附設一個表頭結(jié)點表頭結(jié)點：data存儲頂點vi的名或其他有關的名或其他有關信息firstarc指向依附于該頂點的第一條弧或邊所有表頭結(jié)點通常以順序結(jié)構(gòu)（一維數(shù)組）的形式存儲，以便訪問任一頂點的鏈表。第33頁/共142頁34 7.2 圖的存儲結(jié)構(gòu)7.2.2 鄰接表表示法ABCD有向圖有向圖 G1A0BCD213有向圖有向圖G1的鄰接表的鄰接表0123A2BCD300 有向圖有向圖G1的逆鄰接表的逆鄰接表0123頂點的出度：該頂點所指向的鏈表的結(jié)點總數(shù)。頂點的入度：必須搜索整個鄰接表才能得到。改進：建立逆鄰接表或十字鏈表第34頁/共142頁357.2.2 鄰接表表示法 思考： 若無向圖中有n個頂點

22、、e條邊，則它的鄰接表需要 個頭結(jié)點和 個表結(jié)點。 在邊稀疏的情況下，用鄰接表表示圖比鄰接矩陣節(jié)省存儲空間。n2e第35頁/共142頁36 7.2 圖的存儲結(jié)構(gòu)7.2.2 鄰接表表示法無無向圖向圖 G2ABCDEA4BCD244E31130201無向圖無向圖G2的鄰接表的鄰接表012301234頂點的度頂點的度：為該頂點所指向的鏈表中的結(jié)點總數(shù)。：為該頂點所指向的鏈表中的結(jié)點總數(shù)。六條邊而所有鏈表中的結(jié)點總數(shù)為六條邊而所有鏈表中的結(jié)點總數(shù)為12。改進：改進：建立鄰接多重表建立鄰接多重表第36頁/共142頁37 7.2 圖的存儲結(jié)構(gòu)7.2.2 鄰接表表示法#define MAX_VERTEX_N

23、UM 20typedef struct ArcNode int adjvex;/該弧所指向的頂點的位置 ArcNode *nextarc; /指向下一條弧的指針 InfoType *info;/該弧相關信息的指針，如網(wǎng)的權(quán)值指針 ArcNode;/表結(jié)點typedef struct VNode VertexType data;/頂點的信息 ArcNode *firstarc; /第一個表結(jié)點的地址，指向第一條依附該頂點的弧的指針 VNode, AdjListMAX_VERTEX_NUM;/頭結(jié)點typedef struct AdjList vertices; int vexnum,arcnum

24、;/ 圖的當前頂點數(shù)、弧數(shù) int kind; /圖的種類標志 ALGraph;第37頁/共142頁38鄰接表的優(yōu)缺點： 優(yōu)點：1) 容易找任一頂點的第一鄰接點和下一個鄰接點。 2) 邊稀疏(ev2-v4-v8-v5-v3-v6-v7第49頁/共142頁50 7.3.1 深度優(yōu)先搜索 56724135672314從頂點從頂點 出發(fā)的搜索序列：出發(fā)的搜索序列： 5、6、2、3、1、4、7512431從頂點從頂點 出發(fā)的搜索序列：出發(fā)的搜索序列：1、2、4、3。沒有搜索。沒有搜索到所有的頂點，必到所有的頂點，必須另選圖中未訪須另選圖中未訪問過的頂點，問過的頂點，繼續(xù)進行繼續(xù)進行搜索。搜索。第50頁

25、/共142頁517.3.1 深度優(yōu)先搜索 數(shù)組visited存放結(jié)點的訪問標記，在遍歷開始前，visited的所有成員都被設置成FALSE。 visitedi 值為FALSE：表示頂點i未被訪問過；TRUE：表示頂點i已被訪問過。第51頁/共142頁52 7.3.1 深度優(yōu)先搜索 使用的變量說明：使用的變量說明：#define TRUE 1#define FALSE 0typedef int Boolean; /Boolean是布爾類型，值是是布爾類型，值是FALSE或或TRUEBoolean visitedMAX ; / 用于標識頂點是否已被訪問過用于標識頂點是否已被訪問過Status (

26、* VisitFunc) (int v); / 函數(shù)變量函數(shù)變量void DFSTraverse( Graph G, Status ( * Visit)(int v) /對圖做深度優(yōu)先遍歷對圖做深度優(yōu)先遍歷int v; VisitFunc = Visit; /使用全局變量使用全局變量VisitFunc,使使DFS不必設函數(shù)指針參數(shù)不必設函數(shù)指針參數(shù) for ( v=0; v G.vexnum; +v ) visitedv = FALSE; for ( v=0; v =0 ; w = NextAdjVex(G, v, w) ) if ( ! visitedw ) DFS(G, w);算法函數(shù)Fi

27、rstAdjVex()用來找v的第一個鄰接點返回v的（相對于w的）下一個鄰接頂點的序號。若w是v的最后一個鄰接點，則返回1。第53頁/共142頁54存儲結(jié)構(gòu)為鄰接矩陣時的NextAdjVex()int NextAdjVex(MGraph G,VertexType v,VertexType w) / 初始條件：圖G存在，v是G中某個頂點，w是v的鄰接頂點 / 操作結(jié)果：返回v的(相對于w的)下一個鄰接頂點的序號，若w是v的最后一個鄰接頂點，則返回-1 int i,j=0,k1,k2; k1=LocateVex(G,v); / k1為頂點v在圖G中的序號 k2=LocateVex(G,w); /

28、k2為頂點w在圖G中的序號 if(G.kind%2) / 網(wǎng) j=INFINITY; /無窮大 for(i=k2+1;inext) / 沒找到w或w是最后一個鄰接點 return -1; else / p-data.adjvex=w return p-next-data.adjvex; / 返回v的(相對于w的)下一個鄰接頂點的序號 第55頁/共142頁567.3.1 深度優(yōu)先搜索 非連通圖的深度優(yōu)先遍歷CABDEGF第56頁/共142頁57上圖的鄰接矩陣及深度優(yōu)先遍歷 rowColABCDEFGA (一）01 01000B10001 00C (二）000001 (1) 0D1000001E0

29、100001 F0010000G0001 100CABDEGF第57頁/共142頁58上圖的鄰接矩陣存儲下的深度優(yōu)先遍歷過程 以A為起始點進行DFS，在A所在行找到第一個值不為0且未被訪問的元素B，訪問之；在B所在行找第一個值不為0且未被訪問過的元素E一直到D ，訪問之；此時D所在行中的兩個非0元素對應的頂點均已被訪問過。此時，需返回到 ，找其所在行中下一個不為0的元素， 為其行中最后一個元素，需繼續(xù)返回到就這樣，一直返回到A（一）處，此后再無法返回。 然后排查還有沒有未被訪問過的頂點，于是找到了C（二），訪問之；同樣找到F并訪問之，得到最終的深度優(yōu)先遍歷序列:A B E G D C F第58

30、頁/共142頁59A BC (1)DEFG1304506 16 6 234(2)0123456鄰接表結(jié)構(gòu)及深度優(yōu)先遍歷CABDEGF第59頁/共142頁60 以A為起點，訪問之并找其鄰接表中的第一個結(jié)點，該結(jié)點鄰接點域為1（即為頂點B)，訪問B并找B的鄰接表的第一個結(jié)點，此結(jié)點表示頂點A，而A已訪問過，需找其第二個結(jié)點（即指示頂點E ），訪問E這樣繼續(xù)尋找直到訪問完頂點D，其鄰接表所指示的頂點全被訪問完，此時需返回到結(jié)點 ，其后的邊結(jié)點所指為頂點E（已被訪問），需返回到，其后已無結(jié)點，繼續(xù)返回到 ，此后再無法返回。需逐個第排查以找到下一個還沒有被訪問的頂點。于是找到C，按上述方法繼續(xù)即可。鄰接

31、表結(jié)構(gòu)及深度優(yōu)先遍歷第60頁/共142頁617.3.1 深度優(yōu)先搜索 時間復雜度：時間復雜度： 對前述算法來說，對圖中每個頂點至多調(diào)用一次對前述算法來說，對圖中每個頂點至多調(diào)用一次DFS函數(shù)，函數(shù)，因此，遍歷圖的過程實質(zhì)上是對每個頂點查找其鄰接點的過程。因此，遍歷圖的過程實質(zhì)上是對每個頂點查找其鄰接點的過程。耗費時間取決于其存儲結(jié)構(gòu)。耗費時間取決于其存儲結(jié)構(gòu)。 鄰接矩陣（鄰接矩陣（二維數(shù)組二維數(shù)組）表示時，查找每個頂點的鄰接點所需時間為：）表示時，查找每個頂點的鄰接點所需時間為：T(n)= O(n2)第61頁/共142頁627.3.1 深度優(yōu)先搜索時間復雜度：時間復雜度： 鄰接表（鄰接表（圖的

32、鏈式存儲結(jié)構(gòu)） 調(diào)用調(diào)用DFSDFS找鄰接點所需時間為找鄰接點所需時間為O(e) O(e) (2e(若G為無向圖)或e(若G為有向圖)，即O(e) ; ; 在調(diào)用在調(diào)用DFSDFS之前還需對數(shù)組之前還需對數(shù)組visited visited 進行預處理，顯然其時間復雜進行預處理，顯然其時間復雜度可以控制在度可以控制在O(n)O(n)內(nèi)；內(nèi)； 故總的時間復雜度為：故總的時間復雜度為： T(n)= O(n + e) 注：n-頂點數(shù)， e-邊或弧數(shù)第62頁/共142頁637.3.2 廣度優(yōu)先搜索基本思想 首先，訪問初始點vi ，并做訪問過標志訪問vi 的所有未被訪問過的鄰接點vi1，vi2，.，vit

33、，并均標記為已訪問過然后再按照vi1,vi2,.,vit 的次序，訪問每一個頂點的所有未被訪問過的鄰接點，并做標記。依次類推，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。若圖中還有未被訪問的頂點，則任選其一作為起點，重新開始上述過程，直至圖中所有頂點都被訪問到?！跋缺辉L問的頂點的鄰接點”要先于“后被訪問的頂點的鄰接點”被訪問，也就是先到先被訪問。第63頁/共142頁64 7.3.2 廣度優(yōu)先搜索 需要特別說明的是：頂點的鄰接頂點的次序是任意的，因此廣度優(yōu)先搜索的序列可能有多種。 V1V2V3V4V5V8V6V7v1-v2-v3-v4-v5-v6-v7-v8鄰接頂點的訪問次序以序號為準，序號小

34、的先訪問。從v v1 1出發(fā)進行搜索的訪問序列：第64頁/共142頁657.3.2 廣度優(yōu)先搜索對于廣度優(yōu)先遍歷，其關鍵之處在于怎么保證“先被訪問的頂點的鄰接點”要先于“后被訪問的頂點的鄰接點”被訪問？先到先被訪問，這正好是隊列的特點，因此可以使用隊列來實現(xiàn)。 使用的變量說明等與深度優(yōu)先搜索相同 廣度優(yōu)先遍歷的算法第65頁/共142頁667.3.2 廣度優(yōu)先搜索 廣度優(yōu)先搜索遍歷圖的時間復雜度和深度優(yōu)先搜索遍歷圖相同深度優(yōu)先搜索遍歷圖相同 : : 鄰接矩陣鄰接矩陣 T(n)= O(n2) 鄰接表鄰接表 T(n)= O(n + e) n：頂點數(shù)頂點數(shù) e：邊邊或弧或弧數(shù)數(shù)第66頁/共142頁67

35、 7.4 圖的連通性問題7.4.1 無向圖的連通分量和生成樹 在對無向圖進行遍歷時，對于連通圖，從圖中任一頂點出發(fā)，進行深度優(yōu)先搜索或廣度優(yōu)先搜索，便可訪問到圖中所有頂點；而對于非連通圖，則需從多個頂點出發(fā)進行搜索。而每一次從一個新頂點出發(fā)搜索得到的頂點序列就是圖的各個連通分量中的頂點集。這些頂點集分別加上所有依附于它們的邊，便構(gòu)成了連通分量。第67頁/共142頁687.4.1 無向圖的連通分量和生成樹ABLMCDEGHKFJI無向圖無向圖GABLMCFJDEGHKI無向圖無向圖G的三個連通分量的三個連通分量第68頁/共142頁69 7.4.1 無向圖的連通分量和生成樹 在對連通圖進行搜索時，

36、搜索過程中經(jīng)歷的所有邊和圖中所有的頂點構(gòu)成了連通圖的一個極小連通子圖，即連通圖的生成樹。 稱由深度優(yōu)先搜索得到的生成樹為深度優(yōu)先生成樹，而由廣度優(yōu)先搜索得到的生成樹稱廣度優(yōu)先生成樹。 對于非連通圖，其中的每一個連通分量都可以通過遍歷得到一棵生成樹，所有這些連通分量的生成樹就構(gòu)成了非連通圖的生成森林。第69頁/共142頁707.4.1 無向圖的連通分量和生成樹 設E(G)E(G) 為連通圖GG中所有邊的集合，則從圖中任一頂點出發(fā)遍歷圖時，必定將E(G)E(G) 分成兩個集合T(G)T(G)和B(G)B(G)，其中T(G)T(G)是遍歷圖過程中歷經(jīng)的邊的集合； B(G)B(G)是剩余的邊的集合。顯

37、然，T(G)T(G)和連通圖中所有的頂點構(gòu)成連通圖GG的極小連通子圖。下圖中的虛線為B(G)B(G)中的邊。 ABLMCDEGHKFJI無向圖無向圖GABLMCFJDEGHKI無向圖無向圖GG的的深度優(yōu)先生成森林深度優(yōu)先生成森林第70頁/共142頁71 7.4.1 無向圖的連通分量和生成樹 如果以孩子兄弟鏈表（Page136）作生成森林的存儲結(jié)構(gòu)，則形成非連通圖的深度優(yōu)先生成森林的算法 typedef struct CSNode /二叉鏈表（孩子-兄弟） ElemType data; struct CSNode *firstchild, *nextsibling; CSNOde, *CSTre

38、e;第71頁/共142頁72 7.4.3 最小生成樹假設要在n個城市之間建立通信網(wǎng)絡，連通n個城市只需要n-1條線路，問題是如何鋪設線路才能最節(jié)省資金？而在n個城市間最多可能有n(n-1)條線路，各個線路的費用是不一樣的，怎么選擇這n-1條線路，使總的耗費最少呢？如果把城市當作圖的頂點看待，城市之間的通信線路看作圖的頂點之間的邊，邊的權(quán)值就相當于通信線路的費用。在n個城市之間建立n-1條通信線路實際上就是圖的一棵生成樹。第72頁/共142頁737.4.3 最小生成樹具有n個頂點的圖的生成樹的數(shù)目是很多的，我們的目標是要選擇一棵具有最小代價的生成樹(Minimum Cost Spanning T

39、ree，MST)(簡稱最小生成樹最小生成樹)。一棵生成樹的代價就是該樹上所有邊的權(quán)值之和。第73頁/共142頁747.4.3 最小生成樹構(gòu)造最小生成樹可以有多種算法，最常用的算法利用了最小生成樹的一種簡稱為MST的性質(zhì)：即假設N(V,E)是一個連通網(wǎng)，U是頂點集V的一個非空子集，若(u,v)是一條具有最小權(quán)值（代價）的邊，其中uU, v V-U，則必存在一棵包含邊(u,v)的最小生成樹。該性質(zhì)可以用反證法來證明。第74頁/共142頁757.4.3 最小生成樹證明：假設網(wǎng)N的任何一棵最小生成樹都不包含邊(u,v)。設T是連通網(wǎng)上的一棵最小生成樹，當把邊(u,v)加入T中時，T中必存在一條包含(u

40、,v)的回路；那么在這條回路上任意刪去除邊(u,v)外的一條邊(u, v)，這條回路上的所有頂點之間以及所有頂點與其他頂點之間必定仍然有通路，從而消除了回路，并生成了一棵新的生成樹T，而(u,v)的代價必定不高于(u,v)，所以T是包含(u,v)的一棵最小生成樹，這與假設矛盾。第75頁/共142頁767.4.3 最小生成樹下面介紹兩個利用MST性質(zhì)構(gòu)造最小生成樹的算法：Prim（普里姆）算法Kruskal（克魯斯卡爾）算法第76頁/共142頁77 7.4.3 最小生成樹Prim算法的基本思想：假設N(V,E)是連通網(wǎng)，TE是N上最小生成樹的邊的集合。算法首先從Uu0(u0 V), TE=開始，

41、重復執(zhí)行如下操作： 在所有u U，v V-U的邊(u,v) E找一條代價最小的邊(u0, v0)并入集合TE，同時v0并入U，直到UV為止。 此時TE中必有n-1條邊，T(V, TE)即為N的最小生成樹。第77頁/共142頁78第78頁/共142頁PrimPrim算法實例算法實例79(1) 在以頂點1為出發(fā)點，頂點2, 3, 4, 5, 6為終止點的邊中，將權(quán)最小的邊(1, 3)作為最小生成樹的第一條邊加入TE，頂點3加入U。則U = 1, 3，TE = (1, 3)，V - U = 2, 4, 5, 6，如圖 (b)所示。第79頁/共142頁PrimPrim算法實例算法實例80(2) 在以頂

42、點1, 3為出發(fā)點，頂點2, 4, 5, 6為終止點的邊中，將權(quán)最小的邊(3, 6) 作為最小生成樹的第二條邊加入TE，頂點6加入U。則U = 1, 3, 6，TE = (1, 3),(3, 6)，V - U = 2, 4, 5，如圖 (c)所示。第80頁/共142頁81Prim算法實例81(3) 在以頂點1, 3, 6為出發(fā)點，頂點2, 4, 5為終止點的邊中，將權(quán)最小的邊(6, 4) 作為最小生成樹的第三條邊加入TE，頂點4加入U。則U = 1, 3, 6, 4，TE = (1, 3), (3, 6), (6, 4)，V - U = 2, 5，如圖 (d)所示。第81頁/共142頁8282

43、Prim算法實例82(4) 在以頂點1, 3, 6, 4為出發(fā)點，頂點2, 5為終止點的邊中，將權(quán)最小的邊(3, 2) 作為最小生成樹的第四條邊加入TE，頂點2加入U。則U = 1, 3, 6, 4, 2，TE = (1, 3), (3, 6), (6, 4), (3, 2)，V - U = 5，如圖7.16(e)所示。第82頁/共142頁838383Prim算法實例83(5) 在以頂點1, 3, 6, 4, 2為出發(fā)點，頂點5為終止點的邊中，將權(quán)最小的邊(2, 5) 作為最小生成樹的第五條邊加入TE，頂點5加入U。則U = 1, 3, 6, 4, 2, 5，TE = (1, 3), (3,

44、6), (6, 4), (3, 2), (2, 5)，V - U = ，如圖 (f)所示。第83頁/共142頁84v1v2v4v3v5v66165556342v1v31v25v53v64v42(6) U = V，算法結(jié)束，U = 1, 3, 6, 4, 2, 5，TE = (1, 3), (3, 6), (6, 4), (3, 2), (2, 5)，T=(U,TE)是連通網(wǎng)的最小生成樹。Prim算法實例第84頁/共142頁85 7.4.3 最小生成樹 Prim算法的數(shù)據(jù)結(jié)構(gòu)1 v22 v33 v44 v55 v6UV-Ukadjvexlowcostv16v11v15v1v2,v3,v4,v5,

45、v62adjvexlowcostv350v15v36v34v1,v3v2,v4,v5,v65adjvexlowcostv350v62v360v1,v3,v6v2,v4,v53adjvexlowcostv3500v360v1,v3,v6,v4v2,v51adjvexlowcost000v230v1,v3,v6,v4,v2v54adjvexlowcost00000v1,v3,v6,v4,v2,v5v1v2v4v3v5v66165556342closedgei.adjvex是最小生成樹中的頂點（即U中的頂點）到i點為最小權(quán)值的那個頂點。closedgei第85頁/共142頁867.4.3 最小生成樹

46、 基 于 P r i m 算 法 的 最 小 生 成 樹 函 數(shù) 模 塊MiniSpanTree_PRIM ()的實現(xiàn)代碼如果頂點數(shù)為如果頂點數(shù)為n, n, 則該則該算法的時間復雜度為算法的時間復雜度為O(nO(n2 2) )，與網(wǎng)中的邊數(shù)無關，因此，與網(wǎng)中的邊數(shù)無關，因此適合求邊稠適合求邊稠密的圖密的圖。而而KruskalKruskal算法的時間復雜度為算法的時間復雜度為O(eloge)O(eloge)(e(e為為圖的邊數(shù)圖的邊數(shù)) )。因此后者。因此后者適合求適合求邊稀疏邊稀疏的網(wǎng)的網(wǎng)（Why?Why?）。第86頁/共142頁87下面是x*log(x)的函數(shù)圖，該圖說明克魯斯卡爾算法只適合

47、邊稀疏的網(wǎng)的最小生成樹。第87頁/共142頁88 7.4.3 最小生成樹Kruskal（克魯斯卡爾）算法的基本思想：設連通網(wǎng)N N(V,E)(V,E)。令最小生成樹的初始狀態(tài)為只有n n個頂點而無邊的非連通圖T T(V,)(V,)，圖中每個頂點自成一個連通分量。在E E中選擇代價最小的邊，若該邊依附的頂點落在T T中不同的連通分量上，則將此邊加入T T中，否則舍去此邊而選擇下一條代價最小的邊，依次類推，直到T T中所有頂點都在同一連通分量上為止。Kruskal算法實例v1v2v4v3v5v66165556342v1v2v4v3v5v615342第88頁/共142頁89課堂作 業(yè)1. 一個具有n

48、個頂點的圖，最少有（ ）個連通分量，最多有（ ）個連通分量。 A.0 B. 1 C. n-1 D. n2. 在具有8個頂點的無向簡單圖中，當邊最少為多少（ ）時才能確保該圖一定是連通的？3.寫出一個將有向圖的鄰接表轉(zhuǎn)換為鄰接矩陣的算法。（提示：先建立一個空的鄰接矩陣，然后在鄰接表上順序取每個單鏈表中的表結(jié)點，如果表結(jié)點不為空，則將鄰接矩陣中對應單元置1.）第89頁/共142頁90作業(yè)答案作業(yè)答案1、2、 3、void AdjList_to_Mat(ALGraph G1,MGraph G2) for(i=0;iG1.vexnum;i+)for( j=0;jG1.vexnum;j+)G2.arcs

49、i j=0;for(i=0;iadjvex=1; p=p-nextarc; 第90頁/共142頁91 7.5 有向無環(huán)圖及其應用定義： 一個無環(huán)的有向圖稱作有向無環(huán)圖(Directed AcyclineGraph)，簡稱DAG圖。 BEFGLMN有向樹有向樹BEFGLMNDAG圖圖BEFGLMN有向圖（含環(huán)）有向圖（含環(huán)）較有向樹更一般的特殊有向圖第91頁/共142頁92 7.5 有向無環(huán)圖及其應用1、有向無環(huán)圖是描述含有公共子式的表達式的有效工具。 如對下述表達式：(a+b)*(b*(c+d)+(c+d)*e)*(c+d)*e)可以用二叉樹來表示。但實際上該表達式中有相同的子表達式，在二叉樹

50、中它們會重復出現(xiàn)，這樣就比較浪費空間，如果用有向無環(huán)圖則可以實現(xiàn)對相同子式的共享，從而節(jié)省存儲空間。*+e+ab*b+cd+ecdcd*+*+*+eabcd第92頁/共142頁93 7.5 有向無環(huán)圖及其應用 檢查一個有向圖是否存在環(huán)要比無向圖復雜。 因為對于無向圖來說，若深度優(yōu)先遍歷過程中遇到回邊（即指向已訪問過的頂點的邊），則必定存在環(huán)； 而對于有向圖，這條回邊有可能是指向深度優(yōu)先生成森林中另一棵生成樹上的頂點的弧。 但是，如果從有向圖上某個頂點v出發(fā)的遍歷，在DFS(v)結(jié)束之前出現(xiàn)一條從頂點u到頂點v的回邊，則有向圖中必定存在包含頂點v和u的環(huán)。第93頁/共142頁 2、有向無環(huán)圖也是

51、描述一項工程或系統(tǒng)的進行過程的有效工具。 絕大多數(shù)的工程都可分為若干個活動的子工程，而這些子工程之間，通常都受著一定條件的約束。 對整個工程和系統(tǒng)，人們關心的是兩個方面的問題人們關心的是兩個方面的問題： 一是工程能否順利進行一是工程能否順利進行； 二是工程完成所必須的最短時間二是工程完成所必須的最短時間。 對應于有向圖，即為進行拓撲排序拓撲排序和求關鍵路徑求關鍵路徑的操作。94第94頁/共142頁95 7.5 有向無環(huán)圖及其應用7.5.1 拓撲排序偏序：若集合 X 上的關系 R 是傳遞的、自反的、反對稱的，則稱 R 是集合 X 上的偏序關系。偏序是指集合中僅有部分成員之間可比較。全序：若關系

52、R 是集合 X 上的偏序關系，如果對于每個 x, y 屬于 X，必有 x R y 或 y R x ，則稱 R 是集合 X 上的全序關系。全序是指集合中全體成員之間均可比較。V2V1V4V3偏序偏序V1V3V2V4全序（拓撲有序）全序（拓撲有序）拓撲排序：拓撲排序：由某個集合由某個集合上的上的一個一個偏序偏序得到該集合上的一個得到該集合上的一個全序全序的的操作操作。第95頁/共142頁96 7.5 有向無環(huán)圖及其應用7.5.1 拓撲排序一個表示偏序的有向圖可用來表示一個流程圖，它或者是一個施工流程圖，或者是一個產(chǎn)品生產(chǎn)流程圖。圖中每一條有向邊表示兩個子工程之間的次序關系（領先關系）。 這種用頂點

53、表示活動，用弧表示活動間的優(yōu)先關系的有向圖稱為頂點表示活動的網(wǎng)(Activity On Vertex Network)，簡稱AOV網(wǎng)。AOV網(wǎng)的主要用途：描述工程項目或系統(tǒng)進行的次序。在網(wǎng)中，若從頂點i到頂點j有一條有向路徑，則i是j的前驅(qū)，j就是i的后繼。在AOV網(wǎng)中不應該出現(xiàn)有向環(huán)，因為出現(xiàn)有向環(huán)，就意味著某個活動以自己為先決條件。 因此，對給定的AOV網(wǎng)需首先判斷網(wǎng)中是否有環(huán)。檢測的辦法是對有向圖構(gòu)造其頂點的拓撲有序序列，若網(wǎng)中所有頂點都在其拓撲有序序列中，則該AOV網(wǎng)必定不存在環(huán)。第96頁/共142頁97 7.5 有向無環(huán)圖及其應用7.5.1 拓撲排序定義：如果在AOV網(wǎng)中，從頂點vi

54、到頂點vj存在一條路徑，則在線性序列中，頂點vi一定排在頂點vj之前。具有這種性質(zhì)的線性序列稱為拓撲序列拓撲序列，構(gòu)造拓撲序列的操作稱為拓拓撲排序撲排序。如下圖的一個拓撲序列為（該圖有多個拓撲序列）：(C1, C2, C3, C4, C5, C7, C9, C10, C11, C6, C12, C8)C4C5C1C2C3C7C12C9C10C11C6C8第97頁/共142頁98 7.5 有向無環(huán)圖及其應用7.5.1 拓撲排序如何進行拓撲排序呢？ （1）在有向圖中選取一個沒有前驅(qū)的頂點且輸出之； （2）從圖中刪去該頂點和所有以它為尾的弧。 重復(1)、(2)直至全部頂點都已輸出，或者當前圖中不存

55、在無前驅(qū)的頂點為止，后一種情況說明圖中存在環(huán)。以下圖為例：V2V5V5V1V2V4V3V6V5V2V3V5V1V4V2V3V6V5V4V2V3V5V6V1V4V3V2V5第98頁/共142頁99 7.5 有向無環(huán)圖及其應用7.5.1 拓撲排序?qū)嵗龑嵗合率黾?M 代表課程的集合，其中，C1代表數(shù)學， C2代表程序設計，C3代表離散數(shù)學，C4代表匯編程序設計，C5代表數(shù)據(jù)結(jié)構(gòu)，C6代表結(jié)構(gòu)化程序設計, C7代表編譯原理。 關系 R 課程學習的先后關系，如數(shù)學必須在離散數(shù)學之前學習。要求排一張學習的先后次序表。C1C3C2C4C6C5C7C1C3C2C7C5C6C4數(shù)學數(shù)學程序設計程序設計離散數(shù)

56、學離散數(shù)學匯編程序設計匯編程序設計數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)化程序設計結(jié)構(gòu)化程序設計編譯原理編譯原理第99頁/共142頁100 7.5 有向無環(huán)圖及其應用7.5.1 拓撲排序 如何在計算機中實現(xiàn)？需要一個數(shù)組存放所有頂點的入度（入度為0說明該頂點沒有前驅(qū)）。而刪去該頂點及以它為尾的弧，只要使該弧的弧頭頂點的入度減1就可以了。由于在圖中入度為0的頂點數(shù)可能較多，為了避免重復檢測入度為0的頂點，可設一棧來存放所有入度為0的頂點。01012345611213indegree0棧棧C1C3C2C7C5C6C4C1C21201234563446C3C4C55C6C766第100頁/共142頁101 7.5 有

57、向無環(huán)圖及其應用7.5.1 拓撲排序 算法如下：Status TopologicalSort(ALGraph G) 采用鄰接表存儲 FindInDegree(G, indegree); 對各頂點求入度InitStack(S); 建零入度頂點棧Sfor ( i=0; inextarc ) k=p-adjvex; if ( !(-indegreek) ) Push(S, k); 對i號頂點的每個鄰接點的入度減1，若入度減為0 則入棧if ( countG.vexnum ) return ERROR; 該有向圖有回路 else return OK;第101頁/共142頁102 7.5 有向無環(huán)圖及其

58、應用7.5.1 拓撲排序算法的時間效率算法的時間效率：（1）建立各頂點的入度的時間復雜度為O(e);（2）建入度為0的棧的時間復雜度為O(n);（3）在拓撲排序過程中，若有向圖無環(huán)，則每個頂點進棧一次，出棧一次，入度減1的操作在while循環(huán)總共執(zhí)行e次，所以，總的時間復雜度為O(n+e)。當有向圖無環(huán)時，也可利用深度優(yōu)先搜索進行拓撲排序，因為圖中無環(huán)，則由圖中某個頂點出發(fā)進行深度優(yōu)先搜索時，最先退出DFS函數(shù)的頂點即為出度為0的頂點，是拓撲有序序列中最后一個頂點。由此，按退出DFS函數(shù)的先后記錄下來的頂點序列即為逆向的拓撲有序序列。第102頁/共142頁103 7.5 有向無環(huán)圖及其應用7.

59、5.2 關鍵路徑 AOE網(wǎng)(Activity On Edge)：即用邊表示活動的網(wǎng)，是帶權(quán)的有序無環(huán)圖，其中頂點表示事件，弧表示活動，權(quán)表示活動持續(xù)的時間。如圖所示： 通常，AOE網(wǎng)的主要用途：(1)估算工程完成的時間；(2)找出影響工程進度的關鍵活動。V2V1V3V5V7V8V9V4V6a6=2a1=6a4=1a7=9a10=2a11=4a9=4a3=5a2=4a5=1a8=7AOE網(wǎng)網(wǎng)第103頁/共142頁104 7.5 有向無環(huán)圖及其應用7.5.2 關鍵路徑 由于整個工程只有一個開始點，一個完成點，故在正常情況（無環(huán)）下只有一個入度為0 的點（源點源點）和一個出度為0的點（匯點匯點）。由

60、于有些工程可并行地進行，所以完成工程的最短時間即為從開始點到完成點的最長路徑的長度（路徑長度指的是路徑上各持續(xù)時間之和）。 路徑最長的路徑叫關鍵路徑關鍵路徑（Critical Path）。第104頁/共142頁7.5 有向無環(huán)圖及其應用事件事件Vi的最早發(fā)生時間的最早發(fā)生時間：從開始點v1到vi的最長路徑長度。用ve(i)表示事件事件Vi的最遲發(fā)生時間的最遲發(fā)生時間：在不推遲整個工期的前提下，事件vi允許的最遲發(fā)生時間。用vl(i)表示。活動活動ai的最早開始時間的最早開始時間：即為ai的弧尾頂點(事件)的最早發(fā)生時間。用e(i)表示?；顒踊顒觓i的最遲開始時間的最遲開始時間：在保證不推遲整個

61、工程的完成時間的前提下，活動ai的最遲開始時間。用l(i)表示。105V2V1V3V5V7V8V9V4V6a6=2a1=6a4=1a7=9a10=2a11=4a9=4a3=5a2=4a5=1a8=7AOE網(wǎng)網(wǎng)v: vertexa: activitye: early l: late第105頁/共142頁106 7.5 有向無環(huán)圖及其應用7.5.2 關鍵路徑l(i) - e(i) 意味著完成活動ai的時間余量。關鍵活動關鍵活動：l(i) = e(i)的活動。 顯然，關鍵路徑上的所有活動都是關鍵活動。因此，提前非關鍵活動并不能加快工程的進度。所以分析關鍵路徑的目的是判別哪些是關鍵活動，以便提高關鍵活

62、動的工序，縮短整個工期。 判別關鍵活動就是要找l(i) = e(i)的活動，因此必須首先求出l(i) 和 e(i)，為此，必須先求出事件的最早發(fā)生時間ve(j)和最遲發(fā)生時間vl(j)。如果活動ai由弧表示，其持續(xù)時間為dut()，則有如下的關系：e(i) = ve(j)l(i) = vl(k) - dut() 所以下面的問題就是如何求ve(j)和vl(j)了。k dut()dut()a ai ij第106頁/共142頁107 7.5 有向無環(huán)圖及其應用7.5.2 關鍵路徑求求ve(j)和和vl(j)方法方法：（1）ve(0) = 0開始向前遞推:ve(j) = Maxve(i) + dut(

63、) T, j = 1,2,n-1, T是所有以第j個頂點為弧頭的弧的集合。（2）從vl(n-1) = ve(n-1)起向后遞推:vl(i) = Minvl(j) - dut() S, i = n-2,n-1,.,0,S是所有以第i個頂點為弧尾的弧的集合。 這兩個遞推公式的計算必須分別在拓撲有序和逆拓撲有序的前提下進行。也就是說：ve(j-1)必須在vj的所有前驅(qū)的最早發(fā)生時間求得之后才能確定vl(j-1)則必須在vj的所有后繼的最遲發(fā)生時間求得之后才能確定。第107頁/共142頁108 7.5 有向無環(huán)圖及其應用V0Vj3 35 512128888ve(Vj) = 3、5、12、88的最大值的

64、最大值 88起點起點0 0ViVn-1vl(Vi) = 取取 10-2、10-4、10-3、10-7的最小值的最小值 3 或或 10 - 最長路徑最長路徑 72 24 43 37 710101010匯點匯點V0Vjve(Vj) = Maxve(i) + dut() TVuVvVwVx2 23 39 982821 12 23 36 6由源點至匯點由源點至匯點ViVn-1vl(i) = Minvl(j) - dut() S10101010匯點匯點VuVvVwVx8 88 85 51 12 21 12 29 9由匯點至源點由匯點至源點第108頁/共142頁109 7.5 有向無環(huán)圖及其應用7.5.2

65、 關鍵路徑由此，可以得到求關鍵路徑的算法求關鍵路徑的算法：（1）輸入e條弧，建立AOE網(wǎng)。（2）從源點v1出發(fā)，令ve0 = 0，按拓撲有序求各頂點的最早發(fā)生時間vei(1in-1)，如果得到的拓撲序列中頂點個數(shù)小于網(wǎng)中頂點數(shù)n，說明網(wǎng)中存在環(huán)，不能求關鍵路徑，算法終止；否則執(zhí)行步驟（3）。（3）從匯點vn出發(fā)，令vln-1 = ven-1；按逆拓撲有序求其余各頂點的最遲發(fā)生時間vli(n-2i0);（4）根據(jù)個各頂點的ve和vl值，求每條弧s的e(s)和l(s)。若某條弧滿足e(s) = l(s)，則為關鍵活動。第109頁/共142頁110 7.5 有向無環(huán)圖及其應用7.5.2 關鍵路徑由于

66、求關鍵路徑需要拓撲序列和逆拓撲序列，因此，需要利用拓撲排序的方法。對拓撲排序稍加對拓撲排序稍加修改即可求得各頂點的修改即可求得各頂點的ve和和vl值值，修改方法如下： （1）對vei設初值0。 （2）增加求vj的直接后繼vk的最早發(fā)生時間的操作：若vej+dut() vek,則vek = vej+dut()。 （3）為了求逆拓撲序列，只需要把拓撲序列入棧， 那么出棧的序列即為逆拓撲序列。第110頁/共142頁111 7.5 有向無環(huán)圖及其應用7.5.2 關鍵路徑實例：求事實例：求事件頂點的最件頂點的最早發(fā)生時間早發(fā)生時間V1V2V3V4V5V6正向拓撲排序：正向拓撲排序：利用拓撲排序算法求事件頂點的最早發(fā)生時利用拓撲排序算法求事件頂點的最早發(fā)生時間的執(zhí)行步驟：間的執(zhí)行步驟：1、設每個頂點的最早發(fā)生時間為、設每個頂點的最早發(fā)生時間為0，將入度，將入度為零的頂點進棧。為零的頂點進棧。2、將棧中入度為零的頂點、將棧中入度為零的頂點V取取出，并壓入另出，并壓入另一棧，用于形成逆向拓撲排序的序列。一棧，用于形成逆向拓撲排序的序列。3、根據(jù)鄰接表找到頂點、根據(jù)鄰接表找到頂點V的所有的鄰接的所有的鄰