数据结构(第八章图)DataStructures胡学钢张晶计算机与课件

1、数 据 结 构（第八章 图） Data Structures胡学钢 张 晶计算机与信息学院 2009年2月1第八章 图 (Graph) 第八章 图（Graph) 8.1 基本概念和运算 8.2 图的存储 8.3 图的遍历 8.4 最小生成树 8.5 有向无环图的应用 8.6 最短路径2 8.1 基本概念和运算 图 由顶点集V和连接顶点的弧集E所组成的结构， 记作 G = ( V, E )。 其中弧的形式为， 表示从顶点Vi到Vj之间有一条弧，图形表示为： Vi Vj -有向图例：如右图中的G1就是一个有向图： 其中： 顶点集合 V=1，2，3，4 弧集 E= , , , , 2134图G1 有

2、向图示例3 8.1 基本概念和运算 如果顶点间的关系是相互的，即弧的两端没有方向，则图为无向图。其中的弧称为边。边的形式为(Vi,Vj)，图形表示为： Vi Vj例：如右图中的G2就是一个无向图： 其中： 顶点集合 V=1，2，3，4 边集 E= （1,2）,（1,3）,（1,4） （2,4）,（3,4） 2134图G2 无向图示例48.1 基本概念和运算 若G中每条边（弧）对应一个数值表示关系的程度，则称图G为网络。 例： 图G3 就是一个网络 对图G = ( V, E )，若存在G1=(V1，E1)， 满足V1V，E1E。则G1是G的子图。 例如：右图G4 就是G2 的子图。 213465

3、837图G3 网络示例2134图G4 子图示例2134图G2 无向图示例58.1 基本概念和运算顶点间关系： 如果 E 则称 Vi，Vj相邻接， Vi邻接到Vj，Vj邻接自Vi。 例如，右 图中， V1邻接到V2，V4邻接自V3 若( Vi,Vj )E则称Vi，Vj相邻接 顶点的度 顶点的邻接点的数目。 有向图中：入度，出度。 度入度出度。2134图G1 有向图示例68.1 基本概念和运算路径 若 顶点序列Vi1，Vi2，Vik， 满足E或 者(Vil，Vi(l+1)E）（l=1,2,k-1）， 则该顶点序列Vi1，Vi2，Vik 构成一条路径。 例: 图G1中，1,2,4,1,3,4是一条路

4、径简单路径 中间经过的顶点不重复的路径。 例:图G1中，( 1,2,4 ) ( 1,3,4 ) ( 1,3,4,1 ) 都是简单路径。回路 首尾相同的路径。 例如， ( 1,3,4,1 )简单回路 简单路径 + 回路2134图G1 有向图示例78.1 基本概念和运算 若无向图中任意两点间都存在路径 则称为连通图。 否则，称为不连通图（非连通图）。 非连通图包含若干连通分量-极大连通子图。 若有向图中的任意两点间可以互相到达 则称为强连通图。12534连通图示例6712534非连通图示例-三个连通分量6712534强连通图示例88.1 基本概念和运算若无向图中任意两点间都有一条边 则称为无向完全

5、图。 （共有n (n-1) / 2条边）若有向图中每个顶点到其余各点均有一条弧 则称为有向完全图。 （共有n (n-1) 条边） 125345阶无向完全图21344阶有向图示例98.1 基本概念和运算若无向图满足：连通并且无回路 则称为树。 树的定义有如下几个等价的描述： 有最少边数的连通图。 有n-1条边的连通图。 连通的无环图。有向树 如果在有向图中， 有一个顶点的入度为0，其余顶点的入度为1， 则称此图为有向树。 并称其中入度为0的顶点为有向根。 右下图就是一个有向树，其中顶点1就是有向根。6712534树的示例6712534有向树示例108.1 基本概念和运算图的运算： 基本运算： 初

6、始化图 插入顶点 插入边（弧） 修改权值 删除顶点 删除边（弧） 求指定顶点的邻接点 常用运算： 遍历118.1 基本概念和运算 邻接点的求解方法： 具体实现依赖于图的存储结构， 可以考虑用两个运算来实现求解： int firstadj(G,v); 返回顶点v的第一个邻接点号。 若不存在时，返回0（或定义为-1）。 int nextadj(G,v,w); 返回顶点v的邻接点中处于邻接点w之后的邻接点号。 若不存在时，返回0（或定义为-1）。128.2 图的存储图的存储-图结构在计算机中的存储形式1。邻接矩阵 （1）不带权值 假设图中有n个顶点。则采用nn的矩阵A来表示， 1 E 其中 Aij

7、0 否则例：13240 1 1 00 0 0 10 0 0 11 0 0 0行的方向：发出的弧列的方向 ：进入的弧对应关系138.2 图的存储 （2） 网络的表示方法 wij E Aij 0 或 否则例：4 4 3 54 23 65 2 6 12430 1 1 11 0 0 11 0 0 11 1 1 0无向图的邻接矩阵对称 142363524148.2 图的存储2. 邻接表表示法 -将 邻接点构成链表 例：12341243datafirstadj2341414123对应关系158.2 图的存储逆邻接链表-将“邻接自”的顶点连成链表 1234data firstadj4113432132123

8、4datafirstadj4412data firstadj对应关系代表弧168.3 图的遍历图的遍历访问图中所有顶点一次且仅且一次。 深度优先搜索遍历 图的两种遍历算法 广度优先搜索遍历8.3.1 深度优先搜索遍历（Depth First Search) 这一问题求解包括几个部分。 1. 基本算法 从顶点v0出发深度优先搜索遍历图G的dfs (v0)描述如下： (1) 访问v0； (2) 依次从v0的未被访问过的邻接点出发深度遍历。 17dfs(8)dfs(9)dfs(4)dfs(3)8.3.1 深度优先搜索遍历下面以下图为例来讨论dfs算法的执行过程：调用dfs(1) 此箭头表示是从遍历运

9、算dfs(1)中调用dfs(2)，即从顶点1直接转到2 此虚箭头表示是在dfs(3)执行完毕后返回到遍历运算dfs(2)中，即从顶点3返回到267125348109dfs(1)dfs(2)dfs(5)dfs(6)dfs(7)dfs(10)在访问顶点3后，由于顶点3的邻接点已全被访问，故dfs（3）执行到此结束，应返回到调用层，即返回到dfs(2) dfs(1)包含如下两部分操作：（1）访问顶点1；（2）依次执行dfs(2)和dfs(8) 188.3.1 深度优先搜索遍历将dfs（1）执行过程中所搜索的边连接起来（有标注的边），得到一棵生成树-dfs生成树。 671253481096712534

10、8109原图及其搜索示意图dfs(1)生成树198.3.1 深度优先搜索遍历下面讨论dfs算法的设计。为此，先回顾一下dfs (v0)的描述： (1) 访问v0； (2) 依次从v0的未被访问过的邻接点出发深度遍历。 分析：由算法描述可知： 访问顶点v0的基本操作： 可用visite(v0)简单表示。 设置访问标志数组visted ，并约定： 某顶点vi未被访问时， vistedi=FALSE（初值） vi被访问过后， vistedi=TRUE（初值） 求邻接点可以采用两个函数： firstadj(G,v) ：返回v的第一个邻接点（号），或0（不存在时）。 nextadj(G,v,w);返回v

11、的第邻接点中处于邻接点w之后的邻接点号, 或0（不存在时）访问v0时， vistedi=FTRUE;20YN8.3.1 深度优先搜索遍历 由讨论可得到dfs算法的流程图如下：由此得深度遍历基本算法dfs(v0)如下 : void dfs(int v0) visite(v0); visitedv0=TRUE; w=firstadj(G,v0); while(w!=0) if(!visitedw) dfs(w); w=nextadj(G,v0,w); Nvisite(v0); vistedv0=TRUE;W=0?W被访问过？Ndfs(w);w=nextadj(G,v,w);w=firstadj(G

12、,v) ：218.3.1 深度优先搜索遍历问题： （1）dfs算法是否适用于有向图？ （2）如何设置标志数组visited的初值？ 能否在dfs算法中设置？ （3）从某顶点出发是否能保证访问到所有顶点？ 或者说：选择一个起点调用一次dfs算法，能否实现对整个图的遍历？2. 遍历整个图的算法 dfs算法在应用于非连通图，或者是某些有向图时， 某一次调用就不能保证访问到所有顶点。如下图所示。 61253467125348109228.3.1 深度优先搜索遍历为此，需要重新选择起点来调用dfs算法。 如何选择新的起点？ 起点应满足什么条件？将对访问标志数组的赋初值运算， 以及选择起点的控制合在一起，

13、构成对整个图的遍历算法如下：void travel_dfs(graph G) for (i=1; i=n; i+) visitedi=FALSE; for (i=1; i=n; i+) if(!visitedi) dfs(i); 238.3.1 深度优先搜索遍历 3. 深度遍历算法的应用问题： （1）如何设计算法以判断给定的无向图是否是连通的？ （2）如何设计算法以求解给定的无向图中的边数？ （3）设计算法以判断给定的无向图是树。 （4）设计算法以判断给定的有向图是以v0为根的有向树。 （5）设计算法以判断图中的一个节点是否为关节点。 248.3.1 深度优先搜索遍历例1 设计算法以求解无向图

14、G的连通分量的个数。分析：对无向图G来说，选择某一顶点v执行dfs(v)， 可访问到所在连通分量中的所有顶点 因此，选择起点的次数就是图G的连通分量数， 这可通过修改遍历整个图的算法dfs_travel来实现：每调用一次dfs算法计数一次。 另外，考虑到要求求解连通分量数， 因而可以将算法设计为整型函数。 具体算法如下：258.3.1 深度优先搜索遍历int numofGC(graph G) int i; int k=0; / k用于连通分量的计数 for (i=1; i=n; i+) visitedi=FALSE; for (i=1; i=n; i+) if (visitedi=FALSE)

15、 k+; dfs(G,i); /用k来累计连通分量个数 return k ;遍历整个图的算法dfs_travel中的原来的部分268.3.1 深度优先搜索遍历例2 设计算法求出无向图G的边数。算法如下：void dfs (graph G, int v ) int w; visitedv=TRUE; /设置访问标志（访问结点的其它操作被省去） w=firstadj(G,v); while (w!=0) E+; /此处意味着找到一条边，故累计到变量E中 if (visitedw=FALSE) dfs(G,w); w=nextadj(G,v,w); dfs算法中原有的操作278.3.1 深度优先搜索

16、遍历int Enum (graph G ) int i; E=0; /全局变量E记录整个图中的边数 for (i=1; i=n; i+) visitedi=FALSE; for (i=1; i=n; i+) if (visitedi=FALSE;) dfs(G,i); return E/2;遍历整个图的算法dfs_travel中的原来的部分288.3.1 深度优先搜索遍历 4. 深度遍历算法的应用二例3：设计算法，将1-n(=20,或其他数)放在一个环上，使环上任意两个相邻元素的和为质数。分析：可以用图来描述该问题： 用顶点表示一个数 若两个数的和为质数， 则对应顶点之间有一条边。 例如，若n

17、=10，对应图如右所示。在这一表示下，问题转化为：求图中包含所有顶点的简单回路。如图所示的一个解。（1，2，3，4，7，6，5，8，9，10） 67125348910298.3.1 深度优先搜索遍历算法设计中需要注意的： 通过在dfs算法的基础上变化而得： （1）路径的记录：需要增加变量或参数以记录路径，因此，不妨设一个数组以记录路径中的顶点序列和一个记录长度的变量。 （2）若某些走法行不通，需要重来，为此，要恢复visitedi标志。 （3）需要判断首尾相接。308.3.1 深度优先搜索遍历算法构思如下:(1)设环上已有k个元素（0kn）。(2)若kn, 且不在当前路径上的顶点中存在与Bk相

18、邻的， 则依次从余下的顶点中取出与Bk相邻的顶点放置在Bk+1中, 转(1)。(3)若kn，而在余下的这些顶点中找不到一个与BK相邻的顶点， 或者是虽然存在邻接点，但这些结点均已在同等条件下放置过了，因而须从环上去掉BK，转(1)。(4)若k=,有两种情况: (a)Bn与B1相邻接, 说明已求得一解, 则输出求解结果, 然后返回。 (b)Bn与B1不邻接，说明前面的放置法不行, 即不构成环, 因而需要重新放置，即要去掉Bn和Bn-1，然而转(1)。为避免遗漏某种放置，从最后往前依次用余下的顶点中的与其前面相邻接的顶点替换。采用递归方式实现如下： 其中visited为标志数组，表示各结点是否在当

19、前的路径上。318.3.2 广度优先搜索遍历8.3.2 广度优先搜索遍历（Breadth_first search) 广度优先遍历 由近及远逐层访问顶点（典型的层次遍历） 1. 基本算法 从顶点v0出发广度优先搜索遍历图的算法bfs(v0): （1）访问v0 （2）依次访问v0的各邻接点。 （3）设最近一层访问序列为vi1，vi2，vik， 则依次访问 vi1，vi2，vik的 未被访问过的邻接点。 328.3.2 广度优先搜索遍历bfs(1)的执行过程如下图所示。其中用红线标注搜索路线。将搜索的便连起来得到bfs生成树。6712534810967125348109bfs生成树338.3.2

20、广度优先搜索遍历算法构思： (1) 设访问标志数组； (2)为了能依次访问上一层次的访问序列中的各顶点的邻接点， 需要设置一个结构以保存上一层次的顶点， 这一结构还要满足这样的要求： 这一层中最先被访问的顶点，其后继也应被最先检测到。 由此可知，这一结构应是队列。 (3)既然涉及到队列（不妨Q），则需要安排队列的运算： (a) 初始化； (b) 入队：每访问一个顶点v，除了访问操作、设置标志外，还要将其入队。 (c) 出队：从队列中删除一个顶点v，这意味着要依次访问v的所有未被访问过的邻接点。348.3.2 广度优先搜索遍历广度遍历的基本算法如下：void bfs(int v0) Queue

21、Q; visite(v0); visitedv0=TRUE; Q.append(v0); while(!Q.Empty() v=Q.Serve(); w=firstadj(G,v); while(w!=0) if(!visitew) visite(w); visitedw=TRUE; Q.append(w); w=nextadj(G,v,w); 358.3.2 广度优先搜索遍历2. 遍历整个图的算法 void travel_bfs(graph G) for(i=1;i=n;i+) visitedi=FALSE; for(i=1;i=n;i+) if(!visitedi) bfs(i); 3.广

22、度遍历算法的应用例：迷宫中的最短路径算法368.4 最小生成树问题：修建一个连接各个小区与供应站点之间的管道使得造价成本最低，即构造一颗最小生成树。但是如何求解？8.4.1 prim算法 1. 基本思想 在满足如下条件的过程中选出一条最小的边： 一端已选，另一端未选。 因此，该算法需要给出起点，以作为已选顶点。 2. 实例 对右图所示图， 用Prim算法求最小生成树。1746125349 1299156103378.4 最小生成树 46125349 1299156171039 61253412991561710439 61253412991561710439 61253412991561710

23、439 61253412991561710439 6125341299156171043388.4 最小生成树-求解过程的表格化求解已选顶点集 U顶点1候选边顶点2候选边顶点3候选边顶点4候选边顶点5候选边顶点6候选边11,61,6,51,6,5,41,6,5,4,31,6,5,4,3,2(1,2)/12(1,3)/(1,4)/(1,5)/9(1,6)/9(1,2)/12(6,2)/15(6,3)/17(6,4)/20(1,5)/9(6,5)/9(6,4)/20(5,4)/4(1,2)/12 (6,2)/15(6,3)/17(1,2)/12 (6,2)/15(6,3)/17(4,3)/3(1,

24、2)/12 (6,2)/15(3,2)/61746125349 1299156103398.4 最小生成树 Prim算法练习求下图的最小生成树：1235412354435323136已选顶点集合U顶点1候选边顶点2候选边顶点3候选边顶点4候选边顶点5候选边1(1,2)/3(1,3)/3(1,4)/4(1,5)/1,3(3,2)/5(3,4)/2(3,5)/61,3,4(4,2)/(4,5)/11,3,4,5(5,2)/31,3,4,5,213425Prim最小生成树注：最小生成树不唯一,但权值之和相同。408.4 最小生成树3.算法Prim算法的简要描述（设起点为v0）： 设置各候选边(v0,

25、vi)； for (i=1; i=n-1; i+) 从候选边中找出权值最小的边(v,vk)； /其中v已选边，vk未选 将vk设置为已选顶点； 调整候选边集合-调整新入选顶点和未选顶点之间的边的集合 由此可知，需要考虑如下几个方面的实现：（1）已选顶点的标识：可用数组来或集合来存储（或形式化描述）。（2）候选边的存储 ： 虽然每个顶点可能对应多个候选边，但只要最小的一个， 因此，用一个数组也可以，不妨用edges（下标用1-n即可）418.4 最小生成树初始化候选边数组edges； U=v0；for (i=1; i=n-1; i+) k=最小候选边的未选的一端； U=U+k； 以k修改edge

26、s； 注：edges的元素可以设置为v 思考：权值最小的边一定在最小生成树中么？ 分析 : prim算法的时间复杂度？428.4 最小生成树void prim(graph G,graph &T) for (i=1;i=n;i+) if ( G.Av0,i ) edgesi.vj=v0; edgesi.w=G.Av0,i; else edgesi.w= ; for (i=1;i=n;i+) selectedi=FALSE; selected1=TRUE; for (i=1;i=n-1;i+) minw= ; for (j=1;j=n;i+) if ( !selectedj & edgesj.wG

27、.Ak,w ) edgesw.w=G.Ak,w; edgesw.vj=k; w=nextadj(G,k,w); 初始化候选边数组edges初始化已选边数组selectedprim算法的时间复杂度是O(n2)。设置起始点已选从候选边中找出权值最小的边将k设置为已选顶点调整候选边集合438.4 最小生成树void prim(graph& g, int v0) / Prim算法的主函数，假设v0是起点MinEdgeArray MinEdges;int i,j,k;selected_Vset=v0; /将起始顶点v0作为己选点 Init_MinEdges(g,MinEdges,v0); /初始化候选边

28、集合for (i=1; in; i+) /控制n-1次最小边的选择 k=Get_MinEdge(g,MinEdges); /调用函数选择对应最小候选边的未选顶点 selected_Vset= selected_Vset+k; /在己选点集中插入顶点k change_MinEdges_with(g,MinEdges,k); /调整当前候选边集448.4 最小生成树typedef struct /候选边存储结构 int v; /未选顶点对应的候选边的另一端点 int w; /未选顶点对应的候选边的权值 MinEdgeType;typedef MinEdgeType MinEdgeArraymax_

29、num; /候选边集的存储结构void Init_MinEdges (graph& g, MinEdgeArray& MinEdges, int v0) /初始化候选边集 int i; for (i=1; i=n; i+) / 初始化每个未选顶点对应的候选边的相关信息if (have_edge(g,v0,i) /若g中存在边(v0,i) MinEdgesi.v=v0; /设置顶点i到起点v0的候选边信息 MinEdgesi.w=edge_weight(g,v0,i); /另一端点及相应的权值 else MinEdgesi.w = ; /否则，以表示不存在边(v0,i) 458.4 最小生成树

30、int Get_MinEdge(graph& g, MinEdgeArray& MinEdges) /从候选边集中选出边最短的顶点 int MMin,j,k; MMin = ; /设置当前最短边的权值 for (j=1; j=n; j+) /逐个比较，搜索最小的边 if (j是未选顶点 & MinEdgesj.wMMin) k=j; /记录当前具有最小边的未选顶点 MMin=MinEdgesj.w ; /以及对应最短边的权值return k ; /最后的k值记录的就是具有最小边的未选顶点，作为函数值返回468.4 最小生成树void change_MinEdges_with(graph& g,

31、 MinEdgeArray& MinEdges, int k) int j; /对新选出的候选顶点k调整当前候选边集 for (j=1; j=n; j+) /依次检查每个顶点 if (j 是未选顶点) if ( have_edge(g,k,j) & edge_weight(g,k,j)MinEdgesj.w ) ) /若顶点j到k有更小的边 MinEdgesj.w=edge_weight(g,k,j); /替换顶点j原候选边的相关信息 MinEdgesj.v=k; 478.4 最小生成树 2. 实例 判断构成回路的经典方法：电位法Kruskal算法 1.基本思想 反复在满足如下条件的边中选出一

32、条最小的边 使其和已选边不构成回路。1347521225352111364488.4 最小生成树3算法实现的讨论 Kruskal算法的简要描述： T=(V,) ; /初始化生成树T while(T中所含边数n-1) 从E中选取当前最短边(u,v)； 从E中删去边(u,v)； if ( (u,v)与T中边不构成回路) 将边(u,v)加入T中； 需解决问题：（1）候选边的存储 （2）判断所选择的边和已选的边不构成回路？ 分析Kruskal算法的时间复杂度为(eloge)、(n3) 。其时间性能和空间性能都不是很如意。498.4 最小生成树Kruskal算法练习 Kruskal算法 基本思想 反复在

33、满足如下条件的边中选出一条最小的边 使其和已选边不构成回路。1235443532313612354Kruskal最小生成树508.5 有向无环图的应用工程问题工程由多项活动构成，且活动之间存在一定制约。 工程问题： 1) 工程是否顺利进行？ 2) 工程至少需要的时间？ 3) 工程中哪些是关键环节？用图来表示工程： 其中，顶点表示活动；弧表示活动之间的制约关系。 这种图称为AOV网(Activity On Vertex Network)。工程是否顺利进行？AOV网是否存在有向回路123456518.5 有向无环图的应用工程问题如何判断AOV网中是否存在有向回路？解决方法：(1)用深度遍历要做许多

34、试探性工作；(2)用产生顶点序列的方法拓扑排序； 若图中顶点Vi到顶点Vj存在路径，则在序列中顶点Vi领先于顶点Vj。满足上述条件的顶点序列称为拓扑序列， 产生这一序列的过程称为拓扑排序。结论：如果能产生拓扑序列则说明AOV网中无回路，否则有回路。528.5 拓扑排序拓扑排序算法简单描述： 找一个入度为0的顶点v输出； 删除v及相关弧； 重复，直到无入度为0的顶点为止。538.5 拓扑排序实例12345612345653124563461234561235462456512345612345664123456123456对下图所示AOV网进行拓扑排序548.5 有向无环图的应用拓扑排序 判断有

35、无回路的条件：是否有拓扑序列。思考： 入度数组Ind （数组初始化的实现）； “删除v”的实现后继的入度减一； 找入度为0的顶点将入度为0的待输出顶点放到栈中，若出现入度为0 的顶点则入栈。拓扑排序算法分析 拓扑排序算法： 初始化入度数组Ind （若出现0入度顶点，则入栈s）； 若栈s为空，则跳出循环，转到 v=pop(s)并输出v； 对v的所有后继w实现：Indw-1；若Indw=0；则w入栈； 转； 判断是否存在回路。558.5 有向无环图的应用拓扑排序栈的演示123456123546132546568.5 有向无环图的应用拓扑排序 Bool toposort(graph G) get_I

36、nd(G,Ind); stack s; int count=0; for(i=1;i=n;i+) if ( Indi = 0 ) s.push(i); while ( !s.empty() ) v=s.pop(); coutv; count+; w=firstadj(G,v); while(w!=0) Indw-; if ( Indw = 0 ) s.push(w); w=nextadj(G,v,w); if ( count = n ) return TURE: else returen FALSE; 分析 若图采用邻接矩阵来存储，则算法复杂度为(n2)；若图采用邻接表来存储，则算法复杂度为(

37、n+e)。578.5 有向无环图的应用练习例:写出一种的拓扑序列所以，其中一种拓扑序列为： 25147368910思考：写出所有的拓扑排序。588.5 关键路径问题引入工程由多项活动构成，且活动之间存在一定制约。 工程问题： 1) 工程是否顺利进行？ 拓扑排序（AOV） 2) 工程至少需要的时间？ 3) 工程中哪些是关键环节？用图来表示工程： 其中，用弧表示活动； 用弧的权值表示活动的持续时间； 用弧两端的顶点分别表示活动的开始和结束， 即工程中的瞬间行为或事件。 这种图称为AOE网(Activity On Edge Network)。工程至少需要的时间？工程中哪些是关键环节？AOE网中源点到

38、汇点的最长路径 关键路径123456126537238911598.5 关键路径相关概念123456126537238911在AOE网中分别对应一个顶点， 称开始点（即入度为0的顶点）为源点， 称结束点（即出度为0的顶点）为汇点。 整个工程所需要的最少时间不是所有活动所需时间的累加,而应是从源点到汇点之间的最长的一条路径。 称这条最长的路径为关键路径(critical path)。求解事件的最早发生时间： 每个顶点事件的最早发生时间都依赖于其前驱顶点事件的最早发生时间。源点对应事件的最早发生时间为0求解事件的最迟发生时间每个顶点事件的最迟发生时间都不能影响到后续各顶点的最迟发生时间。 608.

39、5 关键路径为求最长路经，则需求各顶点对应事件的最早发生时间E ;为不耽误工期，则需求各顶点对应时间的最迟发生时间L . 如何判断AOE网中的关键路径？ 关键路径上的事件最早发生时间和最晚发生时间相等； 关键路径上的活动的开始和结束事件发生的时间差等于活动的持续时间。最早发生时间=最晚发生时间相等关键路径618.5 关键路径实例 关键路径的求解方法及路径12345678910a1=3a3=5a2=4a5=3a4=6a8=5a9=4a6=4a10=3a12=6a11=4a15=4a14=6a13=5a7=334598141312191915131491076300关键路径：（1,2,5,7,10

40、）和（1,2,5,8,10） 关键活动：a1，a4，a8，a9，a13，a14 628.6 最短路径(Shortest path)从单个点到其余各点之间的最短路径 Dijkstra算法各点之间的最短路径 Floyd算法638.6 最短路径Dijkstra算法从单个点到其余各点间的最短路径Dijkstra算法 基本思想 按照最短路径长度不减的次序求各顶点的解。 若已知道路v0v1v2v3vn-1vn是v0到vn最近的路， 则途径的某顶点vi也为v0到vi最短的路。12345612653723892648.6 最短路径Dijkstra算法实例12345612653723892例求下图中顶点1到其余各顶点的最短路径。101238510364142512(1)初始化:1到v,若有边,则pathv=边;disti=边的值(2)选出disti为最小值,则pathi为1到i的最短路径(3)修改经过i更近的路径(4)重复（2）（3）658.6 最短路径Dijkstra算法描述方法如下： （其中：pathv和distv表示从v0到v的最短路径及其长度）（1）对v0以外的各顶点vi，若存在，则将其作为v0到vi的（暂时的）最短路径存放到pathv中，将其权值作为对应的路径长度存放到distv中。（2）