c数据结构chapt8图课件

1、第八章 图 图的定义 图的存储结构 图的遍历 图的应用第1页，共82页。8.1 图的定义和术语1. 图 有向图（Digragh） 无向图（Undigraph）第2页，共82页。8.1 图的定义和术语有向图（Digragh） G=（V，A） 其中，V为顶点的有穷非空集合 A为顶点之间的关系集合 G1=（V，A） V=v1, v2, v3, v4A=, , , 其中表示从x到y的一条弧（arc），A为弧集合，x为弧尾（tail），y为弧头（head)G1第3页，共82页。8.1 图的定义和术语无向图（Undigraph） G=(V,E) 其中，V同有向图，E为顶点之间的关系集合， E为边集合G2=

2、（V，A） V=v1, v2, v3, v4, v5E=(v1, v2), (v1, v4), (v2, v3), (v3, v4), (v2,v5), (v3,v5)其中，(x, y)表示x与y之间的一条连线，称为边（edge）G2 第4页，共82页。8.1 图的定义和术语设n为顶点数，e为边或弧的条数 对无向图有：0=e=n(n-1)/2 有向图有：0=e=n(n-1)证明：每个顶点至多有n-1条边与其它的n-1个顶点相 连，则n个顶点至多有n(n-1)条边。但每条边连 接2个顶点，故最多为n(n-1)/2第5页，共82页。8.1 图的定义和术语2. 完全图 边达到最大的图 无向完全图：边

3、数为n(n-1)/2的无向图 有向完全图：弧数为n(n-1)的有向图权：与图的边或弧相关的数网：边或弧上带有权值的图G2 第6页，共82页。8.1 图的定义和术语3. 顶点的度 TD（V） 无向图：为依附于顶点V的边数 有向图：等于以顶点V为弧头的弧数（称为V的 入度，记 为ID（V）与以顶点V为弧尾的弧数（称为V 的出度，记为OD（V）之和。即： TD（V）=ID（V）+OD（V） 无向图 n e= 1/2（TD(vi)） i=1结论： 有向图 n n e= ID(vi)=OD(vi) i=1 i=1无向图的度数为依附于顶点v的边数；有向图的度数等于以顶点v 为弧头的弧数与以顶点v为弧尾的弧

4、数之和G1G2 第7页，共82页。8.1 图的定义和术语4. 路径 无向图：顶点v到v的路径是一个顶点序列（v=vi0, vi1, , vim=v） 其中，（vij-1,vij ）E, 1=j=m 有向图： 顶点v 到v的路径是有向的顶点序列（v=vi0, vi1, , vim=v） 其中，（vij-1,vij ）A, 1=j=m几个概念：路径长度：路径上边或弧的数目回路或环：首尾顶点相同的路径，称为回路或环。即： （v=vi0, vi1, , vim=v=v）简单路径：路径中不含相同顶点的路径简单回路：除首尾顶点外，路径中不含相同顶点的回路BADC82375第8页，共82页。5. 连通 顶点

5、连通：若顶点v到顶点v有路径，则称顶点v与v是连通的 连 通 图 ：包括无向连通图和有向连通图 无向图：若图中任意两个顶点vi,vj都是连通的，则称该图 是连通图(vivj) 有向图：若图中任意两个顶点vi,vj，都存在从vi到vj和从 vj到vi的路径，则称该有向图为强连通图(vivj) 连通分量： 无向图：无向图中极大连通子图，称为连通分量 有向图：有向图中极大强连通子图，称为强连通分量BEADCFBAFEDCV2V4V3V1第9页，共82页。8.1 图的定义和术语5. 连通连通分量： G1有两个强连通分量G1第10页，共82页。8.1 图的定义和术语6. 生成树 定义：设无向图G是含有n

6、个顶点的连通图， 则图G的生成树是 含有n个顶点，且只有n-1条边的连通子图 三要素： n个顶点 n-1条边 连通 极小连通子图，若再加一条边，必构成环生成树n-1条边第11页，共82页。8.2 图的存储结构图有数组、邻接表、邻接多重表和十字链表等表示方法一、数组表示法（邻接矩阵）设图G=（V，E）有n个顶点，则G的邻接矩阵定义为n阶方阵A。其中：Ai，j= 1 若（ vi，vj）或 E，ij 0 其它例如：G1的邻接矩阵 0 1 1 0 A1 0 0 0 0 0 0 0 1 1 0 0 0G2 0 1 0 1 0 A2 1 0 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1

7、0 0无向图的邻接矩阵为对称矩阵G1第12页，共82页。8.2 图的存储结构特点：判定两个顶点Vi与Vj是否关联,只需判Ai,j是否为1 顶点的度容易求得: 有向图中： TD(Vi)=OD(Vi)+ID(Vi) n n = Ai,j+Aj,i j=1 j=1 n n 无向图中：TD(Vi)=Ai,j=Aj,i j=1 j=1 即顶点Vi的度等于邻接矩阵中第i行（或第i列）的元素之和（非0元素个数之和）。即顶点Vi的出度为邻接矩阵中第i行元素之和 顶点Vi的入度为邻接矩阵中第i列元素之和第13页，共82页。8.2 图的存储结构网的邻接矩阵 定义为： Ai，j= Wij，若（Vi，Vj）或E ，其

8、它V1V2V3V435214 3 2 4 A 5 1如图：第14页，共82页。8.2 图的存储结构二、邻接表（adjacency list）1. 无向图邻接表对图中每个顶点Vi建立一个单链表，链表中的结点表示依附于顶点Vi的边，每个链表结点为两个域：adjvexnextarc其中：邻接点域（adjvex）记载与顶点Vi邻接的顶点信息； 链域（nextarc）指向下一个与顶点Vi邻接的邻接的链表p结点每个链表附设一个头结点，头结点结构为：vexdatafirstarc其中：vexdata存放顶点信息（姓名、编号等）； fristarc指向链表的第一个结点。第15页，共82页。8.2 图的存储结构

9、二、邻接表（adjacency list）如图G2的邻接表为：2534154353341221201234特点：设无向图中顶点数为n，边数为e， 则它的邻接表需要n个头结点和2e个表结点。 顶点Vi的度 TD（Vi）=链表i中的表结点数。G2 第16页，共82页。8.2 图的存储结构二、邻接表（adjacency list）2. 有向图邻接表与无向图的邻接表结构一样。只是在第i条链表上的结点是以Vi为弧尾的各个弧头顶点234143120123特点：1. n个顶点，e条弧的有向图，需n个表头结点，e 个表结点 2. 第i条链表上的结点数，为Vi的出度 （求顶点的出度易，求入度难）如图G1的邻接表

10、为：G1第17页，共82页。8.2 图的存储结构二、邻接表（adjacency list）3. 有向图逆邻接表与无向图的邻接表结构一样。只是在第i条链表上的结点是以Vi为弧头的各个弧尾顶点123411430123此时，第i条链表上的结点数，为Vi的入度如图G1的逆邻接表为：G1第18页，共82页。8.2 图的存储结构三、十字链表（orthogonal list）十字链表是将有向图的邻接表和逆邻接表结合起来的一种有向图链式存储结构1. 结点结构有向图的每一条弧有一个弧结点，每一个顶点必有一个顶点结点，其结构为：tailvexheadvexhlinktlinkdatafirstinfirstout

11、弧结点顶点结点tailvex: 指示该弧的弧尾顶点；headvex: 指示该弧的弧头顶点；hlink: 指向弧头相同的下一条弧；tlink: 指向弧尾相同的下一条弧data: 存放顶点的有关信息 （如顶点的名称，或位置）firstin: 指向以该顶点为弧头的 第一个弧结点；firstout: 指向以该顶点为弧尾 的第一个弧结点。第19页，共82页。8.2 图的存储结构2. 整体结构 通过hlink将弧头相同的弧连在一个链表上； 通过tlink将弧尾相同的弧连在一个链表上 而hlink链和tlink链的头结点就是顶点结点3. 例 G1的十字链表为：123412134134e13e12e34e41

12、G1第20页，共82页。8.2 图的存储结构4. 特点： 顶点结点数=顶点数 弧结点数=弧的条数 求入度：从顶点Vi的firstin出发，沿着弧结点中的hlink所经过的弧结点数。 求出度：从顶点Vi的firstout出发，沿着弧结点中的tlink所经过的弧结点数。第21页，共82页。8.2 图的存储结构四、邻接多重表邻接多重表是无向图的另一种链式存储结构。图的每一条边有一个边结点，边结点的结构为：ivexilinkjvexjlink每一个顶点有一个顶点结点，顶点结点结构为：datafirstedge其中：ivex 和jvex为该边所依附的两个顶点。 ilink指向下一条依附于顶点ivex的边

13、。 jlink指向下一条依附于顶点jvex 的边。 data存放顶点的信息。 firstedge指向第一条依附于该顶点的边结点。第22页，共82页。8.2 图的存储结构四、邻接多重表如图G2的邻接多重表:G2 25341123252543435第23页，共82页。8.2 图的存储结构四、邻接多重表如图G2的邻接多重表:特点：顶点结点数为n，边结点数为e； 对需要得到边的两个顶点的一类操作很方便 （如删除一条边，判一条边是否已访问）。G2 25341123252543435第24页，共82页。8.3 图的遍历从图中某个顶点出发，沿路径使图中每个顶点被访问且仅被访问一次的过程，称为遍历图。 两种常

14、用遍历图的方法 深度优先搜索（DFS）广度优先搜索(BFS)第25页，共82页。8.3 图的遍历一、深度优先搜索（depth-first-search)1. 深度优先搜索法遍历图的过程为：访问指定的某顶点V，将V作为当前顶点将该顶点作为当前顶点，访问当前顶点的下一未被访问过的邻接点重复2，直到当前顶点的所有邻接点都被访问点。沿搜索路径回退，退到尚有邻接点未被访问过的某结点，将该结点作为当前结点，重复以上步骤，直到所有顶点被访问过的为止第26页，共82页。8.3 图的遍历一、深度优先搜索（depth-first-search)如图G4：V1V2V3V4V5V6V7V8深到底回退深到底V1V2V4

15、V8V5（V2V8均已访问）深到底V3V6V7回退访问第27页，共82页。8.3 图的遍历一、深度优先搜索（depth-first-search)2. 深度优先搜索递归过程：几点说明： visited1.n是一个辅助数组，记载顶点是否被访问过visitedV=true, 已访问过false, 未访问过（初值） FIRSTADJvex(g,V)和NEXTADJvex(g,V,w）函数的实现与图的 具体存储结构有关第28页，共82页。8.3 图的遍历一、深度优先搜索（depth-first-search)2. 深度优先搜索递归过程：VOID traver(Graph g, Status (*vis

16、it) (int v ) VisitFunc=visit ; FOR (V=0 ; vG.vexnum ; +v ) visitedV=false; /作未访问标记 FOR (V=0 ; vadjvex) Void NEXTADJ( graph g , int v , int w) /找V 的w之后的下一邻接点,不存在返回0 p=adjlistv.firstarc; WHILE (p AND p-adjvex!=w ) p= p-nextarc; /将移动指针定位到w IF (!p | !p-nextarc) RETURN(0) ELSE RETURN(p-nextarc-adjvex) 第3

17、0页，共82页。8.3 图的遍历2. 深度优先搜索递归过程：VOID traver(Graph g, Boolean visitedvtxptr) FOR (V=0; V g.vexmum ; +V ) visitedV=false; FOR (V=0; Vg.vexnum ; +V) IF (! visitedV ) dfs(g,V) /dfs是以V 为出发点，遍历一个连通分量 VOID dfs(Graph g , vtxptr V ) visit(V); visitedV=true; w=FIRSTADJvex(g,V); /找V 的第一个邻接点 WHILE (w ) IF (! visi

18、tedw) dfs(g,w); w=NEXTADJvex(g,V,w) /找V 的w之后的下一邻接点 思考：traver调用 dfs的次数由什么决定？图若采用邻接矩阵存储,编写相应的FIRSTADJvex(g,V)和NEXTADJvex(g,V,w) 第31页，共82页。8.3 图的遍历二、广度优先搜索（breadth-first-search) 首先访问指定顶点v0，将v0作为当前顶点; 访问当前顶点的所有未访问过的邻接点， 并依次将访问的这些邻接点作为当前顶点; 重复2， 直到所有顶点被访问为止。对右图广度优先搜索，访问顶点序列为： V1 V2 V3 V4 V5 V6 V7 V8V1V2V

19、3V4V5V6V7V8第32页，共82页。8.3 图的遍历广度优先搜索算法：VOID bfs(graph g, status (*visit)(int v) for (v=0;vg.vexnum; +v) visitedv=false ; INIQUEUE(Q); for (v=0; vg.vexnum; +v) if (!visitedv) /v未访问 visitedv=true ; visite(v) ; ENQUEUE(Q,V); /找与v邻接的第一个顶点,不存在返回0 WHILE (!QUEUEEMPTY (Q) DEQUEUE(Q,U) ; /队头元素出队并置为u FOR (W=FI

20、RSTADJVEX(g,U);W ;W=NEXTADJVEX(G,U,W) IF (!visitedw) /w为u的尚为访问的邻接点 visitedw=true; visit(w); ENQUEWE(Q,w)； /if /while /找V 的w之后的下一邻接点 /if /bfs第33页，共82页。8.4 最小生成树 一、最小生成树概念1. 设无向连通图G=（V，E）， 其子图G=（V，T）满足： V(G)=V(G) n个顶点 G是连通的 G中无回路则G是G的生成树第34页，共82页。8.4 最小生成树 具有n个顶点的无向连通图G 其任一生成G恰好含n-1条边 生成树不一定唯一，如4个顶点选择

21、3条边有如下5种形状(54= 20种):其中16种为生成树,（保证了连通）第35页，共82页。生成树代价对图中每条边赋于一个权值（代价），则构成一个网，网的生成树G=(V，T)的代价是T中各边的权值之和，最小生成树就是网上所有可能的生成树中，代价最小的一类生成树。最小生成树也不一定唯一。8.4 最小生成树第36页，共82页。V1V2V3V4V5V6V7V8思考：要求每两个城市（顶点）间都有路径V1V2V3V4V6V8V7V5V1V8V5V2V7V6V4V3第37页，共82页。 最小生成树的实用例子很多例1：N台计算机之间建立通讯网顶点表示computer边表示通讯线权值表示通讯线的代价（通讯线

22、长度，computer间距离等）要求： n台计算机中的任何两台能通过网进行通讯； 使总的代价最小。-求最小生成树T8.4 最小生成树第38页，共82页。 最小生成树的实用例子例2：邮递员送信线路T顶点表示投递点边表示街道权值表示街道的长度要求： 完成n个投递点的投递； 使总路径长度最短, 即求最小生成树T8.4 最小生成树第39页，共82页。二、最小生成树性质MST设N=（V，E）是一个连通网，U是顶点集V的一个非空子集。若（u，v）是一条具有最小权值的边，其中uU,vV-U,即（u，v）=Mincost(x,y)|xU,yV-U则必存在一棵包含边（u，v）的最小生成树。uv-uuvuv含义：

23、将顶点分为两个不相交的集合U和V-U，若边（u，v）是连接这两个顶点集的最小权值边，则边（u，v）必然是某最小生成树的边。 第40页，共82页。三、普里姆（Prim）最小生成树算法设 N=（V，E）是一个连通网，V=1，2，n是N的顶点集合，辅助集合U，初值为Uo，用来存放当前所得到的最小生成树的顶点；辅助集合TE，初值为，用来存放当前所得到的最小生成树的边。第41页，共82页。Prim算法步骤1. TE=,U=u02. 当UV，重复下列步骤：(1)选取（u0,v0)=mincost(u,v)|uU,vV-U，保证不形成回路(2)TE=TE+（u0,v0), 边（u0,v0)并入TE(3)U=

24、U+V0，顶点V0 并入U初始化： 5213466556 1第1步：614第2步：6142第3步：56142第4步：23 5614第5步：特点: 以连通为主选代价最小的邻接边第42页，共82页。Prim算法实现:void minispantree_PRIM(mgraph G. vextextype u) / 从u出发构造网 gn的最小生成树 k=locatevex (G,u) ; FOR (j=0;jG.vexnum; +j) IF ( j != k) closedgej=u , G, arcskj.adj ; closedgek .lowcost=0; / 助数组初始化 FOR ( i=1

25、; I0) printf(closedgek.adjvex,G.vexk); /输出生成树的边 closedgek.lowcost=0; /顶点k并入U FOR (j=0 ; jG.vexnum ; +j ) IF ( G.arcs kj.adj closedgej.lowcost ) closedgej = G.vexsk,G.arcskj.adj ; /该图的邻接矩阵 /新顶点并入U后，重选最小代价边 第43页，共82页。算法minispantree_PRIM的几点说明:1. g为 网的邻接矩阵 即 gi, j=w ij 或 为无穷大2. 辅助数组closedge1.n 有两个分量: cl

26、osedgek.vex存放边(k, j)依附的另一顶点j( jU) closedgek.lowcost存放边(k, j)的权值，当值为0时，表示顶点k已加入到集合U中。 区别顶点 U或V-U，是根据， .lowcost=0 U .lowcost0 V-U closedgek.vex U 而 k V-U第44页，共82页。算法minispantree_PRIM的几点说明:3. Int minimum(closedge) min:=; h:=1; FOR (k=1 , kG. vtxnum ; +k) IF (closedgek.lowcost )&( closedgek.lowcostmin)

27、min=closedgek.lowcost; h=k RETURN h ; /minimum 第45页，共82页。 例子： 5213466556 第46页，共82页。四、克鲁斯卡尔（Kruskal）最小生成树算法Kruskal 算法是逐步给生成树T中添加不和T中的边构成回路的当前最小代价边。特点: 以最小代价边主。设N=（V，E）是个连通网, 算法步骤为：1. 置生成树T的初始状态为T=（V，）2. 当T中边数n-1时, 重复下列步骤: 从E中选取代价最小的边（v, u）, 并删除之; 若（v, u）依附的顶点v和u落在T中不同的连同分量上，则将边（v, u）并入到T的边集中；否则，舍去该边，

28、选择下一条代价最小的边.第47页，共82页。四、克鲁斯卡尔（Kruskal）最小生成树算法步骤 (v, u) E T 1 (1, 3)0 523466556 53466556 21第48页，共82页。四、克鲁斯卡尔（Kruskal）最小生成树算法 53466556 步骤 (v, u) E T3 (2, 5)2 (4, 6) 5466556 第49页，共82页。四、克鲁斯卡尔（Kruskal）最小生成树算法步骤 (v, u) E T5 (1, 4)4 (3, 6) 566556 66556 第50页，共82页。四、克鲁斯卡尔（Kruskal）最小生成树算法步骤 (v, u) E T6 (2, 3

29、) 6656 边数=n-1=5代价=(1+2+3+4+5)=15 12345第51页，共82页。思考：已知世界大城市：北京（B）,纽约（N），巴黎（P），伦敦（L），东京（T），墨西哥（M）试确定如下表的交通网中的最小生成树BNPLTMB109828121124N109585510832P825839792L815539589T211089795113M124329289113第52页，共82页。NPBLMT583558997951131243221821098192NPBLMT3第53页，共82页。思考：什么样的图其最小生成树是惟一的？Prim Kruskal 分别适合于哪类图？各条边权值不

30、相同的有向图，其最小生成树是惟一的Prim适合顶点比较少的图kruskal 适合边比较少的图第54页，共82页。思考：下图是各个城市间的交通情况图，如何能造成破坏性AILBJFCMDGHKE第55页，共82页。关节点和重连通分量 关节点：假若在删去顶点v 以及和v相关联的各边之后，将图的一个连通分量分割成两个或两个以上的连通分量，则称顶点v为该图的一个关节点(articulation point) 。重连通图：一个没有关节点的连通图称为重连通图(biconnected graph)第56页，共82页。AILBJFCMDGHKE关节点ABG第57页，共82页。8.5 拓扑排序(topologic

31、al sort) 拓扑排序是一种对非线性结构的有向图进行线性化的重要手段一、AOV网(Activity on vertex network) 一个有向图可用来表示一个施工流程图、一个产品生产流程图、或一个程序框图等。如图：a1a5a4a6a2a3a8a7a9课程安排PascalDSCompilerOSC施工从活动 a1、 a2开始，到达活动 a8和 a9时，整个施工结束。有向图中，顶点表示活动，弧表示活动 ai优先于活动 aj ，称这类有向图为顶点表示活动的网（AOV网）。第58页，共82页。8.5 拓扑排序(topological sort)AOV网可解决如下两个问题：（1）判定工程的可行性

32、。显然，有回路，整个工程就无法结束（2）确定各项活动在整个工程执行中的先后顺序。 称这种先后顺序为拓扑有序序列。如图有如下拓扑有序序列： a1 a2 a3a4 a6 a5 a7 a8 a9 a2 a6 a1 a3 a4 a5 a7 a9 a8a1a5a4a6a2a3a8a7a9第59页，共82页。8.5 拓扑排序(topological sort)拓扑排序：满足以下性质的线性序列：在AOV网中，若顶点i 优先于顶点j ，则在线性序列中顶点i仍然优先于顶点j； 对于网中原来没有优先关系的顶点与顶点 ，在线性序列中也建立一个先后关系，或者顶点i优先于顶点j ，或者顶点j 优先于i。 第60页，共8

33、2页。二、拓扑排序算法1. 算法步骤(1) 在AOV网中，选取一个没有前驱的顶点输出；(2) 删除该顶点和所有以它为弧尾的弧；(3) 重复以上两步，直到AOV网中全部顶点都已输出（得到拓扑有序序列）或者，图中再无没有前驱的顶点（AOV网中有环）第61页，共82页。二、拓扑排序算法如何实现算法中的(1)和(2)？对于(1)，没有前驱的顶点即入度为0的顶点；对于(2)，删除以它为弧尾的所有弧，即让该顶点的所有直接后继的入度减1。由此分析知：拓扑排序算法的实现与顶点的入度有密切关系，因此，在选取存储结构时，应考虑： 能容易得到各顶点的入度； 有利于寻找任一顶点的所有直接后继。为此，采用邻接表作为AO

34、V网的存储结构，并在头结点中增加一个存放顶点入度的域（indegree） 第62页，共82页。V1V4V6V2V3V5V1V2V3V4V5V602123043252554第63页，共82页。V1V4V6V2V3V5V1V2V3V4V5V602123043252554步骤 0 1 2 3 4 5 6输出 V6 V1 V3 V2 V4 V5 m 0 1 2 3 4 5 6=n 栈 TOP611344245入度域021230120120010020000010000010000000第64页，共82页。二、拓扑排序算法Status toposort(algraph G)/G采用邻接链表存储。若无回路

35、输出拓扑序列 finddegree(G,indegree ); /对各顶点求入度，indegree0.vernum-1 INITstack (s); FOR (i=0 ; Inextarc ) k=p-adjvex ; /下面对I号顶点的每个邻接点的入度-1 if (!(-indegreek) PUSH(top, k); /入度减为0的顶点入栈 /for /while IF (count G.vexnum) RETURN error ; /有回路 ELSE RETURN ok; / toposort第65页，共82页。8.6 关键路径一、AOE网（activity on edge） 若有向图中

36、，顶点表示事件，弧表示活动，弧上的权表示完成该活动所需的时间，则称这类有向图为边表示活动的网（AOE网） AOE网中仅有一个入度为0的事件，称为源点，它表示工程的开始；网中也仅有一个出度为0的事件，称为汇点，它表示工程的结束。 每一事件V表示以它为弧头的所有活动已经完成，同时，也表示以它为弧尾的所有活动可以开始。第66页，共82页。8.6 关键路径AOE网可解决如下问题：估算工程的最短工期（从源点到 汇点至少需要多少时间）找出哪些活动是影响整个工程进展的关键a1=6a4=1a2=4a5=1有4个事件：V1， V2， V3， V5 V1为源点，V5为汇点有4个活动：a1, a2, a4, a5

37、V3表示：a2已完成，a5可以开始第67页，共82页。8.6 关键路径二、几个术语路径长度：路径上各活动持续时间的总和 （即：路径上所有弧的权值之和）关键路径：从源点到汇点之间路径长度最长的路径， （不一定唯一）事件V i的最早发生时间ve(i)：从源点到V i的最长路径长度活动 ai的最早开始时间e(i)：等于该活动的弧尾事件V j的最早发生时间 即若表示活动ai ，则有e(i)=ve(j)vjvkaivr第68页，共82页。8.6 关键路径事件 vk 的最迟发生时间 vl(k)：是在不推迟整个工期的前提下，该事件最迟必须发生的时间活动ai的最迟开始时间l(i)：是该活动的弧头事件的最迟发生

38、时间与该活动的持续时间之差， 即l(i)=vl(k)- ai 的持续时间关键活动：l(i)=e(i)的活动由此可见：在AOE网中找关键活动问题可转化为求 l(i)=e(i)，而e(i)=ve(j) l(i)=vl(k) - ai 的持续时间因此，需先求出事件的最早、最迟发生时间v2v3v1v4v5224563第69页，共82页。8.6 关键路径三、关键路径算法思想1. 从ve(1)=0 开始利用下面递推公式，计算出各事件的最早发生时间ve(j)=Maxve(i)+dut()， j=2, n， T其中：T是所有以j为头的弧集合，dut()表示活动的持续时间前例中，ve(5)=Maxve(2)+d

39、ut()， ve(3)+dut() =Max6+1,4+1=7a1=6a4=1a2=4a5=1第70页，共82页。2. 从vl(n)=ve(n)开始，利用下面递推公式，计算出各时间的最迟发生时间：vl(i)=Minvl(j)-dut() i=n-1 , 2, 1 , S其中：S是所有以i为尾的弧集合8.6 关键路径a1=6a4=1a2=4a5=1前例中，vl(5)=ve(5)=7 vl(2)=vl(5)-1=6 vl(3)=vl(5)-1=6vl(1)=Minvl(2)-dut()，vl(3)-dut() =Min6-6,6-4=0第71页，共82页。8.6 关键路径3. 设活动ai由弧表示，

40、其持续时间为dut()，则利用下面公式，计算出各活动的最早、最迟开始时间：e(i)=ve(j)l(i)=vl(k)-dut()4. 找出e(i)=l(i)的活动，即为关键活动，诸关键活动组成的从源点到汇点的路径即为关键路径。第72页，共82页。3125478119106A1=3A3=2A4=1A2=4A5=3A8=8A7=6A11=7A15=6A14=1A10=2A6=5A12=4A13=10A9=4Ve1=0Vek=maxvej+Vln=venVlk=minvlj-ei=vekli=vlj-第73页，共82页。 ve (1)=0 ve (2)=3 ve (3)=4 ve (4)=ve(2)+

41、2=5 ve (5)=maxve(2)+1,ve(3)+3=7 ve (6)=ve(3)+5=9 ve (7)=maxve(4)+6,ve(5)+8=15 ve (8)=ve(5)+4=11 ve (9)=maxve(8)+10,ve(6)+2=21 ve (10)=maxve(8)+4,ve(9)+1=22 ve (11)=maxve(7)+7,ve(10)+6=28 vl (11)= ve (11)=28 vl (10)= vl (11)-6=22 vl (9)= vl (10)-1=21 vl (8)=min vl (10)-4, vl (9)-10=11 vl (7)= vl (11)

42、-7=21 vl (6)= vl (9)-2=19 vl (5)=min vl (7)-8,vl (8)-4=7 vl (4)= vl (7)-6=15 vl (3)=min vl (5)-3, vl (6)-5=4 vl (2)=min vl (4)-2, vl (5)-1=6 vl (1)=minvl (2)-3, vl (3)-4=0 活动a1 e (1)=ve (1)=0 l (1)=vl (2) -3 =3 活动a2 e (2)=ve (1)=0 l (2)=vl (3) - 4=0 活动a3 e (3)=ve (2)=3 l (3)=vl (4) - 2=13 活动a4 e (4)

43、=ve (2)=3 l (4)=vl (5) - 1=6 活动a5 e (5)=ve (3)=4 l (5)=vl (5) - 3=4 活动a6 e (6)=ve (3)=4 l (6)=vl (6) - 5=14 活动a7 e (7)=ve (4)=5 l (7)=vl (7) - 6=15 活动a8 e (8)=ve (5)=7 l (8)=vl (7) - 8=13 活动a9 e (9)=ve (5)=7 l (9)=vl (8) - 4=7 活动a10 e (10)=ve (6)=9 l (10)=vl (9) - 2=19 活动a11 e (11)=ve (7)=15 l (11)=

44、vl (11) - 7=21 活动a12 e (12)=ve (8)=11 l (12)=vl (10) - 4=18 活动a13 e (13)=ve (8)=11 l (13)=vl (9) - 10=11 活动a14 e (14)=ve (9)=21 l (14)=vl (10) -1=21 活动a15 e (15)=ve (10)=22 l (15)=vl (11) -6 =223125478119106A1=3A3=2A4=1A2=4A5=3A8=8A7=6A11=7A15=6A14=1A10=2A6=5A12=4A13=10A9=4第74页，共82页。一个活动的最迟开始实践l(i)和其最早开始时间e(i)的差值l(i) e(i)是该活动完成的时间余额，是在不增加完成整个工程所需的总时间的情况下，活动ai可以拖