《數(shù)據(jù)結(jié)構(gòu)與算法》第七章圖.ppt

1、第七章 圖,7.1 圖的定義 7.2 圖的存儲結(jié)構(gòu) 7.3 圖的遍歷 7.4 圖的連通性問題 7.5 有向無環(huán)圖及其應(yīng)用 7.6 最短路徑,71圖的定義,一、有向圖和無向圖 頂點Vertex V:頂點的有窮非空集合 VR兩個頂點之間的關(guān)系的集合 若VR 則表示從v到w有一條弧Arc v稱作弧尾或初始點，Tail w稱作弧頭或終端點, Head,有向圖,無向圖,稀疏圖 稠密圖 網(wǎng)Network,子圖,鄰接點 相關(guān)聯(lián) 頂點的度、入度、 出度,圖中邊/弧的數(shù)目與頂點度的關(guān)系,路徑,路徑的長度,連通圖,回路或環(huán)Cycle 簡單路徑 簡單回路,強連通圖,完全圖,有向完全圖,由頂點的集合和弧的集合構(gòu)成的圖

2、稱為有向圖,G1=(V1,A1) V1=v1,v2,v3,v4 A1=,若VR必有VR 則用無序?qū)?v,w)代替和稱作邊Edge 由頂點的集合和邊的集合構(gòu)成的圖稱作無向圖,G2=(V2,E2) V2=v1,v2,v3,v4,v5 E2=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5),二、完全圖 Completed Graph 完全圖 有n*（n-1）/2條邊的無向圖 有向完全圖 有n*（n-1）條弧的有向圖 稀疏圖 有很少條邊或弧的圖 稠密圖 網(wǎng)Network 帶權(quán)的圖,三、子圖Subgraph 若有兩個圖G =（V，E）,G1=（V1，E1）

3、如果V1 V , E1 E,則稱G1為G的子圖,子圖,四、度 1.無向圖G =（V，E） 若邊（v，v1）E，則稱頂點v和v1互為鄰接點 邊（v，v1）依附于頂點v和v1 或邊（v，v1）與頂點v、v1相關(guān)聯(lián) 頂點v的度是和v相關(guān)聯(lián)的邊的數(shù)目,記作TD（v） 2.有向圖G =（V，A） 弧v，v1A， 則稱v鄰接到v1 或v1鄰接自v 弧v，v1和頂點v、v1相關(guān)聯(lián) 以頂點v為頭的弧的條數(shù)稱作v的入度,記作ID（v） 以頂點v為尾的弧的條數(shù)稱作v的出度,記作OD（v） 頂點v的度TD（v）=ID（v）+OD（v）,圖中邊/弧的數(shù)目與頂點度的關(guān)系,(若圖中有n個頂點，e條邊/弧),五、路徑 1.

4、無向圖G=（V，E）中 從頂點v到v1的路徑是一個頂點序列: v=Vi,0, Vi,1,Vi,m =v1 其中（Vi,j-1，Vi,j）E， 1jm,3.路徑的長度是路徑上邊或弧的數(shù)目,2.有向圖G=（V，A） 從頂點v到v1的路徑是一個有向頂點序列: v=Vi,0, Vi,1,Vi,m=v1 其中Vi,j-1，Vi,jA， 1jm,4.第一個頂點與最后一個頂點相同的路徑稱為回路或環(huán)Cycle 5.序列中頂點不重復(fù)出現(xiàn)的路徑稱為簡單路徑 除第一個和最后一個頂點外，其余頂點不重復(fù)出現(xiàn)的回路稱為簡單回路,六、連通圖 Connected Graph 1.無向圖 v到v1有路徑，稱v和v1是連通的 若

5、圖中任意兩個頂點vi、vjV都是連通的 則稱G是連通圖,2.若一個無向圖中有n個頂點和少于n-1條邊 則該圖是非連通圖 若它有多于n-1條邊，則一定有環(huán),3.有向圖 對于每一對vi、vjV,從vi到vj和vj到vi 都存在路徑,則稱 G為強連通圖,七、圖的ADT ADT Graph 數(shù)據(jù)對象V:V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點。 數(shù)據(jù)關(guān)系R： R=VR VR=|v,wV且p(v,w), 表示從v到w的弧， 謂詞P(v,w)定義了弧的意義或信息 基本操作P： CreateGraph( 初始條件:圖G存在. 操作結(jié)果:銷毀圖G。,LocateVex(G,u); 初始條件：圖G存在，u和G

6、中頂點有相同特征。 操作結(jié)果: 若G中存在頂點u，則返回該點在圖中的位置,否則返回其它信息。,GetVex(G,v); 初始條件：圖G存在，v是G中某個頂點。 操作結(jié)果: 返回v的值,PutVex( 初始條件：圖G存在，v是G中某個頂點。 操作結(jié)果: 對v賦值 value。,FirstAdjVex(G,v); 初始條件：圖G存在，v是G中某個頂點。 操作結(jié)果:返回v的第一個鄰接頂點。 若頂點在G中沒有鄰接頂點，則返回“空”。,NextAdjVex(G,v,w); 初始條件：圖G存在，v是G中某個頂點，w是v的鄰接頂點。 操作結(jié)果: 返回v的（相對于w的）下一個鄰接頂點。 若w是v 的最后一個鄰

7、接點則返回“空”。,InsertVex( 初始條件：圖G存在，v和圖中頂點有相同特征。 操作結(jié)果: 在圖G中增添新頂點v。,DeleteVex( 初始條件：圖G存在，v是G中某個頂點 操作結(jié)果：刪除G中頂點v及其相關(guān)的弧。,InsertArc( 初始條件：圖G存在，v和w是G中兩個頂點。 操作結(jié)果：在G中刪除弧。若G是無向的，則還刪除對稱弧,DFSTraverse(G,v,Visit(); 初始條件：圖G存在，v是G某個頂點，Visit是頂點的應(yīng)用函數(shù)。 操作結(jié)果:從頂點v起深度優(yōu)先遍歷圖G，并對每個頂點調(diào)用visit一次且 僅一次。一旦visit()失敗，則操作失敗。 BFSTraverse

8、(G,v,Visit(); 初始條件：圖G存在，v是G某個頂點，visit是頂點的應(yīng)用函數(shù)。 操作結(jié)果: 從頂點v起廣度優(yōu)先遍歷圖G， 并對每個頂點調(diào)用visit 一次且僅一次。 一旦visit()失敗，則操作失敗。 ADT Graph,7.2 圖的存儲結(jié)構(gòu),在圖中，無法用數(shù)據(jù)元素在存儲區(qū)的物理位置表示元素之間的關(guān)系。,一、數(shù)組表示法(鄰接矩陣表示法) 用一個數(shù)組存儲頂點的信息， 用另一個數(shù)組存儲邊或弧的信息-鄰接矩陣,15,10,5,30,12,20,3,2,1,0,4,1.圖的數(shù)組存儲表示 / _ _ _ _ _ _圖的數(shù)組（鄰接矩陣）存儲表示 _ _ _ _ _ _ _ #define

9、INFINITY INT_MAX / 最大值 #define MAX_VERTEX_NUM 20 /最大頂點個數(shù) typedef enum DG,DN,UDG,UDNGraphKind; /有向圖，有向網(wǎng)，無向圖，無向網(wǎng) typedef struct ArcCell VRType adj; /VRType是頂點關(guān)系類型.對無權(quán)圖,用1或0 /表示相鄰否；對帶權(quán)圖，則為權(quán)值類型。 InfoType *Info; /該弧相關(guān)信息的指針 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;,typedef struct VertexType vexsMAX_

10、VERTEX_NUM; / 頂點向量 AdjMatrix arcs; / 鄰接矩陣 int vexnum, arcnum; / 圖的當(dāng)前頂點數(shù)和弧數(shù) GraphKind kind; / 圖的種類標志 MGraph;,Mgraph G1; G1.vexnum=4 G1. arcnum=4 G1.kind=DG,G1.arcs01.adj=1,G1.arcs,2圖的構(gòu)造方法 Status CreateGraph( MGraph / CreateGraph,Status CreateUDN(MGraph /adj,info,for (k=0; k的權(quán)值 if (IncInfo) Input(* G.

11、); / 若弧含有相關(guān)信息,則輸入 G.arcsji =G.arcsij; / 置的對稱弧 return OK; / CreateUDN,二、鄰接表Adjacency List 方法：對每個頂點建立一個單向鏈表 鏈接與vi有邊相連的頂點（無向圖） 或從vi出發(fā)到達的頂點（有向圖）,指向該點出發(fā)到達的第一條弧,每個頂點對應(yīng)一個頭結(jié)點,每條邊/弧對應(yīng)一個結(jié)點,無向圖,邊結(jié)點,有向圖,/- - - - - - - 圖的鄰接表存儲表示 - - - - - - - #define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex

12、; / 該弧所指向的頂點的位置 struct ArcNode * nextarc; / 指向下一條弧的指針 InfoType * info; / 該弧相關(guān)信息的指針 ArcNode ;,typedef struct VNode VertexType data; / 頂點信息 ArcNode * firstarc; / 指向第一條依附頂點的弧的指針 VNode, AdjListMAX_VERTEX_NUM ;,typedef struct AdjList vertices; int vexnum, arcnum; / 圖的當(dāng)前頂點數(shù)和弧數(shù) int kind; / 圖的種類標志 ALGraph;,

13、# define MAX_VERTEX_NUM 20 typedef struct ArcBox int tailvex, headvex ; / 該弧的尾和頭頂點的位置 struct ArcBox *hlink, *tlink; /分別為弧頭相同和弧尾相同的弧的鏈域 Info type *info; / 該弧相關(guān)信息的指針 ArcBox;,typedef struct VexNode VertexType data; ArcBox * firstin, * firstout; /分別指向該頂點第一條入弧和出弧 VexNode ; typedef struct VexNode xlist MA

14、X_VERTEX_NUM ; / 表頭向量 int vexnum, arcnum; / 有向圖的當(dāng)前頂點數(shù)和弧數(shù) OLGraph ;,Status CreateDG(OLGraph / 初始化指針 ,for(k=0; kinfo); /若弧含有相關(guān)信息，則輸入 / CreateDG,四、鄰接多重表 Adjancency Multilist 頂點和邊分別用一個結(jié)點表示 邊：,該邊是否搜索過,頂點i在圖中的位置(編號),下一條與i有關(guān)的邊,有關(guān)邊的信息,# define MAX_VERTEX_NUM 20 typedef enum unvisited, visitedVisitIf ; typed

15、ef struct EBox VisitIf mark; / 訪問標記 int ivex, jvex; / 該邊依附的兩個頂點的位置0 struct EBox * ilink, * jlink; /分別指向依附這兩個頂點的下一條邊 InfoType * info; / 該邊信息指針 EBox; typedef struct VexBox VertexType data; EBox * firstedge ; / 指向第一條依附該頂點的邊 VexBox;,typedef struct VexBox adjmulist MAX_VERTEX_NUM ; int vexnum, edgenum; /

16、 無向圖的當(dāng)前頂點數(shù)和邊數(shù) AMLGraph ;,73圖的遍歷Traversing Graph,圖的遍歷： 從圖中某個頂點出發(fā)訪問遍圖中每個頂點， 且圖中每個頂點僅被訪問一次。 遍歷過程中每個頂點可能被訪問多次， 因此，每個頂點被訪問后需作一個標記 一般用一個數(shù)組標記某個結(jié)點是否被訪問 遍歷方法：深度優(yōu)先搜索、廣度優(yōu)先搜索,一、深度優(yōu)先收索Depth-First-Search(DFS) 方法： 從圖中某個頂點出發(fā)（設(shè)為v1），訪問v1， 從v1出發(fā),選擇一個未被訪問的鄰接點vk,訪問vk， 從vk出發(fā)，選擇一個未被訪問的鄰接點, 若vk的所有鄰接頂點都被訪問過了， 回到vk-1,再選擇的一個未

17、被訪問的鄰接點, 若圖中仍有未被訪問的頂點， 從中選擇一個作為起點，重復(fù)上述過程 直到所有頂點均被訪問過為止。,從v1出發(fā),選擇一個未被訪問的鄰接點vk,訪問vk， 從vk出發(fā)，選擇一個未被訪問的鄰接點, 若vk的所有鄰接頂點都被訪問過了， 回到vk-1,再選擇的一個未被訪問的鄰接點, 若圖中仍有未被訪問的頂點， 從中選擇一個作為起點，重復(fù)上述過程 直到所有頂點均被訪問過為止。,Boolean visitedMAX; / 訪問標志數(shù)組 Status (* VisitFunc)(int v); / 函數(shù)指針變量 void DFSTraverse(Graph G, Status(* Visit)(

18、int v) / 對圖G作深度優(yōu)先遍歷 VisitFunc = Visit; /使用全局變量VisitFunc，使DFS不必設(shè)函數(shù)指針參數(shù) for(v=0; vG.vexnum; +v) visitedv = FALSE ; / 訪問標志數(shù)組初始化 for(v=0; vG.vexnum; +v ) if(!visitedv) DFS (G,v ); /對尚未訪問的頂點調(diào)用DFS ,/從第v個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖G void DFS(Graph G, int v) visitedv=TRUE; VistFunc(v); /訪問第v個頂點 for(w=FirstAdjVex(G,v);w0

19、; w=NextAdjVex(G,v,w) if(!visitedw) DFS(G,w); /對v的尚未訪問的鄰接頂點w遞歸調(diào)用DFS printf(v); /起什么作用 ,1,2,3,4,5,6,7,8,9,搜索,回退,二、廣度優(yōu)先收索Breadth-First-Search(BFS) 方法： 從圖中某個頂點出發(fā)（設(shè)為vi），訪問vi， 從vi出發(fā)，依次訪問vi的所有未被訪問的鄰接點， 再從這些鄰接點出發(fā)， 依次訪問它們的所有未被訪問的鄰接點, 若圖中仍有未被訪問的頂點， 從中選擇一個作為起點，重復(fù)上述過程 直到所有頂點均被訪問過為止。,void BFSTraverse(Graph G,St

20、atus(* Visit)(int v) / 按廣度優(yōu)先非遞歸遍歷圖G。使用輔助隊列Q和訪問標志數(shù)組visited。 for(v=0; v0;w=NextAdjVex(G,u,w) if(!visitedw) visitedw = TRUE; Visit(w); EnQueue(Q,w); / u的尚未訪問的鄰接頂點w入隊列Q /while / if / BFSTraverse,搜索,1,2,3,4,5,6,7,8,9,74圖的連通性問題,一、無向圖的連通分量和生成樹 1.連通分量 無向圖的極大連通子圖。即:子圖中不能再增加一個頂點,已有頂點的邊均包含在內(nèi)。 無向圖的連通分量的產(chǎn)生-多次調(diào)用D

21、FS 2.生成樹 一個連通圖的生成樹是一個極小連通子圖,且含有圖中全部頂點,無向圖,連通分量,連通圖,生成樹,3.無向圖的生成樹 對一個連通圖G，從圖中任意一個頂點出發(fā)遍歷圖時，把E分為E1和E2，E1為遍歷過程中經(jīng)過的邊的集合，E2為剩余邊的集合，則E1與V構(gòu)成G的極小連通圖，即連通圖的一棵生成樹 若遍歷為DFS，則稱為深度優(yōu)先生成樹 若遍歷為BFS，則稱為廣度優(yōu)先生成樹,對于非連通圖，每個連通分量中的頂點集合,加上遍歷時經(jīng)過的邊，構(gòu)成了非連通圖的生成森林。,生成森林,4.無向非連通圖的深度優(yōu)先生成森林 void DFSForest(Graph G,CSTree /建立以p為根的生成樹 /D

22、FSForest,void DFSTree(Graph G, int v, CSTree /從第w個頂點出發(fā)深度優(yōu)先遍歷圖G,建立子生成樹q / if / DFSTree,二、最小生成樹Mininum Cost Spanning Tree 問題： 設(shè)有n個城市，兩個城市之間都可以有一條路線，如何從最多n(n-1)/2條邊中選擇代價和最小的n-1條邊(要包含所有頂點),就是連通圖的最小代價生成樹問題，簡稱最小生成樹。,1.普里姆算法Prim 設(shè)N=（V，E）為連通網(wǎng) 用TE表示N上最小生成樹邊的集合 (1)從V中選一頂點u0加入U，TE= (2)對所有uU，vV-U，（u，v）E,找一條代價最小

23、的邊（u0，v0）加入TE,并把v0加入U (3)重復(fù)(2)，直到U=V為止,則（V，TE）為N的最小生成樹,U,V-U,v4,v6,v1,v2,v3,v5,1,5,5,5,6,6,6,3,4,2,2MST性質(zhì)(Prime算法正確性證明） 設(shè)N=(V,E)是一個連通圖, U是V的一個非空子集 若(u,v)是一個具有最小代價的邊,uU，vV-U 則必存在一棵包含邊(u ,v)的最小生成樹,u,v,u,v,U,V-U,證明： 假設(shè)網(wǎng)N的任何一棵最小生成樹都不包含(u ,v) 設(shè)T是N上的一棵最小生成樹，把(u ,v)加入到T中 則T中必存在一條包含(u ,v)的回路 同時,T中必存在另一條邊(u,

24、v)， 其中uU vV-U 并且u和u ,v和v之間均存在路徑相通 刪去邊(u,v)，則可削去回路， 得到另一棵生成樹T 顯然,T的代價不高于T,且包含邊(u ,v),矛盾。,設(shè)N=（V，E）為連通網(wǎng) 用TE表示N上最小生成樹邊的集合 (1)從V中選一頂點u0加入U，TE= (2)對所有uU，vV-U，（u，v）E,找一條代價最小的邊（u0，v0）加入TE,并把v0加入U (3)重復(fù)(2),直到U=V為止,則（V,TE）為N的最小生成樹,圖-鄰接矩陣 最小的邊（u0，v0）（ u0U，v0V-U）用矩陣closedge表示,struct VertexType adjvex; /最短的邊對應(yīng)u中

25、的頂點 VRType lowcost;/記錄u中頂點到頂點j的最短的邊 closedgeMAX_VERTEX_NUM;,void MiniSpanTree_PRIM(MGraph G,VertexType u) k = LocateVex(G, u ); for(j=0;jG.vexnum; +j ) / 輔助數(shù)組初始化 if(j!=k) closedgej=u,G.arcskj.adj; /adjvex,lowcost closedgek.lowcost = 0; / 初始，U = u,for(i=1; iG.vexnum;+i) / 選擇其余G.vexnum-1個頂點 k =minimum

26、(closedge); /求出T的下一個結(jié)點:第k頂點 printf(closedgek.adjvex,G.vexsk); /輸出生成樹的邊 closedgek.lowcost = 0; /第k頂點并入U集 for (j=0; jG.vexnum; +j) if(G.arcskj.adjclosedgej.lowcost) closedgej=G.vexsk,G.arcskj.adj; / MiniSpanTree,3.克魯斯卡爾算法 設(shè)連通圖N=（V，E） (1)構(gòu)造非連通圖T=(V,),圖中每個頂點自成一個連通分量 (2)在E中選擇代價最小的邊（u，v），并刪去該邊。若(u,v)落在T中不

27、同的連通分量上,則將此邊加入T中 (3)重復(fù)(2），直到T中只有一個連通分量為止,2,4,5,3,6.5有向無環(huán)圖及其應(yīng)用,一、DAG圖 -Directed Acycline Graph 一個無環(huán)的有向圖稱為有向無環(huán)圖,二、拓撲排序 Topological Sort 1AOV網(wǎng) Activity On Vertex Network 用頂點表示活動， 用弧表示活動之間的優(yōu)先關(guān)系的有向圖 稱為頂點表示活動的網(wǎng)，簡稱AOV網(wǎng)。 在網(wǎng)中,若頂點i到頂點j有一條路徑,則i為前驅(qū), j為后繼。若A，則vi為vj的直接前驅(qū)，vj為vi直接后繼,在AOV網(wǎng)中不能出現(xiàn)環(huán)，判定網(wǎng)中是否出現(xiàn)環(huán)的辦法是拓撲排序。若所

28、有的頂點都在拓撲有序序列中，則AOV網(wǎng)中無環(huán)，否則有環(huán)。,C語言程序設(shè)計,數(shù)據(jù)結(jié)構(gòu)與算法,面向?qū)ο蟪绦蛟O(shè)計,計算機網(wǎng)絡(luò)原理,信息科學(xué)導(dǎo)論,電路原理,大學(xué)物理,數(shù)字邏輯電路實驗,組成原理實驗,操作系統(tǒng),匯編語言程序設(shè)計,高等數(shù)學(xué)1,離散數(shù)學(xué),數(shù)據(jù)庫原理,線性代數(shù),基礎(chǔ)物理實驗B,高等數(shù)學(xué)2,高等數(shù)學(xué)3,C程序設(shè)計實驗,數(shù)據(jù)結(jié)構(gòu)實驗,電路原理實驗,概率與數(shù)理統(tǒng)計,數(shù)字邏輯電路,計算機組成原理,網(wǎng)絡(luò)原理實驗,操作系統(tǒng)實驗,面向?qū)ο髮嶒?2拓撲次序 設(shè)AOV網(wǎng)中有n個頂點V1，V2，Vn， 將頂點排成這樣一個線性次序：Vi1，Vi2，Vin， 其中i1，i2，in是1到n的一個排列 且若V ij，V

29、ikA，則jk,對AOV網(wǎng)給出拓撲次序的過程稱為拓撲排序,3拓撲排序算法 (1)在網(wǎng)中選一個沒有前驅(qū)的頂點且輸出它 (2)從圖中刪去該頂點及所有以它為尾的弧 (3)重復(fù)(1)(2)直到所有頂點被輸出 或圖中不存在無前驅(qū)的頂點為止,。采用鄰接表作存儲結(jié)構(gòu) 。用一個數(shù)組indegree存放頂點的入度 。用一個棧存放入度為0的頂點,Status TopologicalSort( ALGraph G) /有向圖G采用鄰接表存儲結(jié)構(gòu)。 /若G無回路,則輸出G的頂點的一個拓撲序列并返回OK, /否則ERROR FindInDegree(G,indegree); /對各頂點求入度indegree InitS

30、tack(S); / 建零入度頂點棧S for(i=0; iG.vexnum; +i ) if(!indegreei) Push(S, i); / 入度為0者進棧 count = 0; / 對輸出頂點計數(shù),while(!StackEmpty(S) Pop(S,i); printf(i,G.verticesi.data); +count; / 輸出i號頂點并計數(shù) for(p=G.verticesi.firstarc; p; p=p-nextarc) k = p-adjvex; /對i 號頂點的每個鄰接的入度減1 if(!(- -indegreek)Push(S, k); /若入度減為0，則入棧

31、/ for DestroyStack(S); if(countG.vexnum) return ERROR; /該有向圖有回路 else return OK; / TopologicalSort,。還可以利用深度優(yōu)先遍歷過程進行拓撲排序，按退出DFS的逆序為拓撲次序,1,2,3,4,5,6,拓撲次序為：v6、v1、v4、v3、v5、v2,4.關(guān)鍵路徑 AOE網(wǎng)Activity On Edge 頂點-事件 邊-活動 權(quán)-活動持續(xù)的時間 用AOE網(wǎng)估計工程的完工時間,Vi表示在此之前的活動已完成，在此之后的活動可以開始,1,2,3,4,5,買面粉3,買雞蛋3,買白菜4,買熟食6,6,7,剁餡5,切

32、2,和面2,煮雞蛋1,包餃子4,最短要多久才能包好餃子,開始聚餐?,在一般情況下,AOE網(wǎng)中只有一個入度為0的頂點,稱為源點 只有一個出度為0的頂點，稱為匯（聚）點 ？完成整個工程至少需要多少時間 -從源點到匯點的最長路徑 ？哪些活動是影響工程進度的關(guān)鍵,路徑長度最長的路徑叫做關(guān)鍵路徑 Critical Path 從源點到Vi的最長路徑叫做事件的最早發(fā)生時間,也就是所有以Vi為尾的弧所表示活動的最早開始時間,令e(i)表示ai的最早開始時間 l(i)表示ai的最遲開始時間 l(i)-e(i)為時間余量 關(guān)鍵路徑上的所有活動有：l(i)=e(i) 把所有e(i)=l(i)的活動叫做關(guān)鍵活動。,設(shè)

33、ai由弧表示 ve(j)表示事件j的最早發(fā)生時間 vl(j)表示事件j的最遲發(fā)生時間 ai的持續(xù)時間為dut() 則：e(i)=ve(j) l(i)=vl(k)-dut(),最早開始時間:前驅(qū)活動都按期完成情況下的開始時間 最遲開始時間:保證所有活動都能按期完成情況下最晚開始時間 關(guān)鍵路徑上的所有活動最早=最遲,計算的方法： （1）ve(0)=0 （2）按拓撲順序計算：,其中T是所有以第j個頂點為頭的弧的集合,（3）vl(n-1)=ve(n-1) （4）按逆拓撲順序計算：,其中S是所有以第i個頂點為尾的弧的集合,（5）根據(jù)各頂點的ve和vl的值 計算每條弧s的e(s)和l(s),ve(3)=5

34、,ve(4)=7,ve(7)=14,ve(8)=18,vl(8)=18,vl(7)=14 vl(6)=16,vl(4)=7,ve(0)=0,vl(1)=6 vl(2)=6,vl(0)=0,ve(5)=7,ve(6)=16,vl(5)=10,vl(3)=8,ve(2)=4 ve(1)=6,Status TopologicalOrder(ALGraph G, Stack / 初始化,while (! StackEmpty(S) Pop(S, j); Push(T,j); +count; /j號頂點入T棧并計數(shù) for(p=G.verticesj.firstarc;p;p=p-nextarc) k

35、= p-adjvex; / 對j號頂點的每個鄰接點的入度減1 if(-indegreek=0)Push(S, k); /若入度減為0，則入棧 if(vej+*(p-info)vek)vek=vej+*(p-info); / *(p-info)= dut() / while DestroyStack(S); if(countG.vexnum) return ERROR; /該有向網(wǎng)有回路 else return OK; / TopologicalOrder,Status CriticalPath(ALGraph G) /G為有向網(wǎng)，輸出G的各項關(guān)鍵活動 if(!TopologicalOrder(

36、G,T) return ERROR; vl0.G.vexnum-1=veG.vexnum-1; /初始化頂點事件的最遲發(fā)生時間 while (! StackEmpty(T) /按拓撲逆序求各頂點的v1值 for(Pop(T,j),p=G.verticesj.firstarc; p; p=p-nextarc) k=p-adjvex; dut = * (p-info); / dut if(vlk-dutv1j) vlj = vlk-dut; / for,for(j=0;jnextarc) k = p-adjvex; dut = * (p-info) ; ee=vej; el=vlk-dut; ta

37、g=(ee=e1)? * : ; printf ( j,k, dut, ee, el, tag); / 輸出關(guān)鍵活動 / CriticalPath,76最短路徑 用頂點表示城市， 用邊表示城市之間的交通狀況 用邊上的權(quán)表示城市之間的耗費（距離、時間、各種費用等） 一、從一點到另一點，經(jīng)過的結(jié)點最少 二、從某個源點到其余各個頂點的最短路徑 給定帶權(quán)的有向圖G和源點v， 求從v到G中其余各點的最短路徑 方法：按路徑長度遞增序產(chǎn)生最短路徑 -迪杰斯特拉Dijksta方法,v0,v5,60,v1,v2,v3,v4,100,30,10,10,50,5,20,v0,v5,v1,v2,v3,v4,存儲結(jié)構(gòu) 用帶權(quán)的鄰接矩陣arcs表示帶權(quán)有向圖 arcsij= A 上的權(quán)值 A,算法 (1)設(shè)S為已找到從v出發(fā)的最短路徑的終點集合, 初值S= Di表示從v到Vi的最短路徑的長度 若A,Di為從v到Vi上的權(quán),否則為 即：Di=arcsLo