第8章-图数据结构课件.ppt

1、2023-2-1112023-2-112数据结构 线性-表：每个元素有一个直接前趋和一直接后继非线性 每一层元素可能和下层中的多个元素相关，但只能和上一层中的一个 元素相关 数据元素之间的关系是任意的树：图：2023-2-113图的定义：Graph=(V,E)G=(V,E)V:是顶点的有穷非空集合 E:边的集合（边：顶点的偶对）2023-2-114 V(G1)=V1,V2,V3,V4 E(G1)=(v1,v2),(v1,v3),(v1,v4),(v2,v3),(v2,v4),(v3,v4)V2V4V3V1G1例子：2023-2-115V2V1V3V(G2)=v1,v2,v3 E(G2)=,例子

2、：始点 终点2023-2-116环多重图2023-2-1172023-2-1182023-2-119ni=1e=1/2(TD(Vi)2023-2-1110V3V2V1 ID(V2)=1 TD(V2)=3 OD(V2)=22023-2-11111132413134121432312023-2-11122023-2-11132023-2-1114 非连通图 (极大连通子图叫做连通分量)2023-2-11152023-2-1116V1V2V3V4V523451011862023-2-11172023-2-11182023-2-1119 1 如果E 或 (i,j)E AEdge i j=0 否则202

3、3-2-1120V0V3V1V2V4V3V2V1V0对称矩阵0 1 1 1 1 0 1 1 1 1 0 01 1 0 0 AEdge=0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0AEdge=2023-2-1121031212835496AEdge=0 1 4 0 9 23 5 0 8 6 0 w(i,j)如果ij且 E或(i,j)EAEdgei j=如果ij且 E或(i,j)E 0 i=j 例子：2023-2-1122V0V1V2V3.dataMaxsize012n-12023-2-11232023-2-11242023-2-1125202

4、3-2-1126V2V1V4V3n 个结点，e条边的无向图需用n+2e个单位.V1 V2 V4 V3 3 1 1 2 0 0 0 3 2 1 data adjdest link顶点表NodeTable边链接表Edge Linked List01232023-2-1127V1V2V3311642邻接表V1 V2 V3 2 2 2 11 0 3 0 6 1 4 data adjdest cost link顶点表出边表012V1 V2 V3 1 2 2 3 0 11 0 4 1 6 data adjdest cost link顶点表入边表逆邻接表0122023-2-1128边的三个数据成员2023-

5、2-1129data adjNodeTable2023-2-1130图的私有数据成员2023-2-11312023-2-11322023-2-11332023-2-11342023-2-11352023-2-1136 V1V2V3V4e1e2e4e3e5V1 V2 V4 V3 data Firstout0 1 0 2 0 3 1 3 1 2 vertex1 path1vertex2 path2e1e2e3e4e52023-2-1137ADEBCe3e6e5e4e2e1A B C 1 2 D E 3 4 2 3 4 0 0 1 data Firstin Firstout 0 3 mark v1

6、v2 p1 p22023-2-11382023-2-11392023-2-1140v1v2v6v5v4v3v8v7V1V2V4V8V5V3V6V7v1v2v6v5v4v3v8v7深度优先生成树2023-2-11412023-2-1142用图的抽象数据类型来实现 算法分析：用邻接表表示 O(n+e)用邻接矩阵表示 O(n2)2023-2-11432023-2-1144v1v2v6v5v4v3v8v7 算法同样需要一个辅助数组visited 表示顶点是否被访问过.还需要一个队列,记正在访问的这一层和上一层的顶点.算法显然是非递归的.v1v2v6v5v4v3v8v7广度优先生成树V1V2V3V4V

7、5V6V7V82023-2-11452023-2-11462023-2-11472023-2-1148ABCDEFGHJIKLMNO非连通无向图非连通图的连通分量ABCDEFGA,B,F,G,E,C,DHJI H,I,J KLMNOK,L,O,M,N2023-2-11492023-2-11508.4 最小生成树最小生成树 2)生成树不唯一生成树的代价：TE（G）上诸边的代价之和n个结点的生成树有n-1条边。1.生成树的有关概念1)生成树的定义设G=（V，E）是一个连通的无向图（或是强连通有向图）从图G中的任一顶点出发作遍历图的操作，把遍历走过的边的集合记为TE（G），显然 G=（V，TE）是G

8、之子图，G被称为G的生成树（spanning tree），也称为一个连通图2023-2-11513)最小代价生成树（minimun-cost spanning tree）问题的提出：如何找到一个网络的最小生成树，即各边权的总和为最小的生成树从同一个结点出发遍历可的不同的树从不同的结点出发遍历可得不同的树2023-2-1152实际例子：6个城市已固定，现从一个城市发出信息到每一个城市 如何选择或铺设通信线路，使花费（造价）最低。前提：每条边有代价 1423566551426356如果用广度优先，则12345661534=192023-2-1153最小代价生成树14235612354=15书中介绍

9、了两个算法：Prim,Kruskal.它们都采用了逐步求解（Grandy)的策略。2023-2-1154Grandy策略：设：连通网络N=V,E,V中有n个顶点。1.先构造n个顶点，0条边的森林F=T0,T1,.,Tn-1每次向F中加入一条边。该边是一端在F的某棵树Ti上 而另一端不在Ti上的所有边中具有最小权植的边。这样使F中两棵树合并为一棵，树的棵数-1 重复n-1次 T0Tn-1 T12023-2-1155最小生成树的类声明：const int MAXINT=机器可表示的，问题中不可能出现的大数class MinSpanTree;class MSTEdgeNode friend clas

10、s MinSpanTree;private:int tail,head;int cost;tailcosthead边的结构:2023-2-1156class MinSpanTree public:MinSpanTree(int SZ=NumVertices-1):MaxSize(SZ),n(0)edgevalue=new MSTEdgeNodeMaxSize;protected:MSTEdgeNode*edgevalue;/边值数组 int MaxSize,n;/数组的最大元素个数和/当前个数；2023-2-1157Kruskal算法1)把无向图中的所有边排序 1342521012986372

11、 3 6 7 8 9 10 12（1,2)(3,5)(3,4)(4,5)(2,3)(2,5)(1,4)(1,3)2)一开始的最小生成树为 T (V,)即由 n个不同的连通分量组成TE=2023-2-11583)在E中选一条代价最小的边（u,v)加入T，一定要满足（u,v)不和TE中已有的边构成回路，EE-(u,v),TE=TE(u,v)4)一直到TE中加满n-1条边为止。2023-2-1159134521345221345223134522361345223682023-2-11602023-2-1161（2）取最小的边以及判别是否构成回路，利用最小堆 （MinHeap)和并查找集（Disjo

12、intSets)克鲁斯卡尔算法:void Graph:Kruskal(MinSpanTree&T)MSTEdgeNode e;MinHeapH(currentEdges);int NumVertices=VerticesList.Last,u,v;Ufsets F(NumVertices);/建立n个单元素的连通分量 for(u=0;uNumVertices;u+)for(v=u+1;vNumVertices;v+)if(Edgeuv!=MAXINT)e.tail=u;e.head=v;e.cost=Edgeuv;H.insert(e);/建立边的最小堆 int count=1;/生成树边计数

13、 while(countNumVertices)H.RemoveMin(e);u=F.Find(e.tail);v=F.Find(e.head);if(u!=v)F.union(u,v);T.Insert(e);count+;2023-2-1162算法分析：1)建立e条边的最小堆。每插入一条边，执行一次 filterup()算法：log2e 所以，总的建堆时间为O(e*log2e)检测邻接矩阵O(n2)2)构造最小生成树时：e次出堆操作：每一次出堆，执行一次filterdown(),总时间为O(elog2e)2e次find操作：O(e*log2n)n-1次union操作：O(n)所以，总的计算

14、时间为O(e*log2e+e*log2n+n2+n)2023-2-1163 3.Prim算法 设：原图的顶点集合V(有n 个）生成树的顶点集合 U(最后也有n个），一开始为空 TE集合为 步骤：1)U=1任何起始顶点，TE=2)每次生成（选择）一条边。这条边是所有边(u,v)中代 价(权)最小的边，uU,v V-U TE=TE+(u,v);U=U+v 3)当UV 2023-2-1164用一开始的例子：14235665514263562023-2-11651423566551426356123456U V-U5条中找最小1423566551426356132456U V-U8条中找最小14235

15、665514263562023-2-11669条中找最小136245U V-U142356614263568条中找最小136425U V-U1 14235614263562023-2-11675条中找最小13645U V-U42356142351=152023-2-1168具体实现：1)图采用邻接矩阵2)设置了两个辅助数组：改进了实现效率 最小生成树不是唯一的，因为权相等的边不止一条时可任选一条。2023-2-1169Lowcost:存放生成树顶点集合内顶点到生成树外各顶点的边上的 当前最小权值；nearvex:记录生成树顶点集合外各顶点，距离集合内那个顶点最近。书中例子：从顶点0出发初始状态

16、Lowcost:nearvex:0 1 2 3 4 5 60 1 2 3 4 5 60 28 10-1 0 00 0 00如果为-1则表示已加入生成树顶点集合28161214182422101543265012023-2-11701）在Lowcost中选择nearvexi-1,且lowcostI 最小的边,用v标记它。选中的权值最小的边为（nearvexv,v),相应的权值为lowcostv。如在图8.20的例子中第一次选中的v=5;则边（0，5），是选中的权 值最小的边，相应的权值为lowcost5=10。反复做以下工作：2)将nearvexv 改为-1，表示它已加入生成树顶点集合。将边(n

17、earvexv,v,lowcostv)加入生成树的边集合。2023-2-11713）比较。取lowcosti=minlowcosti,Edgevi,即用生成树顶点集 合外各顶点I到刚加入该集合的新顶点v的距离(Edgevi)与原来它 所到生成树顶点集合中顶点的最短距离lowcosti做比较，取距离 近的，作为这些集合外顶点到生成树顶点集合内顶点的最短 距离。4）如果生成树顶点集合中外顶点 i刚加入该集合新顶点v的距离 比原来它到生成树顶点集合中顶点的最短距离还要近，则修改 nearvexi:nearvexi=v.表示生成树外顶点I到生成树的内顶点v 当前距离最短。2023-2-1172-100

18、00-100123456028100123456nearvexlowcost(0,5,10)10151234560UV-U2023-2-11730512346UV-U-10005-10012345602825100123456nearvexlowcost(5,4,25)10542512023-2-11740541236-1034-1-1301234560283222510180123456nearvexlowcost(4,3,22)105UV-U42521222023-2-11750543126-103-1-1-13012345602812222510180123456nearvexlowco

19、st(3,2,12)105UV-U42512232122023-2-11760543226-1-1-1-1-1-1-1012345601612222510140123456nearvexlowcost(2,1,16)UV-U10542502232121162023-2-11770543216-1-1-1-1-1-1-1012345601612222510140123456nearvexlowcost(1,6,14)UV-U10542502232121166142023-2-1178Prim（普里姆）算法void graph:Prim(MinSpanTree&T)int NumVertices=

20、VerticesList.last;float*lowcost=new floatNumVertices;int*nearvex=new intNumVertices;for(int i=1;i NumVertices;i+)lowcosti=Edge0i;nearvexi=0;nearvex0=-1;MSTEdgeNode e;for(int i=1;i NumVertices;i+)float min=MAXINT;int v=0;for(int j=1;j NumVertices;j+)2023-2-1179if(nearvexj!=-1&lowcostjmin)v=j;min=lowc

21、ostj;if(v)e.tail=nearvexv;e.head=v;e.cost=lowcostv;T.Insert(e);nearvexv=-1;for(int j=1;j NumVertices;j+)if(nearvexj!=-1&Edgevjlowcostj)lowcostj=Edgevj;nearvexj=v;2023-2-1180算法结构为：n 求最小的n 修改n所以时间复杂度：O(n2)2023-2-11818.5 最短路径（最短路径（shortest path)三种算法：1.边上权值非负情况的从一个结点到其它各结点的最短路径 （单源最短路径-Dijkstra算法）2.边上权值

22、为任意值的单源最短路径 3.所有顶点之间的最短路径 设G=(V,E)是一个带权图（有向，无向），如果从顶点v到顶点w的一条路径为（v,v1,v2,w)，其路径长度不大于从v到w的所有其它路径的长度，则该路径为从v到w的最短路径。背景：交通网络中，求各城镇间的最短路径。2023-2-11821.含非负权值的单源最短路径（Dijkstra)1)问题04123101003050201060V0 V110V0 V3 V250V0 V330V0 V3 V2 V460如果按距离递增的顺序重新排列一下经过终止 距离V0 V1 10V0 V3 30V0 V3 V2 50V0 V3 V2 V4 600 1 2

23、3 40 10 30 100 0 50 0 10 20 0 60 0012342023-2-1183 2)思想：按最短路径长度递增的次序产生诸最短路径。一开始，在源点到直接有连线的诸顶点的 path中找最小的，去掉该点，然后找从源点到余下点中最短的path(这里可以不是直接连线，可以是经过前面已找到的最短path的顶点）V0SV1V2V3V4V-SV0V1SV2V3V4V-S算法思想：2023-2-1184V0V1 V3SV2V4V-SV0V1 V3V2SV4V-S距离值数组:dist100-10000-2600-1-250 0-3-2300-3300-31000-41000-4600-3-2

24、-4900-3-401234路径path00000320133-1000001234每次放由v0到达该顶点的前一顶点2023-2-1185下面是Dijkstra 算法的实现const int NumVertices=6;class graph private:int EdgeNumVerticesNumVertices;int distNumVertices;int pathNumVertices;int SNumVertices;/求得最短路径的顶点/i加入S为Si=1,/否则为02023-2-1186public:void shortestpath(int,int);int choose(

25、int);void Graph:shortestpath(int n,int v)for(int i=0;in;i+)disti=Edgevi;si=0;if(i!=v&distiMAXNUM)pathi=v;else pathi=-1;sv=1;distv=0;for(i=0;in-1;i+)2023-2-1187 float min=MAXNUM;int u=v;for(int j=0;jn;j+)if(!sj&distjmin)u=j;min=distj;su=1;for(int w=0;wn;w+)if(!sw&EdgeuwMAXNUM&distu+Edgeuwdistw)distw=

26、distu+Edgeuw;pathw=u;算法分析：O(n)nnnO(n2)2023-2-11882.边上权值为任意值的单源最短路径（贝尔曼福特）例子：012-575如果用Dijkstra算法，则结果为v0 v2 5v0v1 7 实际上v0v1 v2 2问题是一旦v2进入了S 集合，就不可修改了。贝儿曼福特提出了一个改进的算法：构造一个最短路径长度数组 dist1u,dist2u,.distn-1u其中，dist1u:是从源点v到终点u的只经过一条边的 的最短路径长度，dist1u=Edgevudist2u:是从源点v最多经过两条边到达终点u 的最短路径长度；2023-2-1189 dist3

27、u：是从源点v最多经过不构成带负长度边回路的三条边 的最短路径长度；012-211不允许带负权值的边组成回路distn-1u：是从源点v最多经过不构成带负长度边回路的n-1条 边的最短路径长度；递推公式：dist1u=Edgevu;distku=mindistk-1 u,mindistk-1j,Edgejuj=0,1,2,n-12023-2-1190书中的例子：-11253064631-255-1-23distk0distk1distk2distk3distk4distk5distk613200060-110-3-2-130-2-150-2330-3-250-3550-30-420-2-1-4

28、50-1-40-5440-3-50-66570-3-5-60-64013500-3-2-1-4450-2-1-4-62023-2-1191void Graph:BellmanFord(int n,int v)for(int i=0;in;i+)disti=Edgevi;if(i!=v&distiMAXNUM)pathi=v;else pathi=-1;for(int k=2;kn;k+)for(int u=0;un;u+)if(u!=v)for(i=0;in;i+)if(Edgeiu0&Edgeiudisti+Edgeiu)distu=disti+Edgeiu;pathu=i;算法分析：三重循

29、环 O(n3)2023-2-1192 3.所有顶点之间的最短路径（floyed)前提：各边权值均大于0的带权有向图。方法：1)把有向边的每一个顶点作为源点，重复执行算法 Dijkstra n次，执行时间为O(n3)2)Floyed方法，算法形式更简单些，但是仍然是O(n3)例子：134255571020 0 5 5 0 20 5 0 7 10 0A=2023-2-1193floyed算法：在矩阵A上作n-1次迭代，设每次迭代结果分别为A(0),A(1),A(2),A(n)A(0)=源矩阵，认为vi-vj的直接弧为它们的min路径A(1)=A(1)i,j=min(A(0)i,j,A(0)i,1+

30、A(0)1,j)此时 A(1)i,j可能已换成vi-v1-vjA(2)=A(2)i,j=min(A(1)i,j,A(1)i,2+A(1)2,j)即考虑经过顶点2，它是 vi-vj,vi-v1-vj,vi-v1-v2-vj,vi-v2-v1-vj,的min者 .A(k)=A(k)i,j=min(A(k-1)i,j,A(k-1)i,k+A(k-1)k,j).2023-2-1194如上例A(2)=0 5 5 0 10 2010 5 0 715 10 20 0A(1)=0 5 5 0 10 20 5 0 7 10 0A(3)=0 10 5 125 0 10 1710 5 0 715 10 20 0A(

31、0)=0 5 5 0 5 0 7 10 02023-2-1195A(4)=0 10 5 125 0 10 1710 5 0 715 10 20 0path(4)=0 3 0 30 0 1 32 0 0 02 0 1 0具体实现时同样有一个路径数组pathij 放入到达j的紧前一个顶点上面path(4)ij 中 path14=3 再看path13=0 机即路径为134 Path24=3 再看path23=1再看path21=0即路径为2134 Path43=1再看path41=2,再看path42=0即路径为42132023-2-1196算法：void Graph:Alllength(int n

32、)for(int i=0;in;i+)for(int j=0;jn;j+)aij=Edgeij;if(ij&aijMAXNUM)pathij=i;else pathij=0;for(int k=0;kn;k+)for(int i=0;in;i+)for(int j=0;jn;j+)if(aik+akjaij aij=aik+akj;pathij=pathkj;三重循环O（n3）2023-2-11978.6 活动网络（活动网络（Activity Network）本节介绍两个算法 用顶点表示活动的网络（AOV网络）用边表示活动的网络（AOE网络）1.用顶点表示活动的网络（拓扑排序topologic

33、al sort)2023-2-11981)例子：假设计算机系的开课情况为：2023-2-1199 这说明要学C3必须要学C1,C2,所以，整个课程间的优先关系可以用一个有向图来表示。C5C6C4C7C9C8C1C3C2一般来讲集合上的偏序关系用符号“”表示。先于2023-2-11100 图中顶点表示课程（活动），有向边（弧）表示先决条件。若课程i是课程j的预修课程，则图中有弧 2)AOV网（网（Activity On Vertex network)用顶点表示活动，用弧表示活动间的优先关系的有向图称为AOV网。直接前驱，直接后继：是网中一条弧，则i是j的 直接前驱，j是i的直接后继。2023-2

34、-11101 前驱，后继：从顶点i顶点j有一条有向路径，则称i是j的前驱，j是i的后继。AOV网中，不应该出现有向环。3）拓扑排序（拓扑排序（topological sort）有向图G=(V,E),V里结点的线性序列（vi1,vi2,vin),如果满足：在G中从结点vi到vj有一条路径，则序列中结点Vi必先于结点vj，称这样的线性序列为一拓扑序列。上例:学生选课有:C1，C2，C3，C4，C5，C6，C8，C9，C7 或 C1，C8，C9，C2，C5，C3，C4，C7,C6拓扑序列不是唯一的2023-2-11102 不是任何有向图的结点都可以排成拓扑序列，有环图是不能排的。v1v2v3 算法思

35、想：(1)从图中选择一个入度为0的结点输出之。（如果一个图中，同时存在多个入度为0的结点，则随便 输出那一个结点）(2)从图中删掉此结点及其所有的出边。(3)反复执行以上步骤：a）直到所有结点都输出了，则算法结束b）如果图中还有结点，但入度不为0，则 说明有环路2023-2-11103具体实现算法：AOV网用邻接边表来实现;还利用了一个小小的实现技巧，数组count存放各顶点的入度;并且为了避免每次从头到尾查找入度为0的顶点，建立入度为0的 顶点栈，栈顶指针为top，初始化时为1，顶点从0开始编号C4C5C3C6C8C7C0C2C12023-2-11104countdate adjdest l

36、inktop023456781nodetable2023-2-11105AOV网的声明class Graph friend class vertex;friend class Edge;private:vertex *nodeTable;int*count;int n;public:Graph(const int vertices=0):n(vertices)NodeTable=new vertex n;/建立顶点表数组 count=new intn;/建立入度数组 ;void topologicalorder();2023-2-11106void Graph:Topologicalsort(

37、)int top=-1;for(int i=0;in;i+)if(counti=0)counti=top;top=i;for(int i=0;in;i+)if(top=-1)cout“Network has a cycle”endl;return;else int j=top;top=counttop;coutjendl;Edge *l=NodeTablej.adj;whilewhile(l)intint k=l.dest;ifif(-countk=0)countk=top;top=k;l=l-link;2023-2-11107算法分析：n个顶点，e条边 建立链式栈O（n）每个结点输出一次，每

38、条边被检查一次O（ne）所以，O（nne）O(n+e)2023-2-111082.用边表示活动的网络（AOE网络-Activity On Edge Network）又称为事件顶点网络 1)顶点：表示事件（event）事件状态。表示它的入边代表的活动已完成，它的出 边代表的活动可以开始，如下图中v0表示 整个工程开始，v4表示a4，a5活动已完成 a7，a8活动可开始。有向边：表示活动。边上的权完成一项活动需要的时间2023-2-11109025361748a1=6a4=1a7=9a10=2a11=4a8=7a9=4a6=2a3=5a2=4a5=1开始（soure）结束(汇点sink)2023-

39、2-11110图中有11项活动a1，a2，a11 ；9个事件（v0，v1，v8）v0表示整个工程开始，v8表示整个工程结束，边上的权表示活动完成所需的天数（这些天数仅仅是估计值），假设图为无环有向图。*有唯一的入度为0的开始结点 唯一的出度为0的完成结点与AOV网不同2)关键路径（critical path）目的：利用事件顶点网络，研究完成整个工程需要多少时间 加快那些活动的速度后，可是整个工程提前完成 关键路径：具有从开始顶点(源点）完成顶点（汇点）的 最长长度的路径2023-2-11111关键路径:a1，a4，a7，a10或 a1，a4，a8，a11，这条路径所有的持续时间之和是18也只有

40、在这最长路径上，找到关键活动，适当调度，加快完成其速度，则整个工程有希望完成或提前完成。想一想要加快那些活动才能提前？a1或a42023-2-111123)找关键活动的算法：定义几个量 对事件而言:Vei表示事件Vi的可能最早发生时间。定义为从源点V0 Vi的最长路径长度 如Ve4=7天 Vli表示事件Vi的允许的最晚发生时间。是在保证汇点Vn1在Ven-1时刻完成的前提下，事件Vi允许发生的最晚时间 Ven-1 Vi Vn1 的最长路径长度。2023-2-11113339234512233442Vj最早发生时间是12最迟发生时间是12最早发生时间是7最迟发生时间是13（19）2023-2-1

41、1114对活动而言：ek表示活动ak=的可能的最早开始时间 即等于事件Vi的可能最早发生时间。ek=Vei lk表示活动ak=的允许的最迟开始时间 lkVlj-dur()dur()完成ak所需的时间 lk-ek表示活动ak的最早可能开始时间和最迟 允许开始时间的时间余量。也称为松弛时间 （slack time）lk=ek表示活动ak是没有时间余量的关键活动如例子中：a8的最早可能开始时间e8=Ve4=7 最迟允许开始时间l8=Vl7-dur()=14-7=72023-2-11115 a8是关键路径上的关键活动 a9的最早可能开始时间e9=Ve5=7最迟允许开始时间l9=Vl7-dur()=14

42、-4=10 l9-e9=3,该活动的时间余量为3,它不是关键活动 为了求关键活动：求各个活动的ek与lk,为了求ek,lk必须先求各事件的Vei与Vli2023-2-11116例如图中 Ve4为：Ve1+的权1617 Ve2+的权1415取maxjjji 步骤：求各事件的可能最早发生时间 从Ve0=0开始，向前推进求其它事件的Ve Vei=maxVej+dur(),S2,i=1,2,n1 j S2是所有指向顶点Vi的有向边的集合2023-2-11117求各事件的允许最晚发生时间从Vln-1=Ven-1开始，反向递推Vli=minVlj-dur(),S1,i=n-2,n-3,0 j S1是所有从

43、顶点Vi出发的有向边的集合jjjiVln-1图中Vl4为：Vl6-的权91697 Vl7-的权71477min2023-2-11118以上的计算必须在拓扑有序及逆拓扑有序的前提下进行求Vei必须使Vi的所有前驱结点的Ve都求得求Vli必须使Vi的所有后继结点的最晚发生时间Vl 都求得求每条边（活动）ak=的ek,lk ek=Vei;lk=Vlj-dur(),k=1,2,e如果ek=lk 则ak是关键活动AOE网用邻接表来表示，并且假设顶点序列已按拓扑有序与逆拓扑有序排好如上例:2023-2-111191641524169748284773524逆拓扑次序拓扑次序count adjdest du

44、r linkNodeTable2023-2-11120537204816a16a41a24a51a35a62a94a87a114a79a1022023-2-11121void Graph:CriticalPath()int i,j;int p,k;float e,l;float*Ve=new float n;float*Vl=new floatn;for(i=0;in;i+)Vei=0;for(i=0;in;i+)Edge *p=NodeTablei.adj;while(p!=NULL)k=p-dest;if(Vei+p-costVek)Vek=Vei+p-cost;p=p-link;for(

45、i=0;idest;if(Vlk-p-costcost;p=p-link;for(i=0;idest;e=Vei;l=Vlk-p-cost;if(l=e)cout“i“”,”k”“is critical Activity”link;2023-2-11123算法分析：拓扑排序求Vei 逆拓扑排序求Vli 求各活动ek和lkO(n+e)O(e)O(n+e)2023-2-11124第第8章章 图的小结图的小结1图的基本概念2图的存储表示 邻接矩阵，邻接表3图的若干算法以及时间复杂性分析 1 图的遍历 深度优先搜索 广度优先搜索 2 最小生成树Kruscal,Prim 3 最短路径 Dijkstra，BellmanFord，floyed 4 活动网络 AOV,AOE2023-2-11125