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

1、.,1,數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容,多對(duì)多 （m:n),.,2,哥尼斯堡七橋問(wèn)題 德國(guó)古城哥尼斯堡普雷格爾河七 橋問(wèn)題：從任一橋頭出發(fā)，依次走過(guò)每座 橋，每座橋只走一次，最后回到出發(fā)點(diǎn)。 一筆畫(huà)問(wèn)題,.,3,.,4,.,5,7.1 基本術(shù)語(yǔ) 7.2 存儲(chǔ)結(jié)構(gòu) 7.3 圖的遍歷 7.4 圖的連通性 7.5 圖的應(yīng)用,第7章 圖,.,6,7.1 圖的基本術(shù)語(yǔ),其中：V 是G 的頂點(diǎn)集合，是有窮非空集； E 是G 的邊集合，是有窮集。,問(wèn)：當(dāng)E(G)為空時(shí)，圖G存在否？ 答：還存在！但此時(shí)圖G只有頂點(diǎn)而沒(méi)有邊。,有向圖： 無(wú)向圖： 完全圖：,圖G中的每條邊都是有方向的； 圖G中的每條邊都是無(wú)方向的； 圖G任

2、意兩個(gè)頂點(diǎn)都有一條邊相連接；,若 n 個(gè)頂點(diǎn)的無(wú)向圖有 n(n-1)/2 條邊, 稱(chēng)為無(wú)向完全圖 若 n 個(gè)頂點(diǎn)的有向圖有n(n-1) 條邊, 稱(chēng)為有向完全圖,V=vertex E=edge,圖：記為 G( V, E ),有向邊(u, v)稱(chēng)為弧，邊的始點(diǎn)u 叫弧尾，終點(diǎn)v 叫弧頭。,.,7,例：判斷下列4種圖形各屬什么類(lèi)型？,無(wú)向,無(wú)向圖(樹(shù)),有向圖,有向,n(n-1)/2 條邊,n(n-1) 條邊,G1的頂點(diǎn)集合為V(G1)=0,1,2,3 邊集合為E(G1)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3),完全圖,完全圖,.,8,證明：,證明：若是完全有向圖，則

3、n個(gè)頂點(diǎn)中的每個(gè)頂點(diǎn)都有一條弧指向其它n-1個(gè)頂點(diǎn), 因此總邊數(shù)=n(n-1),證明：從可以直接推論出無(wú)向完全圖的邊數(shù)因?yàn)闊o(wú)方向，兩弧合并為一邊，所以邊數(shù)減半，總邊數(shù)為n(n-1)/2。, 完全無(wú)向圖有n(n-1)/2 條邊。, 完全有向圖有n(n-1)條邊。,.,9,稀疏圖：稠密圖：,設(shè)有兩個(gè)圖 G(V, E) 和 G(V, E)。若 V V 且 E E, 則稱(chēng) 圖G 是 圖G 的子圖。,子 圖：,邊較少的圖。通常邊數(shù)遠(yuǎn)少于nlogn 邊很多的圖。,無(wú)向圖中，邊數(shù)接近n(n-1)/2 有向圖中，邊數(shù)接近n(n-1),.,10,帶權(quán)圖：,即邊上帶權(quán)的圖。其中權(quán)是指每條邊可以標(biāo)上具有某種含義的數(shù)

4、值（即與邊相關(guān)的數(shù)）。,連通圖：,在無(wú)向圖中, 若從頂點(diǎn)v1到頂點(diǎn)v2有路徑, 則稱(chēng)頂點(diǎn)v1與v2是連通的。如果圖中任意一對(duì)頂點(diǎn)都是連通的, 則稱(chēng)此圖是連通圖。 非連通圖的極大連通子圖叫做連通分量。,帶權(quán)圖,在有向圖中, 若對(duì)于每一對(duì)頂點(diǎn)vi和vj, 都存在一條從vi到vj和從vj到vi的路徑, 則稱(chēng)此圖是強(qiáng)連通圖。,強(qiáng)連通圖：,網(wǎng) ：,非強(qiáng)連通圖的極大強(qiáng)連通子圖叫做強(qiáng)連通分量。,.,11,生成樹(shù)：,是一個(gè)極小連通子圖，它含有圖中全部n個(gè)頂點(diǎn)，但只有n-1條邊。,若干棵生成樹(shù)的集合，含全部頂點(diǎn)，但構(gòu)成這些樹(shù)的邊或弧是最少的。,有兩類(lèi)圖形不在本章討論之列：,圖的基本術(shù)語(yǔ)(續(xù)),如果在生成樹(shù)上添加

5、1條邊，必定構(gòu)成一個(gè)環(huán)。 若圖中有n個(gè)頂點(diǎn)，卻少于n-1條邊，必為非連通圖。,生成 森林：,.,12,鄰接點(diǎn)：,有向邊(u, v)稱(chēng)為弧，邊的始點(diǎn)u 叫弧尾，終點(diǎn)v 叫弧頭。,頂點(diǎn) v 的入度是以 v 為終點(diǎn)的有向邊的條數(shù), 記作 ID(v); 頂點(diǎn) v 的出度是以 v 為始點(diǎn)的有向邊的條數(shù), 記作 OD(v)。,若 (u, v) 是 E(G) 中的一條邊，則稱(chēng) u 與 v 互為鄰接頂點(diǎn)。,弧頭和弧尾：,入度和出度：,問(wèn)：當(dāng)有向圖中僅1個(gè)頂點(diǎn)的入度為0,其余頂點(diǎn)的入度均為1，此時(shí)是何形狀？,度：,頂點(diǎn)v 的度是與它相關(guān)聯(lián)的邊的條數(shù)。記作TD(v)。 在有向圖中, 頂點(diǎn)的度等于該頂點(diǎn)的入度與出度

6、之和。,U 的入度=? U 的出度=?,答：是樹(shù)！而且是一棵有向樹(shù)！,.,13,簡(jiǎn)單路徑：,路徑上各頂點(diǎn) v1,v2,.,vm 均不互相重復(fù)。,回路：,若路徑上第一個(gè)頂點(diǎn) v1 與最后一個(gè)頂點(diǎn)vm 重合，則稱(chēng)這樣的路徑為回路或環(huán)。,路徑：,在圖 G(V, E) 中, 若從頂點(diǎn) vi 出發(fā), 沿一些邊經(jīng)過(guò)一些頂點(diǎn) vp1, vp2, , vpm，到達(dá)頂點(diǎn)vj。則稱(chēng)頂點(diǎn)序列 ( vi vp1 vp2 . vpm vj ) 為從頂點(diǎn)vi 到頂點(diǎn) vj 的路徑。它經(jīng)過(guò)的邊(vi, vp1)、(vp1, vp2)、.、(vpm, vj)應(yīng)當(dāng)是屬于E的邊。,路徑長(zhǎng)度：,非帶權(quán)圖的路徑長(zhǎng)度是指此路徑上邊的條

7、數(shù)； 帶權(quán)圖的路徑長(zhǎng)度是指路徑上各邊的權(quán)之和。,圖的術(shù)語(yǔ)（續(xù)）,.,14,ADT Graph 數(shù)據(jù)對(duì)象V： 數(shù)據(jù)關(guān)系 R： 基本操作P： ADT Graph,圖的抽象數(shù)據(jù)類(lèi)型,V是具有相同特性的數(shù)據(jù)元素的集合，稱(chēng)為頂點(diǎn)集。,R=VR；VR=|v,wV 且 P(v,w), 表示從v到w的弧， 謂詞P(v,w)定義了弧的意義或信息,CreatGraph ( 初始條件：V是圖的頂點(diǎn)集，VR是圖中弧的集合。 操作結(jié)果：按V和VR的定義構(gòu)造圖G。,注意：V 的大小寫(xiě)含義不同！,InsertVex ( 初始條件：圖G存在，v 和圖中頂點(diǎn)有相同特征。 操作結(jié)果：在圖G中添加新頂點(diǎn)。,（參見(jiàn)教材P156-25

8、7）,.,15,7.2 圖的存儲(chǔ)結(jié)構(gòu),圖的特點(diǎn)：,鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：,順序存儲(chǔ)結(jié)構(gòu)：,難！,（多個(gè)頂點(diǎn)，無(wú)序可言，無(wú)法僅以頂點(diǎn)坐標(biāo)表達(dá)相互關(guān)系）,可用多重鏈表,鄰接矩陣(數(shù)組)表示法 鄰接表(鏈?zhǔn)?表示法 十字鏈表表示法 鄰接多重表表示法,但可用數(shù)組描述元素間關(guān)系。,非線性結(jié)構(gòu)（m :n）,鄰接矩陣,鄰接表 十字鏈表 鄰接多重表,各種表示法成立的原則：存入電腦后能惟一復(fù)原,.,16, 建立一個(gè)頂點(diǎn)表和一個(gè)鄰接矩陣。,1. 鄰接矩陣（數(shù)組）表示法,例1：,鄰接矩陣：,A.Edge =,（ v1 v2 v3 v4 v5 ）,v1 v2 v3 v4 v5,0 1 0 1 0 1 0 1 0 1 0 1

9、0 1 1 1 0 1 0 1 0 1 1 1 0,分析1：無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的； 分析2：頂點(diǎn)i 的度第 i 行 (列) 中1 的個(gè)數(shù)； 特別：完全圖的鄰接矩陣中，對(duì)角元素為0，其余全1。,頂點(diǎn)表：,無(wú)向圖的鄰接矩陣如何表示？,記錄各個(gè)頂點(diǎn)信息,表示各個(gè)頂點(diǎn)之間關(guān)系, 設(shè)圖 A = (V, E) 有 n 個(gè)頂點(diǎn)，則圖的鄰接矩陣是一個(gè)二維數(shù)組 A.Edgenn，定義為：,0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0,0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0,.,17,例2 ：有向

10、圖的鄰接矩陣如何表示？,分析1：有向圖的鄰接矩陣可能是不對(duì)稱(chēng)的。 分析2：頂點(diǎn)vi的出度=第i行元素之和，OD(vi )= A.Edge i j 頂點(diǎn)vi的入度=第i列元素之和。ID(vi )= A.Edge j i 頂點(diǎn)的度=第i行元素之和+第i列元素之和, 即：TD( vi ) = OD( vi ) + ID( vi ),鄰接矩陣：,A.Edge =,( v1 v2 v3 v4 ),v1 v2 v3 v4,0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0,注：在有向圖的鄰接矩陣中， 第i行含義：以結(jié)點(diǎn)vi為尾的弧(即出度邊）； 第i列含義：以結(jié)點(diǎn)vi為頭的弧(即入度邊）。,頂

11、點(diǎn)表：,0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0,0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0,.,18,容易實(shí)現(xiàn)圖的操作，如：求某頂點(diǎn)的度、判斷頂點(diǎn)之間是否有邊（?。⒄翼旤c(diǎn)的鄰接點(diǎn)等等。 n個(gè)頂點(diǎn)需要n*n個(gè)單元存儲(chǔ)邊(弧);空間效率為O(n2)。,例3 ： 有權(quán)圖（即網(wǎng)絡(luò)）的鄰接矩陣如何表示？,定義：,以有向網(wǎng)為例：,鄰接矩陣：, ,N.Edge =,( v1 v2 v3 v4 v5 v6 ),鄰接矩陣法優(yōu)點(diǎn)：,鄰接矩陣法缺點(diǎn)：,頂點(diǎn)表：,5 7 4 8 9 5 6 5 3 1, 5 7 4 8 9 5 6 5 3 1 ,v1 v2 v3 v4 v

12、5 v6,對(duì)稀疏圖而言尤其浪費(fèi)空間。,.,19,注：用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)表和鄰接矩陣 #define INFINITY INT_MAX /最大值 #define MAX_VERTEX_NUM 20 /假設(shè)的最大頂點(diǎn)數(shù) Typedef enum DG, DN, AG, AN GraphKind; /有向/無(wú)向圖，有向/無(wú)向網(wǎng),圖的鄰接矩陣在機(jī)內(nèi)如何表示？ （參見(jiàn)教材P161）,對(duì)于n個(gè)頂點(diǎn)的圖或網(wǎng)，空間效率=O(n2),Typedef struct ArcCell /弧（邊）結(jié)點(diǎn)的定義 VRType adj; /頂點(diǎn)間關(guān)系，無(wú)權(quán)圖取1或0；有權(quán)圖取權(quán)值類(lèi)型 InfoType *info; /該

13、弧相關(guān)信息的指針 ArcCell, AdjMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM ;,Typedef struct /圖的定義 VertexType vexs MAX_VERTEX_NUM ; /頂點(diǎn)表，用一維向量即可(n) AdjMatrix arcs; /鄰接矩陣n*n Int Vernum, arcnum; /頂點(diǎn)總數(shù)n，弧（邊）總數(shù)e GraphKind kind; /圖的種類(lèi)標(biāo)志 Mgraph;,.,20,Status CreateUDN(Mgraph /輸入n個(gè)頂點(diǎn)值，存入一維向量,例：用鄰接矩陣生成無(wú)向網(wǎng)的算法（參見(jiàn)教材P162）,對(duì)于n個(gè)頂點(diǎn)e

14、條弧的網(wǎng)， 建網(wǎng)時(shí)間效率 = O(n+n2+e*n),for(i=0; iG.vexnum; +i) /對(duì)鄰接矩陣n*n個(gè)單元初始化，adj=,info=NULL for(j=0;jG.vexnum;+j) G.arcsij=INFINITY, NULL;,for(k=0;kG.arcnum;+k) /給鄰接矩陣有關(guān)單元賦初值(循環(huán)次數(shù)弧數(shù)e scanf( /如果弧有信息則填入 G.arcsij = G.arcs j i； /無(wú)向網(wǎng)是對(duì)稱(chēng)矩陣 ,return OK; / CreateUDN,.,21,2. 鄰接表（鏈?zhǔn)剑┍硎痉? 對(duì)每個(gè)頂點(diǎn)vi 建立一個(gè)單鏈表，把與vi有關(guān)聯(lián)的邊的信息（即度或

15、出度邊）鏈接起來(lái)，表中每個(gè)結(jié)點(diǎn)都設(shè)為3個(gè)域:, 每個(gè)單鏈表還應(yīng)當(dāng)附設(shè)一個(gè)頭結(jié)點(diǎn)（設(shè)為2個(gè)域），存vi信息；,表結(jié)點(diǎn),頭結(jié)點(diǎn),鄰接點(diǎn)域，表示vi 鄰接點(diǎn)的位置,鏈域，指向下一個(gè)邊或弧的結(jié)點(diǎn),數(shù)據(jù)域，與邊有關(guān)信息（如權(quán)值）,數(shù)據(jù)域，存儲(chǔ)頂點(diǎn)vi 信息,鏈域，指向單鏈表的第一個(gè)結(jié)點(diǎn), 每個(gè)單鏈表的頭結(jié)點(diǎn)另外用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。,.,22,例1：無(wú)向圖的鄰接表如何表示？,鄰接表,例2：有向圖的鄰接表如何表示？,鄰接表(出邊),逆鄰接表(入邊),請(qǐng)注意：鄰接表不惟一！因各個(gè)邊結(jié)點(diǎn)的鏈入順序是任意的。,v1鄰接點(diǎn)v4的位置,此無(wú)權(quán)圖未開(kāi)第3分量,.,23,例3：已知某網(wǎng)的鄰接（出邊）表，請(qǐng)畫(huà)出該網(wǎng)絡(luò)。,8

16、0,64,1,2,5,當(dāng)鄰接表的存儲(chǔ)結(jié)構(gòu)形成后，圖便唯一確定！,.,24,分析1: 對(duì)于n個(gè)頂點(diǎn)e條邊的無(wú)向圖，鄰接表中除了n個(gè)頭結(jié)點(diǎn)外，只有2e個(gè)表結(jié)點(diǎn),空間效率為O(n+2e)。 若是稀疏圖(en2)，則比鄰接矩陣表示法O(n2)省空間。,鄰接表存儲(chǔ)法的特點(diǎn)：,分析2:在有向圖中，鄰接表中除了n個(gè)頭結(jié)點(diǎn)外，只有e個(gè)表結(jié)點(diǎn),空間效率為O(n+e)。若是稀疏圖，則比鄰接矩陣表示法合適。,它其實(shí)是對(duì)鄰接矩陣法的一種改進(jìn),怎樣計(jì)算無(wú)向圖頂點(diǎn)的度？,鄰接表的缺點(diǎn)：,怎樣計(jì)算有向圖頂點(diǎn)的出度？ 怎樣計(jì)算有向圖頂點(diǎn)的入度？ 怎樣計(jì)算有向圖頂點(diǎn)Vi的度：,需遍歷全表,鄰接表的優(yōu)點(diǎn)：,TD(Vi)=單鏈表中

17、鏈接的結(jié)點(diǎn)個(gè)數(shù),OD(Vi)單鏈出邊表中鏈接的結(jié)點(diǎn)數(shù) I D( Vi ) 鄰接點(diǎn)為Vi的弧個(gè)數(shù),TD(Vi) = OD( Vi ) + I D( Vi ),空間效率高；容易尋找頂點(diǎn)的鄰接點(diǎn)；,判斷兩頂點(diǎn)間是否有邊或弧，需搜索兩結(jié)點(diǎn)對(duì)應(yīng)的單鏈表，沒(méi)有鄰接矩陣方便。,.,25,討論：鄰接表與鄰接矩陣有什么異同之處？,1. 聯(lián)系：鄰接表中每個(gè)鏈表對(duì)應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點(diǎn)個(gè)數(shù)等于一行中非零元素的個(gè)數(shù)。 2. 區(qū)別： 對(duì)于任一確定的無(wú)向圖，鄰接矩陣是唯一的（行列號(hào)與頂點(diǎn)編號(hào)一致），但鄰接表不唯一（鏈接次序與頂點(diǎn)編號(hào)無(wú)關(guān)）。 鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。

18、 3. 用途： 鄰接矩陣多用于稠密圖的存儲(chǔ)（e接近n(n-1)/2)； 而鄰接表多用于稀疏圖的存儲(chǔ)（en2),.,26,圖的鄰接表在機(jī)內(nèi)如何表示？ （參見(jiàn)教材P163）,#define MAX_VERTEX_NUM 20 /假設(shè)的最大頂點(diǎn)數(shù),空間效率為O(n+2e)或O(n+e) 時(shí)間效率為O(n+e*n),Typedef struct VNode /頂點(diǎn)結(jié)構(gòu) VertexType data; /頂點(diǎn)信息 ArcNode * firstarc; /指向依附該頂點(diǎn)的第一條弧的指針 VNode, AdjList MAX_VERTEX_NUM ;,Typedef struct /圖結(jié)構(gòu) AdjLis

19、t vertics ; /應(yīng)包含鄰接表 int vexnum, arcnum; /應(yīng)包含頂點(diǎn)總數(shù)和弧總數(shù) int kind; /還應(yīng)說(shuō)明圖的種類(lèi)（用標(biāo)志） ALGraph;,Typedef struct ArcNode /弧結(jié)構(gòu) int adjvex; /該弧所指向的頂點(diǎn)位置 struct ArcNode *nextarcs; /指向下一條弧的指針 InfoArc *info; /該弧相關(guān)信息的指針 ArcNode；,圖的鄰接表生成算法作為自測(cè)題,.,27,它是有向圖的另一種鏈?zhǔn)浇Y(jié)構(gòu)。 思路：將鄰接矩陣用鏈表存儲(chǔ)，是鄰接表、逆鄰接表的結(jié)合。 1、開(kāi)設(shè)弧結(jié)點(diǎn)，設(shè)5個(gè)域（每段弧是一個(gè)數(shù)據(jù)元素） 2

20、、開(kāi)設(shè)頂點(diǎn)結(jié)點(diǎn)，設(shè)3個(gè)域（每個(gè)頂點(diǎn)也是一個(gè)數(shù)據(jù)元素）,data : 頂點(diǎn)信息 Firstin : 以頂點(diǎn)為弧頭的第一條弧結(jié)點(diǎn) Firstout: 以頂點(diǎn)為弧尾的第一條弧結(jié)點(diǎn),頂點(diǎn)結(jié)點(diǎn),弧結(jié)點(diǎn),3. 十字鏈表表示法,tailvex: 弧尾頂點(diǎn)位置 headvex: 弧頭頂點(diǎn)位置 hlink: 弧頭相同的下一弧位置 tlink: 弧尾相同的下一弧位置 info: 弧信息,n個(gè)頂點(diǎn)的集合怎樣儲(chǔ)存？,仍用順序存儲(chǔ)結(jié)構(gòu),.,28,例：畫(huà)出有向圖的十字鏈表。,十字鏈表優(yōu)點(diǎn)：容易操作，如求頂點(diǎn)的入度、出度等。,此無(wú)權(quán)圖未開(kāi)第4分量,空間復(fù)雜度和建表的時(shí)間復(fù)雜度都與鄰接表相同。,.,29,#define MA

21、X_VERTEX_NUM 20,十字鏈表存儲(chǔ)結(jié)構(gòu)描述：,Typedef struct ArcBox /弧結(jié)點(diǎn)結(jié)構(gòu)，5分量 int tailvex , headvex ; struct ArcBox * hlink , tlink; InfoType *info; ArcBox;,Typedef struct VexNode /頂點(diǎn)結(jié)構(gòu), 3分量 VertexType data; ArcBox * firstin,*firstout; VexNode;,Typedef struct /圖結(jié)構(gòu),整體概念 VexNode xlist MAX_VERTEX_NUM ; /表頭向量 int vexnum

22、, arcnum; OLGraph;,.,30,這是無(wú)向圖的另一種存儲(chǔ)結(jié)構(gòu)，當(dāng)對(duì)邊操作時(shí)建議采用此種結(jié)構(gòu)存儲(chǔ)。 1、設(shè)立邊結(jié)點(diǎn)， 6個(gè)域（每條邊是一個(gè)數(shù)據(jù)元素） 2、設(shè)立頂點(diǎn)結(jié)點(diǎn)， 2個(gè)域（每個(gè)頂點(diǎn)也是一個(gè)數(shù)據(jù)元素）,邊結(jié)點(diǎn),data : 存儲(chǔ)頂點(diǎn)信息 Firstedge : 依附頂點(diǎn)的第一條邊結(jié)點(diǎn),頂點(diǎn)結(jié)點(diǎn),4. 鄰接多重表表示法,mark：標(biāo)志域 ivex， jvex : 邊依附的兩個(gè)頂點(diǎn)位置 ilink: 指向下一條依附頂點(diǎn) i 的邊位置 jlink; 指向下一條依附頂點(diǎn) j 的邊位置 info: 邊信息,n個(gè)頂點(diǎn)的集合怎樣儲(chǔ)存？,仍用順序存儲(chǔ)結(jié)構(gòu),.,31,例：畫(huà)出無(wú)向圖的鄰接多重表,

23、鄰接多重表優(yōu)點(diǎn)： 容易操作，如求頂點(diǎn)的度等。,空間復(fù)雜度和建表的時(shí)間復(fù)雜度都與鄰接表相同。,此無(wú)權(quán)圖未開(kāi)第6分量,.,32,一、深度優(yōu)先搜索 二、廣度優(yōu)先搜索,7.3 圖的遍歷,遍歷定義：從已給的連通圖中某一頂點(diǎn)出發(fā)，沿著一些邊，訪遍圖中所有的頂點(diǎn)，且使每個(gè)頂點(diǎn)僅被訪問(wèn)一次，就叫做圖的遍歷，它是圖的基本運(yùn)算。,遍歷實(shí)質(zhì)：找每個(gè)頂點(diǎn)的鄰接點(diǎn)的過(guò)程。 圖的特點(diǎn)：圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問(wèn)完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問(wèn)過(guò)的頂點(diǎn)。,解決思路：可設(shè)置一個(gè)輔助數(shù)組 visited n ，用來(lái)標(biāo)記每個(gè)被訪問(wèn)過(guò)的頂點(diǎn)。它的初始狀態(tài)為0，在圖的遍歷過(guò)程中，一旦某

24、一個(gè)頂點(diǎn)i 被訪問(wèn)，就立即改 visited i為1，防止它被多次訪問(wèn)。,圖常用的遍歷：,怎樣避免重復(fù)訪問(wèn)？,.,33,一、深度優(yōu)先搜索( DFS ),基本思想：仿樹(shù)的先序遍歷過(guò)程。,Depth_First Search,v1,DFS 結(jié)果,例1：,v2,v4,v8,v5,v3,v6,v7,例2：,v2 v1 v3 v5 ,DFS 結(jié)果,v4 v6,起點(diǎn),起點(diǎn),遍歷步驟,應(yīng)退回到V8，因?yàn)閂2已有標(biāo)記,.,34,深度優(yōu)先搜索（遍歷）步驟：,詳細(xì)歸納： 在訪問(wèn)圖中某一起始頂點(diǎn) v 后，由 v 出發(fā)，訪問(wèn)它的任一鄰接頂點(diǎn) w1； 再?gòu)?w1 出發(fā)，訪問(wèn)與 w1鄰接但還未被訪問(wèn)過(guò)的頂點(diǎn) w2； 然后

25、再?gòu)?w2 出發(fā)，進(jìn)行類(lèi)似的訪問(wèn)， 如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問(wèn)過(guò)的頂點(diǎn) u 為止。 接著，退回一步，退到前一次剛訪問(wèn)過(guò)的頂點(diǎn)，看是否還有其它未被訪問(wèn)的鄰接頂點(diǎn)。 如果有，則訪問(wèn)此頂點(diǎn)，之后再?gòu)拇隧旤c(diǎn)出發(fā)，進(jìn)行與前述類(lèi)似的訪問(wèn)； 如果沒(méi)有，就再退回一步進(jìn)行搜索。重復(fù)上述過(guò)程，直到連通圖中所有頂點(diǎn)都被訪問(wèn)過(guò)為止。,簡(jiǎn)單歸納： 訪問(wèn)起始點(diǎn) v; 若v的第1個(gè)鄰接點(diǎn)沒(méi)訪問(wèn)過(guò)，深度遍歷此鄰接點(diǎn)； 若當(dāng)前鄰接點(diǎn)已訪問(wèn)過(guò)，再找v的第2個(gè)鄰接點(diǎn)重新遍歷。,.,35,討論1：計(jì)算機(jī)如何實(shí)現(xiàn)DFS？,DFS 結(jié)果,鄰接矩陣 A,輔助數(shù)組 visited n ,起點(diǎn),開(kāi)輔助數(shù)組 visited n

26、 ！,例：,v2,v1,v3,v5,v4,v6,請(qǐng)注意逐級(jí)回退是遞歸概念,.,36,for( j=1; j=n; j+) if ( Av, j / DFS1,討論2： DFS算法如何編程？,DFS1(A, n, v) visit（v）; visitedv=1;,可以用遞歸算法！,/Ann為鄰接矩陣，v為起始頂點(diǎn)(編號(hào)）,/訪問(wèn)（例如打?。╉旤c(diǎn)v,Av,j 1 有鄰接點(diǎn),visited n =0 未訪問(wèn)過(guò),/訪問(wèn)后立即修改輔助數(shù)組標(biāo)志,/從v所在行從頭搜索鄰接點(diǎn),（教材上DFS遞歸算法見(jiàn)P169）,.,37,討論3：在圖的鄰接表中如何進(jìn)行DFS？,DFS 結(jié)果,輔助數(shù)組 visited n ,例

27、：,照樣借用visited n ！,起點(diǎn),0 1 2 3,注意：在鄰接表中，并非每個(gè)鏈表元素（表結(jié)點(diǎn)）都被掃描到,因此遍歷速度很快。,v0,v1,v2,v3,.,38,討論4： 鄰接表的DFS算法如何編程？,（書(shū)上沒(méi)有，僅供參考）,/訪問(wèn)后立即修改輔助數(shù)組標(biāo)志,仍用遞歸算法,Int visited; /初始化輔助數(shù)組,元素均為0 Void DFS(List,v,p) /設(shè)p為v的頭指針 visit(v); /訪問(wèn)起點(diǎn) visitedv=1; /起點(diǎn)已訪問(wèn),0變1 while(p-link) /當(dāng)存在起點(diǎn)的第一個(gè)鄰接點(diǎn)時(shí) p=p-link; v=p-data; if(!visitedv)DFS(

28、List,v,p); /進(jìn)行遞歸 return; ,.,39,DFS 算法效率分析:,（設(shè)圖中有 n 個(gè)頂點(diǎn)，e 條邊） 如果用鄰接矩陣來(lái)表示圖，遍歷圖中每一個(gè)頂點(diǎn)都要從頭掃描該頂點(diǎn)所在行，因此遍歷全部頂點(diǎn)所需的時(shí)間為O(n2)。 如果用鄰接表來(lái)表示圖，雖然有 2e 個(gè)表結(jié)點(diǎn)，但只需掃描 e 個(gè)結(jié)點(diǎn)即可完成遍歷，加上訪問(wèn) n個(gè)頭結(jié)點(diǎn)的時(shí)間，因此遍歷圖的時(shí)間復(fù)雜度為O(n+e)。,結(jié) 論： 稠密圖適于在鄰接矩陣上進(jìn)行深度遍歷； 稀疏圖適于在鄰接表上進(jìn)行深度遍歷。,.,40,二、廣度優(yōu)先搜索( BFS ),基本思想：仿樹(shù)的層次遍歷過(guò)程。,Breadth_First Search,v1,BFS 結(jié)果

29、,例1：,例2：,v3 ,BFS 結(jié)果,v4 v5 ,起點(diǎn),遍歷步驟,起點(diǎn),v2 v1 v6 ,v9 v8 v7,.,41,廣度優(yōu)先搜索（遍歷）步驟：,簡(jiǎn)單歸納： 在訪問(wèn)了起始點(diǎn)v之后，依次訪問(wèn) v的鄰接點(diǎn)； 然后再依次（順序）訪問(wèn)這些點(diǎn)（下一層）中未被訪問(wèn)過(guò)的鄰接點(diǎn)； 直到所有頂點(diǎn)都被訪問(wèn)過(guò)為止。,廣度優(yōu)先搜索是一種分層的搜索過(guò)程，每向前走一步可能訪問(wèn)一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有回退的情況。 因此，廣度優(yōu)先搜索不是一個(gè)遞歸的過(guò)程，其算法也不是遞歸的。,.,42,討論1：計(jì)算機(jī)如何實(shí)現(xiàn)BFS？,鄰接表,寬度優(yōu)先搜索要借助隊(duì)列！,例：,起點(diǎn),輔助隊(duì)列,v2已訪問(wèn)過(guò)了,V2入隊(duì),visited

30、 n 仍需要,BFS 遍歷結(jié)果,.,43,while(rear!=front) /隊(duì)不空時(shí) front=(front+1)%n; v=qfront; /訪問(wèn)過(guò)的頂點(diǎn)出隊(duì) p=Listv.firstarc; /P指向第1個(gè)鄰接點(diǎn) while(!p) if(! Visitedadjvex(p) )/未到表尾，且鄰接域未訪問(wèn)過(guò)， Visit(adjvex(p); Visitedadjvex(p)=1;/則先輸出再改標(biāo)記， rear=(rear+1)%n; qrear= adjvex(p) /最后再入隊(duì) p=nextarc(p); /指向單鏈表中下一個(gè)鄰接點(diǎn) return / BFS1,討論2： BF

31、S算法如何編程？,BFS1(List, n, v) /List為鄰接表，v為起點(diǎn)，Qn為輔助隊(duì)列 Visit(v); Visitedv=1; /訪問(wèn)（例如打?。╉旤c(diǎn)v并修改標(biāo)志,層次遍歷應(yīng)當(dāng)用隊(duì)列！,（教材上BFS算法見(jiàn)P170）,front=n-1;rear=0; /隊(duì)列指針初始化 qrear=v; /起始點(diǎn)入隊(duì),.,44,BFS 算法效率分析:,DFS與BFS之比較： 空間復(fù)雜度相同，都是O(n)(借用堆棧或隊(duì)列裝n個(gè)頂點(diǎn)）； 時(shí)間復(fù)雜度只與存儲(chǔ)結(jié)構(gòu)（鄰接矩陣或鄰接表）有關(guān)，而與搜索路徑無(wú)關(guān)。,如果使用鄰接表來(lái)表示圖，則BFS循環(huán)的總時(shí)間代價(jià)為 d0 + d1 + + dn-1 = O(e

32、)，其中的 di 是頂點(diǎn) i 的度。 如果使用鄰接矩陣，則BFS對(duì)于每一個(gè)被訪問(wèn)到的頂點(diǎn)，都要循環(huán)檢測(cè)矩陣中的整整一行（ n 個(gè)元素），總的時(shí)間代價(jià)為O(n2)。,（設(shè)圖中有 n 個(gè)頂點(diǎn)，e 條邊）,.,45,7.4 圖的連通性問(wèn)題,1. 求圖的生成樹(shù) 2. 求最小生成樹(shù),.,46,1.求圖的生成樹(shù)（或生成森林）,生成樹(shù)：是一個(gè)極小連通子圖，它含有圖中全部頂點(diǎn)，但只有n-1條邊。 生成森林：由若干棵生成樹(shù)組成，含全部頂點(diǎn)，但構(gòu)成這些樹(shù)的邊是最少的。,思考1：若對(duì)連通圖進(jìn)行遍歷，得到的是什么？ 得到的將是一個(gè)極小連通子圖，即圖的生成樹(shù)！ 由深度優(yōu)先搜索得到的生成樹(shù)，稱(chēng)為深度優(yōu)先搜索生成樹(shù)。 由廣

33、度優(yōu)先搜索得到的生成樹(shù)，稱(chēng)為廣度優(yōu)先搜索生成樹(shù)。 思考2：若對(duì)非連通圖進(jìn)行遍歷，得到的是什么？ 得到的將是各連通分量的生成樹(shù)，即圖的生成森林！,.,47,例1 ：畫(huà)出下圖的生成樹(shù),DFS生成樹(shù),鄰接表,v0,v2,v1,v4,v3,BFS生成樹(shù),v0,無(wú)向連通圖,.,48,其實(shí)由鄰接矩陣或鄰接表也能直接畫(huà)出生成森林,例2：畫(huà)出下圖的生成森林（或極小連通子圖）,求解步驟： Step1:先求出鄰接矩陣或鄰接表； Step2:寫(xiě)出DFS或BFS結(jié)果序列； Step3:畫(huà)出對(duì)應(yīng)子圖或生成森林。,這是一個(gè)無(wú)向非連通圖（參見(jiàn)教材P170-171例）,下面選用鄰接表方式來(lái)求深度優(yōu)先搜索生成森林,生成森林的定

34、義（對(duì)有向或無(wú)向圖均適用）：是若干棵生成樹(shù)的集合，含全部頂點(diǎn)，但構(gòu)成這些樹(shù)的邊或弧是最少的。,.,49,子圖1：,再寫(xiě)出DFS結(jié)果ABMJLCF DE GHKI,先寫(xiě)出鄰接表（或鄰接矩陣）：,子圖2：,子圖3：,最小連通！,怎樣找3個(gè)根？,.,50,子圖 (或連通分量),生成森林,.,51,2. 求最小生成樹(shù),首先明確： 使用不同的遍歷圖的方法，可以得到不同的生成樹(shù)；從不同的頂點(diǎn)出發(fā)，也可能得到不同的生成樹(shù)。 按照生成樹(shù)的定義，n 個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)的生成樹(shù)肯定有 n 個(gè)頂點(diǎn)和僅僅n-1 條邊。,即有權(quán)圖,構(gòu)造最小生成樹(shù)的準(zhǔn)則 必須只使用該網(wǎng)絡(luò)中的邊來(lái)構(gòu)造最小生成樹(shù)； 必須使用且僅使用n-1條邊

35、來(lái)聯(lián)結(jié)網(wǎng)絡(luò)中的n個(gè)頂點(diǎn)； 不能使用產(chǎn)生回路的邊。,目標(biāo)：在網(wǎng)絡(luò)的多個(gè)生成樹(shù)中，尋找一個(gè)各邊權(quán)值之和最小的生成樹(shù)。,.,52,欲在n個(gè)城市間建立通信網(wǎng)，則n個(gè)城市應(yīng)鋪n-1條線路；但因?yàn)槊織l線路都會(huì)有對(duì)應(yīng)的經(jīng)濟(jì)成本，而n個(gè)城市可能有 n(n-1)/2 條線路，那么，如何選擇n1條線路使總費(fèi)用最少？,典型用途：,先建立數(shù)學(xué)模型： 頂點(diǎn)表示城市，有n個(gè)； 邊表示線路，有n1條； 邊的權(quán)值表示線路的經(jīng)濟(jì)代價(jià)； 連通網(wǎng)表示n個(gè)城市間的通信網(wǎng)。,顯然此連通網(wǎng)是一棵生成樹(shù)！,問(wèn)題抽象： n個(gè)頂點(diǎn)的生成樹(shù)很多，需要從中選一棵代價(jià)最小的生成樹(shù)，即該樹(shù)各邊的代價(jià)之和最小。此樹(shù)便稱(chēng)為最小生成樹(shù)MST。,Minimu

36、m cost Spanning Tree,.,53,討論：如何求得最小生成樹(shù)？,最小生成樹(shù)（MST）的 性質(zhì)如下：,若U集是V的一個(gè)非空子集，若(u0, v0)是一條最小權(quán)值的邊，其中u0U，v0V-U；則：(u0, v0)必在最小生成樹(shù)上。,設(shè)想一下：先把權(quán)值最小的邊歸入生成樹(shù)內(nèi)，逐個(gè)遞增，舍去回路邊，則得到的很可能就是最小生成樹(shù)！,求MST有多種算法，但最常用的是以下兩種：,Kruskal（克魯斯卡爾）算法 Prim（普里姆）算法,Kruskal算法特點(diǎn)：將邊歸并，適于求稀疏網(wǎng)的最小生成樹(shù)。 Prime算法特點(diǎn): 將頂點(diǎn)歸并，與邊數(shù)無(wú)關(guān)，適于稠密網(wǎng)。,54,Kruskal算法示例：對(duì)邊操作

37、，歸并邊,Kruskal算法效率分析：,Kruskal算法的時(shí)間效率O（elog2e）,Kruskal算法是歸并邊，適用于稀疏圖（用鄰接表）,.,55,普利姆（Prim）算法示例： 歸并頂點(diǎn),1,Prim算法效率分析：,Prim算法的時(shí)間效率O（n2）,Prim算法是歸并頂點(diǎn)，適用于稠密網(wǎng)。,.,56,圖5-4-5 構(gòu)造最小生成樹(shù)過(guò)程中輔助數(shù)組中各分量的值,圖5-4-5 構(gòu)造最小生成樹(shù)過(guò)程中輔助數(shù)組中各分量的值,.,57,7.5 有向無(wú)環(huán)圖及其應(yīng)用,1. 拓?fù)渑判?2. 求關(guān)鍵路徑,.,58,1 拓?fù)渑判?在工程實(shí)踐中，一個(gè)工程項(xiàng)目往往由若干個(gè)子項(xiàng)目組成，這些子項(xiàng)目間往往有多種關(guān)系： 先后關(guān)系

38、，即必須在一子項(xiàng)目完成后，才能開(kāi)始實(shí)施另一個(gè)子項(xiàng)目； 子項(xiàng)目之間無(wú)次序要求，即兩個(gè)子項(xiàng)目可以同時(shí)進(jìn)行，互不影響。 在工廠中，一件設(shè)備的生產(chǎn)包括許多工序，各工序之間也存在這兩種關(guān)系。 學(xué)校里某個(gè)專(zhuān)業(yè)的課程學(xué)習(xí)，有些課程是基礎(chǔ)課，它們可以獨(dú)立于其它課程，即無(wú)前導(dǎo)課程；有些課程必須在一些課程學(xué)完后才能開(kāi)始學(xué)。,.,59,這些類(lèi)似的問(wèn)題都可以用有向圖來(lái)表示，我們把這些子項(xiàng)目、工序、課程看成一個(gè)個(gè)頂點(diǎn)稱(chēng)之為活動(dòng)(Activity)。 如果從頂點(diǎn)Vi到Vj之間存在有向邊,則表示活動(dòng)i必須先于活動(dòng)j進(jìn)行。這種圖稱(chēng)做頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(Activity On Vertex network,簡(jiǎn)稱(chēng)AOV網(wǎng)絡(luò))。

39、例如表5-6-1是某校計(jì)算機(jī)專(zhuān)業(yè)的課程及其相互之間的關(guān)系，它對(duì)應(yīng)的AOV網(wǎng)絡(luò)如圖5-6-1所示。,.,60,表5-6-1 某專(zhuān)業(yè)課程設(shè)置,.,61,圖5-6-1（a） AOV網(wǎng)絡(luò),.,62,在AOV網(wǎng)絡(luò)中，如果頂點(diǎn)Vi的活動(dòng)必須在頂點(diǎn)Vj的活動(dòng)以前進(jìn)行，則稱(chēng)Vi為Vj的前趨頂點(diǎn)，而稱(chēng)Vj為Vi的后繼頂點(diǎn)。這種前趨后繼關(guān)系有傳遞性。 AOV網(wǎng)絡(luò)中一定不能有有向環(huán)路。例如在圖5-6-1（b）那樣的有向環(huán)路中，V2是V3的前趨頂點(diǎn)，V1是V2的前趨頂點(diǎn)，V3又是V1的前趨頂點(diǎn)，環(huán)路表示頂點(diǎn)之間的先后關(guān)系進(jìn)入了死循環(huán)。 因此，對(duì)給定的AOV網(wǎng)絡(luò)首先要判定網(wǎng)絡(luò)中是否存在環(huán)路，只有有向無(wú)環(huán)路網(wǎng)絡(luò)在應(yīng)用中才

40、有實(shí)際意義。,.,63,圖5-6-1（b） 有向環(huán)路,.,64,所謂“拓?fù)渑判颉本褪菍OV網(wǎng)絡(luò)中的各個(gè)頂點(diǎn)(各個(gè)活動(dòng))排列成一個(gè)線性有序序列，使得所有要求的前趨、后繼關(guān)系都能得到滿足。 由于AOV網(wǎng)絡(luò)中有些頂點(diǎn)之間沒(méi)有次序要求，它們?cè)谕負(fù)溆行蛐蛄兄械奈恢每梢匀我忸嵉?，所以拓?fù)渑判虻慕Y(jié)果一般并不是唯一的。 通過(guò)拓?fù)渑判蜻€可以判斷出此AOV網(wǎng)絡(luò)是否包含有有向環(huán)路，若有向圖G所有頂點(diǎn)都在拓?fù)渑判蛐蛄兄校瑒tAOV網(wǎng)絡(luò)必定不包含有有向環(huán)路。,.,65,拓?fù)渑判蚍椒?(1) 在AOV網(wǎng)中選擇一個(gè)沒(méi)有前驅(qū)（即入度為0）的頂點(diǎn)，并把它輸出； (2) 從網(wǎng)絡(luò)中刪去該頂點(diǎn)和從該頂點(diǎn)發(fā)出的所有有向邊； (3) 重

41、復(fù)執(zhí)行上述兩步，直到網(wǎng)中所有的頂點(diǎn)都被輸出 (此時(shí)，原AOV網(wǎng)絡(luò)中的所有頂點(diǎn)和邊就都被刪除掉了)。 如果進(jìn)行到某一步，無(wú)法找到無(wú)前趨的頂點(diǎn)，則說(shuō)明此AOV網(wǎng)絡(luò)中存在有向環(huán)路，遇到這種情況，拓?fù)渑判蚓蜔o(wú)法進(jìn)行了。,.,66,C1,C10,C11,C6,C2,C12,C4,C8,C3,C7,C5,C9,拓?fù)溆行蛐蛄校?（C1，C2，C3，C4，C5，C7，C9，C10，C11，C6，C12，C8） （C9，C10，C11，C6，C1，C12，C4，C2，C3，C5，C7，C8）,.,67,0,1,0,1,0,2,1,1,.,68,圖5-6-2 AOV網(wǎng)及拓?fù)湫蛄械漠a(chǎn)生過(guò)程,a b c d e f,

42、（a）AOV網(wǎng)；(b)輸出v0后；（c）輸出v5后；（d）輸出v3后；（e）輸出v2后；（f）輸出v1后。 這樣得到的一個(gè)拓?fù)渑判蛐蛄袨椋簐0, v5, v3, v2, v1, v4,.,69,為了實(shí)現(xiàn)拓?fù)渑判?，針?duì)上述兩個(gè)步驟，采用鄰接表作為有向圖的存儲(chǔ)結(jié)構(gòu)，并且在表結(jié)點(diǎn)中增設(shè)一個(gè)入度，存放頂點(diǎn)的入度。例如圖5-6-2種的AOV網(wǎng)的鄰接表如圖5-6-3（a）所示。這樣，入度域?yàn)榱愕谋斫Y(jié)點(diǎn)及時(shí)無(wú)前驅(qū)的頂點(diǎn)，刪除該頂點(diǎn)及它為尾的弧的操作，則可以轉(zhuǎn)換為將它的所有弧頭頂點(diǎn)的入度減1來(lái)實(shí)現(xiàn),.,70,.,71,A,B,C,D,E,F,G,H,I,.,72,兩個(gè)事件之間只能畫(huà)一條箭線，表示一項(xiàng)作業(yè)。若兩

43、項(xiàng)或兩項(xiàng)以上作業(yè)同時(shí)開(kāi)始或結(jié)束，就要引進(jìn)虛事件和虛作業(yè)，虛作業(yè)不消耗資源。,.,73,3各項(xiàng)作業(yè)之間的關(guān)系及它們?cè)诰W(wǎng)絡(luò)圖上的表達(dá)方式如下： 作業(yè)a結(jié)束后可以開(kāi)始b和c，見(jiàn)圖(a)； 作業(yè)c在a和b均結(jié)束后才能開(kāi)始，見(jiàn)圖(b)；,.,74,a、b兩項(xiàng)作業(yè)均結(jié)束后可以開(kāi)始c和d，見(jiàn)圖(c)； 作業(yè)c在a結(jié)束后即可進(jìn)行，但作業(yè)d必須同時(shí)在a和b結(jié)束后才能開(kāi)始，見(jiàn)圖(d)。,.,75,表71,.,76,C,B,E,D,A,X2,X1,K,G,I,H,0,F,J,0,.,77,2.關(guān)鍵路徑,關(guān)鍵路徑法是采用邊表示活動(dòng)(Activity On Edge)的網(wǎng)絡(luò)，簡(jiǎn)稱(chēng)為AOE網(wǎng)絡(luò)。 AOE網(wǎng)絡(luò)是一個(gè)帶權(quán)的有

44、向無(wú)環(huán)路圖，其中，每個(gè)頂點(diǎn)代表一個(gè)事件(Event)，事件說(shuō)明某些活動(dòng)或某一項(xiàng)活動(dòng)的完成，即階段性的結(jié)果。 離開(kāi)某頂點(diǎn)的各條邊所代表的活動(dòng)，只有在該頂點(diǎn)對(duì)應(yīng)的事件出現(xiàn)后才能開(kāi)始。 權(quán)值表示活動(dòng)持續(xù)的時(shí)間。,.,78,圖5-6-4 一個(gè)AOE網(wǎng)絡(luò),.,79,AOE網(wǎng)絡(luò),通常利用AOE網(wǎng)絡(luò)可以研究以下兩個(gè)問(wèn)題： (1) 完成整個(gè)工程至少需要多少時(shí)間？ (2) 哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？,.,80,關(guān)鍵路徑,完成工程所需的時(shí)間就是從開(kāi)始點(diǎn)起進(jìn)行到結(jié)束點(diǎn)止所需的時(shí)間。 路徑長(zhǎng)度是指沿路徑各邊的權(quán)值之和，也就是這些邊所代表的活動(dòng)所需時(shí)間之和。 完成整個(gè)工程所需的時(shí)間取決于從開(kāi)始點(diǎn)到結(jié)束點(diǎn)的最長(zhǎng)路徑長(zhǎng)

45、度，此長(zhǎng)度最大的路徑叫做關(guān)鍵路徑。 分析關(guān)鍵路徑的目的是辨別哪些是關(guān)鍵活動(dòng)，以便爭(zhēng)取提高關(guān)鍵活動(dòng)的效率，縮短整個(gè)工期。,.,81,在描述關(guān)鍵路徑的算法時(shí)，設(shè)活動(dòng)ai由弧表示，要確定如下幾個(gè)相關(guān)的量： (1) 事件Vj的最早出現(xiàn)時(shí)間和活動(dòng)的最早開(kāi)始時(shí)間：從源點(diǎn)V1到某頂點(diǎn)Vj的最長(zhǎng)路徑長(zhǎng)度叫作事件j的最早出現(xiàn)時(shí)間，表示成Vej。頂點(diǎn)Vj的最早出現(xiàn)時(shí)間Vej決定了從Vj指出的各條邊所代表活動(dòng)的最早開(kāi)始時(shí)間，因?yàn)槭录不出現(xiàn)，它后面的各項(xiàng)活動(dòng)就不能開(kāi)始。我們以ei表示活動(dòng)ai的最早開(kāi)始時(shí)間。顯然ei= Vej 。 (2) 活動(dòng)ai的最遲開(kāi)始時(shí)間：在不影響整個(gè)工程按時(shí)完成的前提下，此項(xiàng)活動(dòng)最遲的必須開(kāi)

46、始時(shí)間，表示成Li。 只要某活動(dòng)ai有Li=ei的關(guān)系，我們就稱(chēng)ai為關(guān)鍵活動(dòng)。關(guān)鍵活動(dòng)只允許在一個(gè)確定的時(shí)間開(kāi)始，再早，它前面的事件還沒(méi)出現(xiàn)，尚不能開(kāi)始；再晚，又會(huì)延誤整個(gè)工程的按時(shí)完成。由于完成整個(gè)工程所需的時(shí)間是由關(guān)鍵路徑上各邊權(quán)值之和所決定的，顯然關(guān)鍵路徑上各條邊所對(duì)應(yīng)的活動(dòng)都是關(guān)鍵活動(dòng)。,.,82,(3) 事件j的最遲出現(xiàn)時(shí)間：即事件j在不延誤整個(gè)工程的前提下允許發(fā)生的最遲時(shí)間，表示為VLj。對(duì)某條指向頂點(diǎn)Vj的邊所代表的活動(dòng)ai可得到： Li= VLj-(活動(dòng)ai所需時(shí)間) 也就是活動(dòng)ai必須先于它后面事件的最遲出現(xiàn)時(shí)間開(kāi)始，提前的時(shí)間為進(jìn)行此活動(dòng)所需的時(shí)間。 下圖所示為活動(dòng)開(kāi)始時(shí)

47、間與事件出現(xiàn)時(shí)間的關(guān)系。,確定關(guān)鍵路徑的方法就是要確定ei=Li的關(guān)鍵活動(dòng)！,.,83,假設(shè)以wj,k表示有向邊的權(quán)，即此邊對(duì)應(yīng)的活動(dòng)所需的時(shí)間，為了求AOE網(wǎng)絡(luò)中活動(dòng)ai的最早開(kāi)始時(shí)間ei和活動(dòng)ai的最遲開(kāi)始時(shí)間Li，先要求得頂點(diǎn)Vk的事件Vk的最早出現(xiàn)時(shí)間Vek和最遲出現(xiàn)時(shí)間VLk 。,.,84,事件最早出現(xiàn)時(shí)間Ve（j）和最遲出現(xiàn)時(shí)間Vl（j）,Vek和VLk可以采用下面的遞推公式計(jì)算： (1) 向匯點(diǎn)遞推 由源點(diǎn)的Vv1=0開(kāi)始，利用公式： 向匯點(diǎn)的方向遞推，可逐個(gè)求出各頂點(diǎn)的ev 。式中p表示所有指向頂點(diǎn)的邊的集合，如圖6.22所示。,.,85,圖7-6-6 集合p,此式的意義為：從

48、指向頂點(diǎn)Vk的各邊的活動(dòng)中取最晚完成的一個(gè)活動(dòng)的完成時(shí)間作為Vk的最早出現(xiàn)時(shí)間Vek。,.,86,(2) 向源點(diǎn)遞推 由上一步的遞推，最后總可求出匯點(diǎn)的最早出現(xiàn)時(shí)間evn。因匯點(diǎn)就是結(jié)束點(diǎn)，最遲出現(xiàn)時(shí)間與最早出現(xiàn)時(shí)間相同，即Lvn=evn。從匯點(diǎn)的最遲出現(xiàn)時(shí)間Lvn開(kāi)始，利用下面公式： 向源點(diǎn)的方向往回遞推，可逐個(gè)求出各頂點(diǎn)的最遲出現(xiàn)時(shí)間Lv。式中s表示所有由Vj點(diǎn)指出的邊的集合，如圖6.23所示。,.,87,圖5-6-7 集合s,此公式的意義為：由從Vj頂點(diǎn)指出的各邊所代表的活動(dòng)中取需最早開(kāi)始的一個(gè)開(kāi)始時(shí)間作為Vj的最遲出現(xiàn)時(shí)間。,.,88,無(wú)論是向匯點(diǎn)遞推還是向源點(diǎn)遞推，都必須按一定的頂點(diǎn)

49、順序進(jìn)行。 對(duì)所有的有向邊，向匯點(diǎn)遞推是先求出尾頂點(diǎn)的ev值，再求頭頂點(diǎn)的ev值；向源點(diǎn)遞推則相反，先求頭頂點(diǎn)的Lv值，再求尾頂點(diǎn)的Lv值。 為此，可利用上節(jié)介紹的拓?fù)渑判虻玫降捻旤c(diǎn)次序進(jìn)行向匯點(diǎn)的遞推，向源點(diǎn)的遞推按相反的順序進(jìn)行即可，不必再重新排序。,.,89,7.5.2 關(guān)鍵路徑算法,(1) 輸入e條有向邊，建立AOE網(wǎng)絡(luò)的存儲(chǔ)結(jié)構(gòu)； (2) 從源點(diǎn)出發(fā)，令ev1 =0，按拓?fù)渑判虻男蛄星笃溆喔黜旤c(diǎn)的最早出現(xiàn)時(shí)間evi(2in)。若拓?fù)渑判蛐蛄兄械捻旤c(diǎn)個(gè)數(shù)小于網(wǎng)絡(luò)中的頂點(diǎn)數(shù)n，則說(shuō)明網(wǎng)絡(luò)中存在環(huán)路，算法中止執(zhí)行；否則執(zhí)行(3)； (3) 從匯點(diǎn)Vn出發(fā)，令Lvn=evn，按逆拓?fù)渑判虻男?/p>

50、列求其余各頂點(diǎn)的最遲出現(xiàn)時(shí)間 Lvi(n-1i1)； (4) 根據(jù)各頂點(diǎn)的ev和Lv值求每條有向邊ai的最早開(kāi)始時(shí)間ei和最遲開(kāi)始時(shí)間Li。若某有向邊ai滿足ei=Li,則為關(guān)鍵活動(dòng),.,90,AOE網(wǎng)：帶權(quán)的有向圖，其中，頂點(diǎn)表示事件，弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)的時(shí)間。 關(guān)鍵路徑：AOE-網(wǎng)中有些活動(dòng)可以并行的進(jìn)行，所以完成工程的最短時(shí)間是從開(kāi)始點(diǎn)到完成點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度（這里所說(shuō)的長(zhǎng)度是指路徑上各個(gè)活動(dòng)持續(xù)時(shí)間之和，不是路徑上弧的數(shù)目）。路徑長(zhǎng)度最長(zhǎng)的路徑叫做關(guān)鍵路徑。 最早發(fā)生時(shí)間：假設(shè)開(kāi)始點(diǎn)是V1，從V1到Vi的最長(zhǎng)的路徑的長(zhǎng)度叫做事件Vi的最早發(fā)生時(shí)間。 最遲開(kāi)始時(shí)間：不推遲整個(gè)工程

51、完成的前提下，活動(dòng)ai最遲 必須開(kāi)始進(jìn)行的時(shí)間。 關(guān)鍵活動(dòng)：l（i）=e（i）的活動(dòng)。,回顧基本概念并練習(xí)：,.,91,v1,v3,v8,v9,v7,v2,v6,v4,v5,a3=5,a6=2,a9=4,a11=4,a10=2,a8=7,a4=1,a1=6,a2=4,a5=1,a7=9,如何求關(guān)鍵路徑？,如圖所示：,關(guān)鍵： 求出各個(gè)事件最早出現(xiàn)時(shí)間ve（j）和最遲發(fā)生時(shí) 間vl（j）。 再判斷各活動(dòng)e（i）是否等于l（i）！,.,92,1 求事件最早出現(xiàn)時(shí)間,v1,v3,v8,v9,v7,v2,v6,v4,v5,a3=5,a6=2,a9=4,a11=4,a10=2,a8=7,a4=1,a1=6

52、,a2=4,a5=1,a7=9,0,6,4,5,7,14,18,7,16,從ve（0）=0開(kāi)始向后推. Ve（j）=Maxve（i）+dut（i,j） (j=1，2.n-1),.,93,1 求事件最遲出現(xiàn)時(shí)間,v1,v3,v8,v9,v7,v2,v6,v4,v5,a3=5,a6=2,a9=4,a11=4,a10=2,a8=7,a4=1,a1=6,a2=4,a5=1,a7=9,0,6,6,8,10,14,18,7,16,從vl(9）=18開(kāi)始向回推（倒計(jì)時(shí)）。 Ve（i）=Minvl（j）- dut（i,j） (j=n-2,n-3,-,0),.,94,.,95,由表可知時(shí)間余量為零的活動(dòng)都是關(guān)鍵活動(dòng)，即為a1，a4，a7，a8，a10，a11。 這些關(guān)鍵活動(dòng)構(gòu)成兩條關(guān)鍵路徑，即