第5章 圖結(jié)構(gòu)

1、第5章 圖結(jié)構(gòu)第2頁2022年3月27日教學(xué)內(nèi)容： 圖的基本概念、圖的存儲方法、圖的遍歷、生成樹和最小生成樹、有向無環(huán)圖及其應(yīng)用、最短路徑教學(xué)目的： 理解圖的基本概念及術(shù)語；掌握圖的存儲方法；熟練掌握圖的兩種遍歷的算法思想、步驟；理解最小生成樹的概念，能按Prim算法構(gòu)造最小生成樹；領(lǐng)會并掌握拓撲排序、關(guān)鍵路徑、最短路徑的算法思想。教學(xué)重點： 圖的定義及其含義；圖的鄰接矩陣和鄰接表存儲方法；圖的按深度優(yōu)先搜索遍歷和按廣度優(yōu)先搜索遍歷方法；生成樹和最小生成樹的概念；Prim算法思想構(gòu)造最小生成樹按Prim算法思想；有向無環(huán)圖的應(yīng)用。教學(xué)難點： 正確理解與區(qū)別圖的常用術(shù)語；區(qū)別圖的兩種存儲結(jié)構(gòu)的不

2、同點及其應(yīng)用場合；關(guān)鍵路徑的算法思想；最短路徑的算法思想。第3頁2022年3月27日5.1 引言5.1.1 問題的提出問題1：尋求走迷宮問題的解，迷宮可表示成圖，求解即為尋求滿足某種要求的從迷宮的入口結(jié)點到迷宮的出口結(jié)點的路徑。問題2：從公園入口處尋找一條參觀某個動物的最短路徑。問題3：在幾個村落之間鋪設(shè)通訊線路，如何鋪設(shè)最省錢。問題4：計算機科學(xué)與技術(shù)專業(yè)的大學(xué)生，本科四年需要學(xué)習(xí)公共基礎(chǔ)課、專業(yè)基礎(chǔ)課、專業(yè)課幾十門，每門課程都可能有先修課程的要求，如何合理安排課程的教學(xué)順序，使學(xué)生能夠順利完成學(xué)業(yè)。第4頁2022年3月27日5.1.2 圖的定義和術(shù)語1圖的定義v2v1v 4v5v3第5頁2

3、022年3月27日2.圖的相關(guān)術(shù)語 無向圖 有向圖 例：右圖是一個有向圖G2。 表示為： G2=(V2,E2) V2=v1,v2,v3,v4 E2=, v4v3v2v1第6頁2022年3月27日 (3) 鄰接點、鄰接邊 (4) 完全圖 (5) 稠密圖、稀疏圖 (6) 頂點的度、入度、出度 (7) 邊的權(quán)、網(wǎng)圖 (8) 路徑和路徑長度 (9) 回路、簡單路徑、簡單回路 (10) 子圖 (11) 連通的、連通圖、連通分量 (12) 強連通圖、強連通分量 (13) 連通圖（或子圖）的生成樹 (14) 非連通圖的生成森林 第7頁2022年3月27日5.1.3 圖的基本操作(1) CreatGraph(

4、G)：建立圖G的存儲。(2) DestroyGraph(G)：釋放圖G占用的存儲空間。(3) GetVex(G, v)：在圖G中找到頂點v，并返回頂點v的相關(guān)信息。(4) PutVex(G, v, value)：在圖G中找到頂點v，并將value值賦給 頂點v。(5) InsertVex(G, v)：在圖G中增添新頂點v。(6) DeleteVex(G, v)：在圖G中，刪除頂點v以及所有和頂點v相關(guān)聯(lián)的邊或弧。(7) InsertArc(G, v, w)：在圖G中增添一條從頂點v到頂點w的邊或弧。第8頁2022年3月27日(8) DeleteArc(G, v, w)：在圖G中刪除一條從頂點v

5、到頂點w的邊或弧。(9) Traverse(G, v)：在圖G中，從頂點v出發(fā)遍歷圖G。(10) LocateVex(G, u)：在圖G中找到頂點u，返回該頂點在圖中存儲位置。(11) FirstAdjVex(G, v)：在圖G中，返回v的第一個鄰接點。若頂點在G中沒有鄰接點，則返回“空”。(13) NextAdjVex(G, v, w)：在圖G中，返回v的（相對于w的）下一個鄰接點。若w是v的最后一個鄰接點，則返回“空”。 第9頁2022年3月27日5.2.1 鄰接矩陣 1.鄰接矩陣的存儲思想 (1) 圖中頂點順序存儲； (2) 用一個n*n矩陣（設(shè)圖有n個頂點）來存儲任意兩個頂點之間邊的信

6、息，也就是各頂點之間的鄰接關(guān)系。 其中，wij表示邊(vi,vj)或上的權(quán)值；表示一個計算機允許的、大于所有邊上權(quán)值的數(shù)。1 若(vi,vj)或是E(G)中的邊0 若(vi,vj)或不是E(G)中的邊Aij=wij 若(vi,vj)或是E(G)中的邊0或 若(vi,vj)或不是E(G)中的邊Aij=若G是帶權(quán)圖，則鄰接矩陣可定義為：5.2 圖的存儲方法 第10頁2022年3月27日 用鄰接矩陣表示法表示的無向圖和網(wǎng)圖如下圖所示。第11頁2022年3月27日2.鄰接矩陣的表示 #define MaxVertexNum /定義能存儲的足夠大的頂點個數(shù) typedef char VertexType

7、; / VertexType為頂點類型，設(shè)為字符型 typedef int EdgeType; / EdgeType為邊的權(quán)值類型，設(shè)為整型 typedef struct VertexType vexsMaxVertexNum; /頂點表 EdgeType dgesMaxVertexNumMaxVertexNum;/鄰接矩陣 int n, e; /實際的頂點數(shù)和邊數(shù) MMGragh; 第12頁2022年3月27日3、鄰接矩陣存儲方法的特點 無向圖的鄰接矩陣一定是一個對稱矩陣。 對于無向圖，鄰接矩陣的第i行（或第i列）非零元素（或非元素）的個數(shù)正好是第i個頂點的度TD(vi)。 對于有向圖，鄰接

8、矩陣的第i行（或第i列）非零元素（或非元素）的個數(shù)正好是第i個頂點的出度OD(vi)（或入度ID(vi)）。 用鄰接矩陣方法存儲圖，很容易確定圖中任意兩個頂點之間是否有邊相連；但是，要確定圖中有多少條邊，則必須按行、按列對每個元素進行檢測，所花費的時間代價很大。這是用鄰接矩陣存儲圖的局限性。第13頁2022年3月27日5、建立一個有向圖鄰接矩陣存儲的算法【算法5-1】建立一個有向圖的鄰接矩陣存儲void CreateMGraph(MGraph *G) /建立有向圖G的鄰接矩陣存儲，N,E是圖的頂點個數(shù)和邊的個數(shù) int i,j,k,w; char ch; /設(shè)圖的頂點信息為字符型 for (i

9、=0;ivexsi); /輸入頂點信息，建立頂點表 for (i=0;iN;i+) for (j=0;jedgesij=0; /初始化鄰接矩陣 for (k=0;kedgesij=1; /若為無向圖，還要建立(i,j)邊，即：G-edgesij=1; 第14頁2022年3月27日5.2.2 鄰接表 鄰接表(Adjacency List)是圖的一種順序存儲與鏈式存儲結(jié)合的存儲方法。1、鄰接表的存儲思想第15頁2022年3月27日 下圖給出無向圖及對應(yīng)的鄰接表表示。第16頁2022年3月27日2、鄰接表的兩種結(jié)點結(jié)構(gòu)第17頁2022年3月27日3、鄰接表的定義 typedef struct nod

10、e int adjvex; /鄰接點域 struct node *next; /指向下一個鄰接點（或邊）的指針域 /若要表示邊上信息，則應(yīng)增加相關(guān)數(shù)據(jù)域info EdgeNode; /邊結(jié)點 typedef struct vnode VertexType vertex; /頂點域 EdgeNode *firstedge; /第一條邊的指針 VertexNode; /頂點結(jié)點 VertexNode AdjListN; /頂點結(jié)點向量第18頁2022年3月27日【算法5-2】建立一個有向圖的鄰接表存儲 void CreateALGraph(VertexNode AdjList ) /建立有向圖的鄰

11、接表存儲，N,E是圖的頂點個數(shù)和邊的個數(shù) int i, j, k; EdgeNode * s; for (i=0; iN; i+) /建立有n個頂點的頂點表 scanf(%c,&( AdjListi.vertex);/讀入頂點信息 AdjListi.firstedge=NULL; /頂點的邊表頭指針設(shè)為空 for (k=0; kE; k+) /建立邊表 scanf(%d,%d,&i,&j); /讀入邊的頂點序號對偶 s=(EdgeNode*)malloc(sizeof(EdgeNode); /生成新邊表結(jié)點s s-adjvex=j; /鄰接點序號為j s-next= AdjListi.firs

12、tedge; /將新邊表結(jié)點s插入到頂點vi的邊表頭部 AdjListi.firstedge=s; 第19頁2022年3月27日有向圖的逆鄰接表 若鄰接表的邊結(jié)點鏈表建立的是以vi為頭的弧鏈表，這樣的鄰接表稱為逆鄰接表。逆鄰接表便于確定頂點的入度或以頂點vi為頭的弧。 下圖所示為有向圖G2的鄰接表和逆鄰接表。第20頁2022年3月27日 圖的遍歷是指從圖中的任一頂點出發(fā)，對圖中的所有頂點訪問一次且只訪問一次。圖的遍歷是圖的一種基本操作，圖的許多其它操作都是建立在遍歷操作的基礎(chǔ)之上。 5.3 圖的遍歷第21頁2022年3月27日5.3.1 深度優(yōu)先搜索 深度優(yōu)先搜索（Depth_Fisrst S

13、earch）遍歷類似于樹的先根遍歷，是樹的先根遍歷的推廣。1、深度優(yōu)先搜索的概念 第22頁2022年3月27日以下圖的無向圖G5為例，進行圖的深度優(yōu)先搜索。得到的頂點訪問序列為： v1 v2 v4v8 v5 v3v6v7第23頁2022年3月27日2、圖的深度優(yōu)先遍歷算法【算法5-4】圖的深度優(yōu)先遍歷int flagN=0；/N為圖的頂點個數(shù)void DFSTraverse (Graph *G, int v ) /從頂點v出發(fā)深度優(yōu)先遍歷圖G Visited(v); flagv=1; /訪問頂點v，并置訪問標記 for(w=FisrAdjVex(G,v); w; w=NextAdjVex(G,

14、v,w) if (!flagw) DFSTraverse (G,w); /對頂點v的尚未訪問的鄰接頂點w遞歸調(diào)用DFSTraverse 上面算法只是一個形式化的算法，算法5-5給出了對用鄰接表存儲的圖進行深度優(yōu)先遍歷的過程。 【算法5-5】深度優(yōu)先遍歷鄰接表存儲的圖int flagN=0; /全局數(shù)組初始化為0void DFS(VertexNode AdjList , int i) /以頂點i為出發(fā)點，對鄰接表存儲的圖G進行DFS搜索 EdgeNode *p; Visited(AdjListi.vertex); /訪問頂點vi flagi=1; /標記頂點i已訪問 p=AdjListi.fir

15、stedge; /取頂點i鄰接邊鏈表的頭指針 while(p) j=p-adjvex; /依次搜索頂點i的鄰接點頂點j if (!flagj) 第24頁2022年3月27日5.3.2 廣度優(yōu)先搜索 廣度優(yōu)先搜索（Breadth_First Search） 遍歷類似于樹的按層次遍歷的過程。1、廣度優(yōu)先搜索的概念 第25頁2022年3月27日 例如，得到的頂點訪問序列為： v1v2 v3 v4 v5 v6 v7 v8第26頁2022年3月27日2、圖的廣度優(yōu)先遍歷算法【算法5-6】圖的廣度優(yōu)先遍歷int flagN=0; /全局數(shù)組初始化為0 void BFSTraverse(Graph *G,

16、int v) /對G進行廣度優(yōu)先遍歷 InitQueue(Q); /置空的隊列Q if (!flagv) /v尚未訪問 EnQueue(Q, v); /v入隊 while (!QueueEmpty(Q) /隊列不空 DeQueue(Q, u); /隊頭元素出隊 Visited (u); /訪問該頂點 flagu=1; /置訪問標志 for(w=FirstAdjVex(G,u); w; w=NextAdjVex(G,u,w) if (!flagw) /依次將尚未訪問的鄰接頂點 EnQueue(Q,w); 第27頁2022年3月27日 1 . 無向圖的連通性 在對無向圖進行遍歷時，對于連通圖，僅需

17、從圖中任一頂點出發(fā)，進行深度優(yōu)先搜索或廣度優(yōu)先搜索，便可訪問到圖中所有頂點。對非連通圖，則需從多個頂點出發(fā)進行搜索，而每一次從一個新的起始點出發(fā)進行搜索過程中得到的頂點訪問序列恰為其各個連通分量中的頂點集。5.3.3遍歷圖的簡單應(yīng)用第28頁2022年3月27日 第29頁2022年3月27日2. 有向圖的連通性 有向圖的連通性不同于無向圖的連通性，可分為弱連通、單側(cè)連通和強連通。對有向圖的強連通性以及強連通分量的判定，可通過對以十字鏈表為存儲結(jié)構(gòu)的有向圖的深度優(yōu)先搜索實現(xiàn)。 第30頁2022年3月27日5.4 生成樹和生成森林5.4.1 生成樹和生成森林 1.生成樹和生成森林的概念 第31頁20

18、22年3月27日 下圖是連通圖G5和其深度優(yōu)先生成樹和廣度優(yōu)先生成樹。圖中虛線為集合B(G) 中的邊，實線為集合T(G)中的邊。第32頁2022年3月27日 對于非連通圖，通過這樣的遍歷，將得到的是生成森林。例如，下圖所示為一個無向圖及其深度優(yōu)先生成森林，它由三棵深度優(yōu)先生成樹組成。第33頁2022年3月27日2. 生成森林的構(gòu)建算法 【算法5-8】建立無向圖的深度優(yōu)先生成森林的孩子兄弟鏈表int flagN=0; /全局訪問標志數(shù)組，初始化為0void DFSForest(Graph *G, CSTree *T) /建立無向圖G的深度優(yōu)先生成森林T，森林用孩子兄弟鏈表存儲,N是圖頂點個數(shù) C

19、SNode *p,*q; / CSNode是孩子兄弟存儲方法的結(jié)點類型 *T=NULL; for(v=0;vnextsibling=p; /前一棵的根的兄弟是其它生成樹的根 q=p; /q指示當(dāng)前生成樹的根 DFSTree(G,v,&p); /建立以p為根的生成樹 void DFSTree(Graph *G, int v, CSTree *T) /從第v個頂點出發(fā)深度優(yōu)先遍歷圖G，建立以*T為根的生成樹 / Graph是圖G的形式存儲類型，CSTree是指向CSNode的指針類型第34頁2022年3月27日5.4.2 最小生成樹 1、 最小生成樹的概念第35頁2022年3月27日2、如何找到一

20、個連通網(wǎng)絡(luò)的最小生成樹？ (1) MST性質(zhì)： 第36頁2022年3月27日5.4.3 構(gòu)造最小生成樹的Prim算法1、Prim算法 設(shè)G(Vn, En)為一網(wǎng)圖，其中Vn為網(wǎng)圖中所有頂點的集合，En為網(wǎng)圖中所有帶權(quán)邊的集合。 第37頁2022年3月27日 Prim算法可用下述過程描述，其中用wuv表示頂點u與頂點v邊上的權(quán)值。 Uu1,T=; while (UV)do (u,v)minwuv|uU,vVU TT(u,v) UUv 結(jié)束。第38頁2022年3月27日 2、 Prim過程 第39頁2022年3月27日【算法5-9】用Prim算法構(gòu)造無向連通網(wǎng)的最小生成樹#define MAXCO

21、ST /定義MAXCOST為一個足夠大的常量值void Prim(int gmNN, int treeN, int costN) /從序號為0的頂點出發(fā)，建立連通網(wǎng)的最小生成樹，二維數(shù)組gmNN是其鄰接矩陣/頂點編號依次為0.N-1，建立的最小生成樹存于數(shù)組tree中，對應(yīng)的邊值在cost中 int flagN=0; int i, j, k, mincost;for (i=0;iN;i+) costi=gm0i; /從存儲序號為0的頂點出發(fā)生成最小生成樹 treei=0; flag0=1;for (i=1;iN;i+) / N -1次循環(huán)，尋找當(dāng)前最小權(quán)值的邊 mincost=MAXCOST;

22、 for(j=1;jN;j+) if (flagj=0&costjmincost ) mincost=costj; k=j; /記憶最小的邊 flagk=0; /k進入了U集合 for (j=1;jN;j+) /是否用新點k連通不在U的頂點 if (gmkjcostj)第40頁2022年3月27日5.4.4 構(gòu)造最小生成樹的Kruskal算法 Kruskal算法是一種按照網(wǎng)中邊的權(quán)值遞增的順序構(gòu)造最小生成樹的方法。1、 Kruskal算法基本思想 第41頁2022年3月27日 2、Kruskal方法過程 第42頁2022年3月27日3、算法實現(xiàn)【算法5-10】Kruskal方法構(gòu)造無向網(wǎng)的最小

23、生成樹void Kruskal(EdgeType edges ,EdgeType T )/用Kruskal方法構(gòu)造圖的最小生成樹 /edge中是圖中各條邊，且已按其權(quán)值從小到大有序 /最小生成樹的邊在T中 int fatherN; int i,j,vf1,vf2; for (i=0;iN;i+) fatheri=-1; i=0;j=0; while(iE & jN-1) vf1=Find(father,edgesi.v1); vf2=Find(father,edgesi.v2); if (vf1!=vf2) fathervf2=vf1; Tj=edgesi; j+; i+; int Find(

24、int father , int v) /尋找頂點v所在樹的根結(jié)點 int t;第43頁2022年3月27日 5.5 最短路徑 最短路徑問題：如果從圖中某一頂點(稱為源點)到達另一頂點(稱為終點)的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達到最小。 第44頁2022年3月27日5.5.1 從一個源點到其它各點的最短路徑1.單源點的最短路徑問題2.迪杰斯特拉（Dijkstra）算法 第45頁2022年3月27日第46頁2022年3月27日3.Dijkstra算法的實現(xiàn)【算法5-11】求單源點到圖上其余各頂點的最短路徑-Dijkstra算法 void ShortestPat

25、h(MGraph *G, int PN, float DN) /設(shè)源點為頂點0，求到其余頂點的最短路徑 /Dv存放從源點頂點0到終點v最短路徑其長度 /Pv存放相應(yīng)的最短路徑終點的前驅(qū)點 /常量INFINITY是為鄰接矩陣中的 int finalN=1,0; for (i=0;iedges0i; Pi=0; D0=0; final0=1; P0=-1; /初始化，源點屬于S集 for(i=1; iN; i+) /開始主循環(huán)，每次求得源點到某個頂點k的最短路徑，并加k到S集 min=INFINITY+1; /為了將沒有路徑的點最后選中，初始化+1 for (k=0; kN; j+) /從未進入S

26、的點中找最小的Dk if (finalk=0& Dkmin) /頂點k沒進入S中且當(dāng)前的路徑更短 j=k; /具有更小路徑的點存儲在j中 min=Dk; finalj=1; /將j加入S集合第47頁2022年3月27日5.5.2 每一對頂點之間的最短路徑 -弗洛伊德算法 解決這個問題的一個辦法是：每次以一個頂點為源點，重復(fù)調(diào)用Dijkstra算法n次。這樣，便可求得每一對頂點之間的最短路徑，總的時間復(fù)雜度為O(n3)。 弗洛伊德（Floyd）提出了另一個算法。Floyd算法求解每一對頂點對間的最短路徑問題仍從圖的帶權(quán)鄰接矩陣出發(fā)，依據(jù)的是以下遞推關(guān)系： D(-1)ij=edgesij D(k)

27、ij=MinD(k-1)ij, D(k-1) ik+ D(k-1) kj 0kn-1第48頁2022年3月27日5.6.1 有向無環(huán)圖的概念5.6 有向無環(huán)圖及其應(yīng)用 第49頁2022年3月27日(1) 有向無環(huán)圖是描述含有公共子式的表達式的有效工具： 例如下述表達式： (a+b)*(b*(c+d)+(c+d)*e)*(c+d)*e) 可以用第六章討論的二叉樹來表示，如下圖所示。第50頁2022年3月27日 仔細觀察該表達式，可發(fā)現(xiàn)有一些相同的子表達式，如(c+d)和(c+d)*e等，在二叉樹中，它們也重復(fù)出現(xiàn)。若利用有向無環(huán)圖，則可實現(xiàn)對相同子式的共享，從而節(jié)省存儲空間。例如下圖所示為表示同

28、一表達式的有向無環(huán)圖。第51頁2022年3月27日5.6.2 AOV網(wǎng)與拓撲排序1AOV網(wǎng) (頂點表示活動的網(wǎng))(1) AOV概念：頂點表示活動，弧表示活動之間存在的制約關(guān)系網(wǎng)稱為AOV。(2) 用AOV表示一個工程： 第52頁2022年3月27日 例如：計算機專業(yè)的學(xué)生必須完成一系列規(guī)定的基礎(chǔ)課和專業(yè)課才能畢業(yè)。第53頁2022年3月27日2拓撲排序概念 (1)偏序集合概念 若集合A中的二元關(guān)系R是自反的、非對稱的和傳遞的，則R是A上的偏序關(guān)系。集合A與關(guān)系R一起稱為一個偏序集合。 (2) 全序集合概念 若R是集合A上的一個偏序關(guān)系，如果對每個a、bA必有aRb或bRa ，則R是A上的全序關(guān)

29、系。集合A與關(guān)系R一起稱為一個全序集合。 第54頁2022年3月27日 （3）拓撲排序 滿足這樣性質(zhì)的線性序列稱為拓撲有序序列: 在AOV網(wǎng)中，若頂點i 優(yōu)先于頂點j ，則在線性序列中頂點i仍然優(yōu)先于頂點j； 對于網(wǎng)中原來沒有優(yōu)先關(guān)系的頂點與頂點，在線性序列中也建立一個先后關(guān)系，或者頂點i優(yōu)先于頂點j ，或者頂點j 優(yōu)先于i。 第55頁2022年3月27日3拓撲排序算法 對AOV網(wǎng)進行拓撲排序的方法和步驟是： 從AOV網(wǎng)中選擇一個沒有前驅(qū)的頂點（該頂點的入度為0）并且輸出它； 從網(wǎng)中刪去該頂點，并且刪去從該頂點發(fā)出的全部有向邊； 重復(fù)上述兩步，直到剩余的網(wǎng)中不再存在沒有前驅(qū)的頂點為止。 這樣操

30、作的結(jié)果有兩種：一是網(wǎng)中全部頂點都被輸出，這說明網(wǎng)中不存在有向回路；一是網(wǎng)中頂點未全部輸出，剩余的頂點均不前驅(qū)頂點，這說明網(wǎng)中存在有向回路。第56頁2022年3月27日下圖給出在一個AOV網(wǎng)上實施上述步驟的例子。第57頁2022年3月27日 算法實現(xiàn)【算法5-12】有向網(wǎng)的拓撲排序int Top_Sort (VertexNode AdjListN,int Tsort ) /圖G用鄰接表存儲，頂點結(jié)點帶入度域，求其拓撲序列；其拓撲序列存入Tsort 向量 Queue Q; /Q為一隊列int m=0; /c為計數(shù)器，記錄已輸出的頂點數(shù)目Init_Queue(Q); /初始化隊列Q for (i=

31、0;iadjvex; AdjListk.indegree-; /當(dāng)前輸出頂點鄰接點的入度減1 if(AdjListk.indegree=0) /新的入度為0的頂點入隊 In_Queue(Q,k); p=p-next; /找到下一個鄰接點第58頁2022年3月27日5.6.3 AOE圖與關(guān)鍵路徑1AOE網(wǎng)（邊表示活動的網(wǎng)） (1) AOE網(wǎng)概念：若在帶權(quán)的有向圖中，以頂點表示事件，以有向邊表示活動，邊上的權(quán)值表示活動的開銷（如該活動持續(xù)的時間），則此帶權(quán)的有向圖稱為AOE網(wǎng)。 (2)AOE網(wǎng)表示一項工程能表示出： 完成預(yù)定工程計劃所需要進行的活動; 每個活動計劃完成的時間; 要發(fā)生哪些事件以及這

32、些事件與活動之間的關(guān)系;第59頁2022年3月27日(3) 通過AOE網(wǎng)可以求得： 估算工程完成的時間 確定哪些活動是影響工程進度的關(guān)鍵。 (4) AOE網(wǎng)的兩個特點： 只有在某頂點所代表的事件發(fā)生后，從該頂點出發(fā)的各有向邊所代表的活動才能開始。 只有在進入一某頂點的各有向邊所代表的活動都已經(jīng)結(jié)束，該頂點所代表的事件才能發(fā)生。第60頁2022年3月27日 下圖給出了一個具有15個活動、11個事件的假想工程的AOE網(wǎng)。第61頁2022年3月27日2關(guān)鍵路徑具有最大路徑長度的路徑稱為關(guān)鍵路徑。關(guān)鍵路徑上的活動稱為關(guān)鍵活動。第62頁2022年3月27日 3.關(guān)鍵路徑的確定 為了在AOE網(wǎng)中找出關(guān)鍵路

33、徑，需要定義幾個參量：事件的最早發(fā)生時間vek 事件的最遲發(fā)生時間vlk： 活動ai的最早開始時間ei 活動ai的最晚開始時間li第63頁2022年3月27日 4.那些是關(guān)鍵活動？ 根據(jù)每個活動的最早開始時間ei和最晚開始時間li就可判定該活動是否為關(guān)鍵活動，也就是那些li=ei的活動就是關(guān)鍵活動，而那些liei的活動則不是關(guān)鍵活動，li-ei的值為活動的時間余量。關(guān)鍵活動確定之后，關(guān)鍵活動所在的路徑就是關(guān)鍵路徑。第64頁2022年3月27日5、求關(guān)鍵路徑的過程 (1) 按照式5-1求事件的最早發(fā)生時間vek ve 1=0 ve 2=3 ve 3=4 ve 4=ve2+2=5 ve 5=maxve2+1,ve3+3=7 ve 6=ve3+5=9 ve 7=maxve4+6,ve5+8=15 ve 8=ve5+4=11 ve 9=maxve8+10,ve6+2=21 ve 10=maxve8+4,ve9+1=22 ve 11=maxve7+7,ve10+6=28第65頁2022年3月27日(2) 按照式5-2求事件的最遲發(fā)生時間vlk。 vl 11= ve 11=28 vl 10= vl 11-6=22 vl 9= vl