1、第七章 圖7.1 圖的定義7.2 圖的存儲結構7.3 圖的遍歷7.4 圖的連通性問題7.5 有向無環圖及其應用7.6 最短路徑71圖的定義一、有向圖和無向圖頂點VertexV:頂點的有窮非空集合VR兩個頂點之間的關系的集合若VR 則表示從v到w有一條弧Arc v稱作弧尾或初始點，Tail w稱作弧頭或終端點, Head有向圖無向圖稀疏圖稠密圖網Network子圖鄰接點相關聯頂點的度、入度、 出度圖中邊/弧的數目與頂點度的關系路徑路徑的長度連通圖回路或環Cycle簡單路徑簡單回路強連通圖完全圖有向完全圖由頂點的集合和弧的集合構成的圖稱為有向圖G1=(V1,A1)V1=v1,v2,v3,v4A1=

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

3、E，則稱頂點v和v1互為鄰接點 邊（v，v1）依附于頂點v和v1 或邊（v，v1）與頂點v、v1相關聯頂點v的度是和v相關聯的邊的數目,記作TD（v）2.有向圖G =（V，A）弧v，v1A， 則稱v鄰接到v1 或v1鄰接自v 弧v，v1和頂點v、v1相關聯以頂點v為頭的弧的條數稱作v的入度,記作ID（v） 以頂點v為尾的弧的條數稱作v的出度,記作OD（v） 頂點v的度TD（v）=ID（v）+OD（v）圖中邊/弧的數目與頂點度的關系(若圖中有n個頂點，e條邊/弧)五、路徑1.無向圖G=（V，E）中 從頂點v到v1的路徑是一個頂點序列: v=Vi,0, Vi,1,Vi,m =v1 其中（Vi,j-

4、1，Vi,j）E， 1jm3.路徑的長度是路徑上邊或弧的數目2.有向圖G=（V，A） 從頂點v到v1的路徑是一個有向頂點序列: v=Vi,0, Vi,1,Vi,m=v1 其中Vi,j-1，Vi,jA， 1jm4.第一個頂點與最后一個頂點相同的路徑稱為回路或環Cycle5.序列中頂點不重復出現的路徑稱為簡單路徑 除第一個和最后一個頂點外，其余頂點不重復出現的回路稱為簡單回路六、連通圖 Connected Graph1.無向圖 v到v1有路徑，稱v和v1是連通的 若圖中任意兩個頂點vi、vjV都是連通的 則稱G是連通圖2.若一個無向圖中有n個頂點和少于n-1條邊 則該圖是非連通圖 若它有多于n-1

5、條邊，則一定有環3.有向圖 對于每一對vi、vjV,從vi到vj和vj到vi 都存在路徑,則稱 G為強連通圖七、圖的ADTADT Graph數據對象V:V是具有相同特性的數據元素的集合，稱為頂點。 數據關系R： R=VR VR=|v,wV且p(v,w), 表示從v到w的弧， 謂詞P(v,w)定義了弧的意義或信息 基本操作P： CreateGraph(&G,V,VR); 初始條件：V是圖的頂點集，VR是圖中弧的集合。 操作結果：按V和VR的定義構造圖G. DestroyGraph(&G); 初始條件:圖G存在. 操作結果:銷毀圖G。LocateVex(G,u); 初始條件：圖G存在，u和G中頂點

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

7、最后一個鄰接點則返回“空”。InsertVex(&G,v); 初始條件：圖G存在，v和圖中頂點有相同特征。 操作結果: 在圖G中增添新頂點v。 DeleteVex(&G,v); 初始條件：圖G存在，v是G中某個頂點 操作結果：刪除G中頂點v及其相關的弧。InsertArc(&G,v,w); 初始條件：圖G存在，v和w是G中兩個頂點。 操作結果：在G中增添弧。若G是無向的，則還增添對稱弧DeleteArc(&G,v,w); 初始條件：圖G存在，v和w是G中兩個頂點。 操作結果：在G中刪除弧。若G是無向的，則還刪除對稱弧DFSTraverse(G,v,Visit(); 初始條件：圖G存在，v是G某

8、個頂點，Visit是頂點的應用函數。 操作結果:從頂點v起深度優先遍歷圖G，并對每個頂點調用visit一次且 僅一次。一旦visit()失敗，則操作失敗。BFSTraverse(G,v,Visit(); 初始條件：圖G存在，v是G某個頂點，visit是頂點的應用函數。 操作結果: 從頂點v起廣度優先遍歷圖G， 并對每個頂點調用visit 一次且僅一次。 一旦visit()失敗，則操作失敗。ADT Graph7.2 圖的存儲結構在圖中，無法用數據元素在存儲區的物理位置表示元素之間的關系。一、數組表示法(鄰接矩陣表示法) 用一個數組存儲頂點的信息， 用另一個數組存儲邊或弧的信息-鄰接矩陣0123v

9、1v2v3v401234南校區，105號北一區，83號北二區，56號東一區，甲23東二區，5號15105301220321041.圖的數組存儲表示/ _ _ _ _ _ _圖的數組（鄰接矩陣）存儲表示 _ _ _ _ _ _ _#define INFINITY INT_MAX / 最大值#define MAX_VERTEX_NUM 20 /最大頂點個數typedef enum DG,DN,UDG,UDNGraphKind; /有向圖，有向網，無向圖，無向網typedef struct ArcCellVRType adj; /VRType是頂點關系類型.對無權圖,用1或0 /表示相鄰否；對帶權圖

10、，則為權值類型。 InfoType *Info; /該弧相關信息的指針ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM; / 頂點向量 AdjMatrix arcs; / 鄰接矩陣 int vexnum, arcnum; / 圖的當前頂點數和弧數 GraphKind kind; / 圖的種類標志MGraph;Mgraph G1; G1.vexnum=4G1. arcnum=4 G1.kind=DG 0123v1v2v3v4G1.vexsG1.arcs01.adj=1

11、G1.arcs2圖的構造方法Status CreateGraph( MGraph &G)/ 采用數組（鄰接矩陣）表示法，構造圖G scanf(&G.kind); switch (G.kind) case DG: return CreateDG(G); / 構造有向圖G case DN: nretur CreateDN(G); / 構造有向網G case UDG: return CreateUDG(G); / 構造無向圖G case UDN: return CreateUDN(G); / 構造無向網G default : return ERROR; / CreateGraph Status Cr

12、eateUDN(MGraph &G)/采用數組（鄰接矩陣）表示法，構造無向網Gscanf(&G.vexnum, &G.arcnum, &IncInfo); / IncInfo 為0則各弧不含其它信息for (i=0; iG.vexnum; +i ) scanf (&G.vexsi); / 構造頂點向量for (i=0; iG.vexnum; +i ) / 初始化鄰接矩陣 for (j=0; jG.vexnum; +j ) G.arcsij=INFINITY, NULL; /adj,infofor (k=0; kG.arcnum; +k ) / 構造鄰接矩陣 scanf (&v1, &v2, &

13、w); / 輸入一條邊依附的頂點及權值 i =LocateVex(G, v1 ); j = LocateVex (G, v2 ); / 確定v1和v2在G中位置 G.arcij.adj = w; / 弧的權值 if (IncInfo) Input(* G.); / 若弧含有相關信息,則輸入 G.arcsji =G.arcsij; / 置的對稱弧 return OK; / CreateUDN二、鄰接表Adjacency List方法：對每個頂點建立一個單向鏈表 鏈接與vi有邊相連的頂點（無向圖） 或從vi出發到達的頂點（有向圖） datafirstarc指向該點出發到達的第

14、一條弧adjvex nextarc info每個頂點對應一個頭結點每條邊/弧對應一個結點到達頂點 下一條邊/弧 邊的信息無向圖邊結點有向圖/- - - - - - - 圖的鄰接表存儲表示 - - - - - - - #define MAX_VERTEX_NUM 20typedef struct ArcNode int adjvex; / 該弧所指向的頂點的位置 struct ArcNode * nextarc; / 指向下一條弧的指針 InfoType * info; / 該弧相關信息的指針ArcNode ;typedef struct VNode VertexType data; / 頂點信

15、息 ArcNode * firstarc; / 指向第一條依附頂點的弧的指針VNode, AdjListMAX_VERTEX_NUM ;typedef struct AdjList vertices; int vexnum, arcnum; / 圖的當前頂點數和弧數 int kind; / 圖的種類標志 ALGraph;ALGraph G1;G1.kind=DG;G1.vexnum=4G1.arcnum=4G1.verticesdatafirstarcadjvex info nextarc三、十字鏈表 Orthogonal List方法：圖中的每個頂點用一個結點表示：圖中的每一弧也用一個結點表

16、示：data firstinfirstouttailvex headvex hlink tlink info# define MAX_VERTEX_NUM 20typedef struct ArcBox int tailvex, headvex ; / 該弧的尾和頭頂點的位置 struct ArcBox *hlink, *tlink; /分別為弧頭相同和弧尾相同的弧的鏈域 Info type *info; / 該弧相關信息的指針ArcBox;typedef struct VexNode VertexType data; ArcBox * firstin, * firstout; /分別指向該頂

17、點第一條入弧和出弧 VexNode ;typedef struct VexNode xlist MAX_VERTEX_NUM ; / 表頭向量 int vexnum, arcnum; / 有向圖的當前頂點數和弧數 OLGraph ;Status CreateDG(OLGraph &G) /采用十字鏈表存儲表示， /構造有向圖G, IncInfo為0則各弧不含其它信息 scanf(&G.vexnum, &G.arcnum, &IncInfo); for(i=0; iG.vexnum; +i ) / 構造表頭向量 scanf(&G.xlisti.data); / 輸入頂點值 G.xlisti.fi

18、rstin = NULL; G.xlisti.firstout = NULL; / 初始化指針 for(k=0; kinfo); /若弧含有相關信息，則輸入 / CreateDG四、鄰接多重表 Adjancency Multilist 頂點和邊分別用一個結點表示 邊：mark ivex ilink jvex jlink info該邊是否搜索過頂點i在圖中的位置(編號)下一條與i有關的邊有關邊的信息data firstedge頂點：242342# define MAX_VERTEX_NUM 20typedef enum unvisited, visitedVisitIf ;typedef str

19、uct 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; / 無向圖的當前頂

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

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

22、t v) / 對圖G作深度優先遍歷VisitFunc = Visit; /使用全局變量VisitFunc，使DFS不必設函數指針參數 for(v=0; vG.vexnum; +v) visitedv = FALSE ; / 訪問標志數組初始化 for(v=0; v0; w=NextAdjVex(G,v,w) if(!visitedw) DFS(G,w); /對v的尚未訪問的鄰接頂點w遞歸調用DFS printf(v); /起什么作用ABCDEFHGK123456789搜索回退ABCDEFHGK12345679二、廣度優先收索Breadth-First-Search(BFS)方法： 從圖中某個頂

23、點出發（設為vi），訪問vi， 從vi出發，依次訪問vi的所有未被訪問的鄰接點， 再從這些鄰接點出發， 依次訪問它們的所有未被訪問的鄰接點, 若圖中仍有未被訪問的頂點， 從中選擇一個作為起點，重復上述過程 直到所有頂點均被訪問過為止。void BFSTraverse(Graph G,Status(* Visit)(int v) / 按廣度優先非遞歸遍歷圖G。使用輔助隊列Q和訪問標志數組visited。 for(v=0; vG.vexnum; +v ) visitedv = FALSE; InitQueue(Q); / 置空的輔助隊列Q for (v=0; v0;w=NextAdjVex(G,u

24、,w) if(!visitedw) visitedw = TRUE; Visit(w); EnQueue(Q,w); / u的尚未訪問的鄰接頂點w入隊列Q /while / if / BFSTraverse搜索ABCDEFHGK123456789ABCDEFHGK12345678974圖的連通性問題一、無向圖的連通分量和生成樹1.連通分量 無向圖的極大連通子圖。即:子圖中不能再增加一個頂點,已有頂點的邊均包含在內。 無向圖的連通分量的產生-多次調用DFS2.生成樹 一個連通圖的生成樹是一個極小連通子圖,且含有圖中全部頂點無向圖連通分量連通圖生成樹3.無向圖的生成樹 對一個連通圖G，從圖中任意一

25、個頂點出發遍歷圖時，把E分為E1和E2，E1為遍歷過程中經過的邊的集合，E2為剩余邊的集合，則E1與V構成G的極小連通圖，即連通圖的一棵生成樹 若遍歷為DFS，則稱為深度優先生成樹 若遍歷為BFS，則稱為廣度優先生成樹v1v2v3v4v5v6v7v8深度優先生成樹v1v2v3v4v5v6v7v8廣度優先生成樹v1v2v3v4v5v6v7v8對于非連通圖，每個連通分量中的頂點集合,加上遍歷時經過的邊，構成了非連通圖的生成森林。生成森林4.無向非連通圖的深度優先生成森林void DFSForest(Graph G,CSTree &T) /建立無向圖的深度優先生成森林的(最左)孩子(右)兄弟鏈表 T

26、=NULL; for(v=0; vG.vexnum; +v) visitedv=FALSE; /頂點遍歷初始化 for(v=0; vnextsibling=p; /是其它生成樹的根(前一棵的根的兄弟） q=p; /q指示當前生成樹的根 DFSTree(G,v,p); /建立以p為根的生成樹 /DFSForestvoid DFSTree(Graph G, int v, CSTree &T) / 從第v個頂點出發深度優先遍歷圖G，建立以T為根的生成樹。 visitedv=TRUE; first =TRUE; for(w=FisrtAdjVex(G,v);w=0;w=NextAdjVex(G,v,w

27、) if(!visitedw) p=(CSTree)malloc(sizeof(CSNode); / 分配孩子結點 *p=GetVex(G,w), NULL, NULL ; if(first) / w是v的第一個未被訪問的鄰接頂點 T-firstchild=p; first= FALSE; /是根的第一個孩子結點 else / w是v的其它未被訪問的鄰接頂點 q-nextsibling = p; /是上一鄰接頂點的右兄弟結點 q = p; DFSTree(G,w,q);/從第w個頂點出發深度優先遍歷圖G,建立子生成樹q / if/ DFSTree二、最小生成樹Mininum Cost Span

28、ning Tree問題： 設有n個城市，兩個城市之間都可以有一條路線，如何從最多n(n-1)/2條邊中選擇代價和最小的n-1條邊(要包含所有頂點),就是連通圖的最小代價生成樹問題，簡稱最小生成樹。 1.普里姆算法Prim 設N=（V，E）為連通網 用TE表示N上最小生成樹邊的集合 (1)從V中選一頂點u0加入U，TE= (2)對所有uU，vV-U，（u，v）E,找一條代價最小的邊（u0，v0）加入TE,并把v0加入U (3)重復(2)，直到U=V為止,則（V，TE）為N的最小生成樹 UV-Uv4v6v1v2v3v51555666342v1v31v1v31v64v42v25v53v1v31v64

29、v42v1v31v64v25v42v1v31v642MST性質(Prime算法正確性證明）設N=(V,E)是一個連通圖, U是V的一個非空子集若(u,v)是一個具有最小代價的邊,uU，vV-U則必存在一棵包含邊(u ,v)的最小生成樹uvuvUV-U證明： 假設網N的任何一棵最小生成樹都不包含(u ,v) 設T是N上的一棵最小生成樹，把(u ,v)加入到T中 則T中必存在一條包含(u ,v)的回路 同時,T中必存在另一條邊(u,v)， 其中uU vV-U 并且u和u ,v和v之間均存在路徑相通 刪去邊(u,v)，則可削去回路， 得到另一棵生成樹T 顯然,T的代價不高于T,且包含邊(u ,v),

30、矛盾。設N=（V，E）為連通網用TE表示N上最小生成樹邊的集合(1)從V中選一頂點u0加入U，TE=(2)對所有uU，vV-U，（u，v）E,找一條代價最小的邊（u0，v0）加入TE,并把v0加入U (3)重復(2),直到U=V為止,則（V,TE）為N的最小生成樹 圖-鄰接矩陣最小的邊（u0，v0）（ u0U，v0V-U）用矩陣closedge表示struct VertexType adjvex; /最短的邊對應u中的頂點 VRType lowcost;/記錄u中頂點到頂點j的最短的邊 closedgeMAX_VERTEX_NUM;void MiniSpanTree_PRIM(MGraph G

31、,VertexType u)k = LocateVex(G, u ); for(j=0;jG.vexnum; +j ) / 輔助數組初始化 if(j!=k) closedgej=u,G.arcskj.adj; /adjvex,lowcost closedgek.lowcost = 0; / 初始，U = ufor(i=1; iG.vexnum;+i) / 選擇其余G.vexnum-1個頂點 k =minimum(closedge); /求出T的下一個結點:第k頂點 printf(closedgek.adjvex,G.vexsk); /輸出生成樹的邊 closedgek.lowcost = 0;

32、 /第k頂點并入U集 for (j=0; jG.vexnum; +j) if(G.arcskj.adjclosedgej.lowcost) closedgej=G.vexsk,G.arcskj.adj; / MiniSpanTree1234UV-UkadjvexlowcostA2AA6A4AB,C,D,EadjvexlowcostA, adjvexlowcostadjvexlowcostadjvexlowcost3.克魯斯卡爾算法 設連通圖N=（V，E） (1)構造非連通圖T=(V,),圖中每個頂點自成一個連通分量 (2)在E中選擇代價最小的邊（u，v），并刪去該邊。若(u,v)落在T中不同的

33、連通分量上,則將此邊加入T中 (3)重復(2），直到T中只有一個連通分量為止v1v2v3v4v5v6v4v6v1v2v3v515556663421v1v2v3v4v5v612453v1v2v3v4v5v612v1v2v3v4v5v6123v1v2v3v4v5v614236.5有向無環圖及其應用一、DAG圖 -Directed Acycline Graph 一個無環的有向圖稱為有向無環圖二、拓撲排序 Topological Sort1AOV網 Activity On Vertex Network 用頂點表示活動， 用弧表示活動之間的優先關系的有向圖 稱為頂點表示活動的網，簡稱AOV網。 在網中,

34、若頂點i到頂點j有一條路徑,則i為前驅, j為后繼。若A，則vi為vj的直接前驅，vj為vi直接后繼在AOV網中不能出現環，判定網中是否出現環的辦法是拓撲排序。若所有的頂點都在拓撲有序序列中，則AOV網中無環，否則有環。C語言程序設計數據結構與算法面向對象程序設計計算機網絡原理信息科學導論電路原理大學物理數字邏輯電路實驗 組成原理實驗操作系統匯編語言程序設計高等數學1離散數學數據庫原理線性代數基礎物理實驗B高等數學2高等數學3C程序設計實驗數據結構實驗電路原理實驗概率與數理統計數字邏輯電路計算機組成原理網絡原理實驗操作系統實驗 面向對象實驗2拓撲次序 設AOV網中有n個頂點V1，V2，Vn，

35、將頂點排成這樣一個線性次序：Vi1，Vi2，Vin， 其中i1，i2，in是1到n的一個排列 且若V ij，V ikA，則jk對AOV網給出拓撲次序的過程稱為拓撲排序3拓撲排序算法(1)在網中選一個沒有前驅的頂點且輸出它(2)從圖中刪去該頂點及所有以它為尾的弧(3)重復(1)(2)直到所有頂點被輸出 或圖中不存在無前驅的頂點為止。采用鄰接表作存儲結構。用一個數組indegree存放頂點的入度。用一個棧存放入度為0的頂點Status TopologicalSort( ALGraph G) /有向圖G采用鄰接表存儲結構。 /若G無回路,則輸出G的頂點的一個拓撲序列并返回OK, /否則ERROR F

36、indInDegree(G,indegree); /對各頂點求入度indegree InitStack(S); / 建零入度頂點棧S for(i=0; inextarc) k = p-adjvex; /對i 號頂點的每個鄰接的入度減1 if(!(- -indegreek)Push(S, k); /若入度減為0，則入棧 / for DestroyStack(S); if(countG.vexnum) return ERROR; /該有向圖有回路 else return OK;/ TopologicalSort。還可以利用深度優先遍歷過程進行拓撲排序，按退出DFS的逆序為拓撲次序v1v2v3v4v

37、5v6123456拓撲次序為：v6、v1、v4、v3、v5、v24.關鍵路徑 AOE網Activity On Edge 頂點-事件 邊-活動 權-活動持續的時間 用AOE網估計工程的完工時間Vi表示在此之前的活動已完成，在此之后的活動可以開始a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=412345買面粉3買雞蛋3買白菜4買熟食667剁餡5切2和面2煮雞蛋1包餃子4最短要多久才能包好餃子,開始聚餐?在一般情況下,AOE網中只有一個入度為0的頂點,稱為源點只有一個出度為0的頂點，稱為匯（聚）點？完成整個工程至少需要多少時間 -從源點到匯點的最長路徑？哪

38、些活動是影響工程進度的關鍵路徑長度最長的路徑叫做關鍵路徑 Critical Path從源點到Vi的最長路徑叫做事件的最早發生時間,也就是所有以Vi為尾的弧所表示活動的最早開始時間 令e(i)表示ai的最早開始時間 l(i)表示ai的最遲開始時間 l(i)-e(i)為時間余量關鍵路徑上的所有活動有：l(i)=e(i) 把所有e(i)=l(i)的活動叫做關鍵活動。設ai由弧表示 ve(j)表示事件j的最早發生時間 vl(j)表示事件j的最遲發生時間 ai的持續時間為dut() 則：e(i)=ve(j) l(i)=vl(k)-dut()a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7

39、a9=4a10=2a11=4最早開始時間:前驅活動都按期完成情況下的開始時間最遲開始時間:保證所有活動都能按期完成情況下最晚開始時間關鍵路徑上的所有活動最早=最遲計算的方法：（1）ve(0)=0（2）按拓撲順序計算： 其中T是所有以第j個頂點為頭的弧的集合i1i2i3j（3）vl(n-1)=ve(n-1)（4）按逆拓撲順序計算： 其中S是所有以第i個頂點為尾的弧的集合 j1j2j3i（5）根據各頂點的ve和vl的值 計算每條弧s的e(s)和l(s)a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4ve(3)=5ve(4)=7ve(7)=14ve(8)=

40、18vl(8)=18vl(7)=14vl(6)=16vl(4)=7ve(0)=0vl(1)=6vl(2)=6vl(0)=0ve(5)=7ve(6)=16vl(5)=10vl(3)=8ve(2)=4ve(1)=6Status TopologicalOrder(ALGraph G, Stack &T) FindInDegree(G, indegree); /對各頂點求入度indegree InitStack(S);/建零入度頂點棧S for(i=0; inextarc) k = p-adjvex; / 對j號頂點的每個鄰接點的入度減1 if(-indegreek=0)Push(S, k); /若入

41、度減為0，則入棧 if(vej+*(p-info)vek)vek=vej+*(p-info); / *(p-info)= dut() / while DestroyStack(S); if(countnextarc) k=p-adjvex; dut = * (p-info); / dut if(vlk-dutv1j) vlj = vlk-dut; / forfor(j=0;jnextarc) k = p-adjvex; dut = * (p-info) ; ee=vej; el=vlk-dut; tag=(ee=e1)? * : ; printf ( j,k, dut, ee, el, tag

42、); / 輸出關鍵活動 / CriticalPath76最短路徑 用頂點表示城市， 用邊表示城市之間的交通狀況 用邊上的權表示城市之間的耗費（距離、時間、各種費用等）一、從一點到另一點，經過的結點最少二、從某個源點到其余各個頂點的最短路徑 給定帶權的有向圖G和源點v， 求從v到G中其余各點的最短路徑方法：按路徑長度遞增序產生最短路徑 -迪杰斯特拉Dijksta方法v0v560v1v2v3v410030101050520v0v5v1v2v3v430101020存儲結構用帶權的鄰接矩陣arcs表示帶權有向圖arcsij= A 上的權值 A算法(1)設S為已找到從v出發的最短路徑的終點集合, 初值S

43、= Di表示從v到Vi的最短路徑的長度 若A,Di為從v到Vi上的權,否則為 即：Di=arcsLocateVex(G,v),i, ViV(2)選擇Vj，使得 Dj=minDi| ViV-S 并修改S: S=Sj Vj就是一條從v出發的最短路徑的頂點(3)修改從v出發到集合V-S上任一點Vk可到達的最短路徑 即如果 Dj+arcsjkDk 則： Dk=Dj+arcsjk(如果S為已求得最短路徑的終點集合,則下一條最短路徑或者是弧, 或者是從v到Vk加上弧,其中 VkS）(4)重復(2)(3)共n-1次,求得從v到圖中其余各頂點的最短路徑終點從V0到各終點D值和最短路徑的求解過程V1V2V3V4VjV5i=1V210(V0 ,V2)30(V0 ,V4)100(V0 ,V5)V0 ,V2S30(V0 ,V4)100(V0 ,V5)60(V0 ,V2,V3)V0 ,V2,V4V4i=2i=550(V0 ,V4 ,V3)90(V0 ,V4 ,V5)V3i=3V0,