第03基本数据结构与运算优秀PPT.ppt

第第03基本数据结构与运算基本数据结构与运算现在学习的是第1页，共50页3.6.1 图的基本概念图的基本概念BACD63215数据结构数据结构 B=B=（D D，R R）图：图：G=G=（V V，E E）顶点顶点:图中的数据元素图中的数据元素V V：表示：表示顶顶点的非空有限集合。点的非空有限集合。E E：表示两个：表示两个顶顶点之间关系的集合。点之间关系的集合。图的定义、术语图的定义、术语现在学习的是第2页，共50页图图有向图有向图无向图无向图在有向图中，在有向图中，V 表示从表示从V V1 1到到V V3 3的一条弧。的一条弧。V V1 1为弧尾或初始点，为弧尾或初始点，V V3 3为弧头或终端点。为弧头或终端点。在无向图中，在无向图中，(V(V1 1，V V3 3)表示表示V V1 1和和V V3 3之间的一条边之间的一条边。V1V3V2V4V1V3V2V4图的定义、术语图的定义、术语现在学习的是第3页，共50页V1V3V2V4V1V3V2V4顶点集合顶点集合V=V1，V2，V3，V4 弧的集合弧的集合G=,顶点集合顶点集合V=V1，V2，V3，V4 边的集合边的集合E=(V1,V3),(V1,V2),(V1,V4),(V2,V4)G=(V,E)顶点顶点(V1,V3)与与(V3,V1)表示同一条边表示同一条边图的定义、术语图的定义、术语现在学习的是第4页，共50页BACD63215权权：与图的边或弧相关的数。：与图的边或弧相关的数。顶点的度顶点的度：依附于该顶点的边数或弧数。：依附于该顶点的边数或弧数。出度出度：（仅对有向图）以该顶点为尾的弧数。：（仅对有向图）以该顶点为尾的弧数。入度入度：（仅对有向图）以该顶点为头的弧数。：（仅对有向图）以该顶点为头的弧数。路径路径：顶点：顶点A A与顶点与顶点C C之间存在一条路径。路径上边或弧的数目之间存在一条路径。路径上边或弧的数目 称为该路径的路径长度。称为该路径的路径长度。连通图连通图：无向图任意两顶点都有路径（：无向图任意两顶点都有路径（没有孤立顶点）没有孤立顶点）没有孤立顶点）没有孤立顶点）强连通图强连通图：有向图有向图任意两顶点都有路径任意两顶点都有路径网网网网：带权的图称为网：带权的图称为网：带权的图称为网：带权的图称为网图的定义、术语图的定义、术语现在学习的是第5页，共50页图的存储图的存储 邻接矩阵邻接矩阵n3.6.2 图的存储图的存储n n1.邻接矩阵法邻接矩阵法uu（1 1）给顶点编号）给顶点编号）给顶点编号）给顶点编号uu（2 2）建立邻接（关系）矩阵）建立邻接（关系）矩阵）建立邻接（关系）矩阵）建立邻接（关系）矩阵21431 2 3 41 2 3 40 0 0 01 0 1 11 0 0 10 1 1 0a a i j i j表示弧表示弧 ij 1 1：表示有弧；：表示有弧；0:0:表示无弧表示无弧任意顶点的出度是该行元素之和任意顶点的出度是该行元素之和任意顶点的出度是该行元素之和任意顶点的出度是该行元素之和任意顶点的入度是该列元素之和任意顶点的入度是该列元素之和任意顶点的入度是该列元素之和任意顶点的入度是该列元素之和现在学习的是第6页，共50页图的存储图的存储 邻接矩阵邻接矩阵uu邻接矩阵的优点：邻接矩阵的优点：增减边的操作简单增减边的操作简单uu邻接矩阵的缺点：邻接矩阵的缺点：增减顶点的操作需要搬移大量的元素，增减顶点的操作需要搬移大量的元素，浪费存储空间浪费存储空间21431 2 3 41 2 3 41 1 2 2 3 3 4 40 1 1 01 0 1 11 1 0 10 1 1 0无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的现在学习的是第7页，共50页图的存储图的存储 邻接矩阵的实现邻接矩阵的实现n n图的邻接矩阵实现图的邻接矩阵实现typedef struct graph_mtypedef struct graph_melemtype nodeMAXNUM;int arcsMAXNUMMAXNUM;graph_m;graph_m;顶点集合顶点集合顶点集合顶点集合边的邻接矩阵边的邻接矩阵边的邻接矩阵边的邻接矩阵二维数组二维数组现在学习的是第8页，共50页图的存储图的存储 邻接表邻接表n n2.邻接表法邻接表法uu一个邻接表由两种结构组成一个邻接表由两种结构组成存放各顶点元素的数组，头结点存放各顶点元素的数组，头结点各顶点各自的邻接链表，邻接结点各顶点各自的邻接链表，邻接结点2143231 data2data3data4data134124233data顶点号顶点号元素域元素域邻接链表邻接链表头指针头指针2邻接顶点号邻接顶点号下一邻接结点下一邻接结点现在学习的是第9页，共50页图的存储（课堂练习）图的存储（课堂练习）n n请写出下面这副图的邻接表请写出下面这副图的邻接表uu1）给顶点编号）给顶点编号uu2）建立顶点数组）建立顶点数组uu3）建立各顶点的邻接链表）建立各顶点的邻接链表注意，此图为有向图注意，此图为有向图2 21 13 34 45 51datadata2datadata3datadata4datadata5datadata2313514现在学习的是第10页，共50页图的存储图的存储 邻接表的实现邻接表的实现n n邻接表的定义邻接表的定义uu头结点的定义头结点的定义uu邻接结点的定义邻接结点的定义顶点号顶点号元素域元素域与头结点与头结点与头结点与头结点相邻的顶点相邻的顶点相邻的顶点相邻的顶点typedef struct headnodetypedef struct headnodeint node_index;int node_index;elemtype data;elemtype data;struct adj_node*next_adj;headnode;headnode;顶点号顶点号下一个与头结点相邻的下一个与头结点相邻的下一个与头结点相邻的下一个与头结点相邻的顶点的邻接结点顶点的邻接结点顶点的邻接结点顶点的邻接结点typedef struct adj_nodetypedef struct adj_nodeint node_index;struct adj_node*next_adj;struct adj_node*next_adj;adj_node;adj_node;现在学习的是第11页，共50页图的存储图的存储 邻接表邻接表uu图邻接表的定义图邻接表的定义typedef struct graph_ltypedef struct graph_lheadnode node_listMAXNUM;int node_num;graph_l;231 data2data3data4data13412423现在学习的是第12页，共50页图的存储图的存储 邻接表邻接表2143231 data2data3data4data1341242321431 data2data3data4data134134注意：有向图与无向图的区别注意：有向图与无向图的区别注意：有向图与无向图的区别注意：有向图与无向图的区别现在学习的是第13页，共50页图的存储图的存储n n图的邻接表存储法的特点图的邻接表存储法的特点uu优点优点节省存储空间节省存储空间边的插入和删除操作比较简便边的插入和删除操作比较简便uu缺点缺点结构复杂结构复杂vv具有两种不同的基本组成单元具有两种不同的基本组成单元现在学习的是第14页，共50页图的存储图的存储n n3.边带权值的图的存储边带权值的图的存储uu1）在邻接矩阵中的实现）在邻接矩阵中的实现0 2 3 520 1 031 0 15 0 1 0a44=a44=a i j a i j：记录边的权值；为：记录边的权值；为：记录边的权值；为：记录边的权值；为0 0表示无边表示无边表示无边表示无边12432 235 51 11 1现在学习的是第15页，共50页图的存储图的存储n n3.边带权值的图的存储边带权值的图的存储uu2）在邻接表中的实现）在邻接表中的实现在邻接结点结构中增加一个权值域在邻接结点结构中增加一个权值域1 data2data3data4data233211354102331顶点号顶点号边权值边权值1 12 24 433 32 25 51 11 110103 3现在学习的是第16页，共50页图的遍历图的遍历n n3.6.3 图的遍历图的遍历n n问题：问题：uu1）对于连通图，从一个顶点出发沿着所有可能）对于连通图，从一个顶点出发沿着所有可能的路径，是否可以将所有的顶点遍历到。的路径，是否可以将所有的顶点遍历到。uu2）图中有回路，遍历算法可能产生死循环。）图中有回路，遍历算法可能产生死循环。n n有重复的路径称为有重复的路径称为回路回路2143现在学习的是第17页，共50页图的遍历图的遍历 深优深优n n1.深度优先遍历深度优先遍历uu（1）从一个未访问过的顶点开始，访问它的一个）从一个未访问过的顶点开始，访问它的一个未访问过的相邻顶点。未访问过的相邻顶点。uu（2）如果顶点的所有相邻顶点都是已访问过的，）如果顶点的所有相邻顶点都是已访问过的，则需要回溯到之前的一个顶点，选取它的另一个则需要回溯到之前的一个顶点，选取它的另一个未被访问的相邻顶点。未被访问的相邻顶点。uu（3）对于前两个步骤是递归的）对于前两个步骤是递归的现在学习的是第18页，共50页图的遍历图的遍历 深优深优n n1.深度优先遍历深度优先遍历uu（1）从一个未访问过的顶点开始，访问它的一个）从一个未访问过的顶点开始，访问它的一个未访问过的相邻顶点。未访问过的相邻顶点。uu（2）如果顶点的所有相邻顶点都是已访问过的，）如果顶点的所有相邻顶点都是已访问过的，则需要回溯到之前的一个顶点，选取它的另一个则需要回溯到之前的一个顶点，选取它的另一个未被访问的相邻顶点。未被访问的相邻顶点。uu（3）对于前两个步骤是递归的）对于前两个步骤是递归的1258463717365 284回到回到8173652841 3 6 8 4 2 5 7或者按以下顺序遍历：或者按以下顺序遍历：或者按以下顺序遍历：或者按以下顺序遍历：注意使用栈支持递归：注意使用栈支持递归：注意使用栈支持递归：注意使用栈支持递归：现在学习的是第19页，共50页图的遍历图的遍历 深优深优n n深度优先遍历的特点深度优先遍历的特点uu“深度深度”：总是访问顶点的：总是访问顶点的一个一个相邻顶点，好像相邻顶点，好像是沿着图中的一条路径走到是沿着图中的一条路径走到“底底”，然后后退一，然后后退一点，再选一条路。如此点，再选一条路。如此“进进退退进进退退”，直到所有，直到所有顶点都被访问顶点都被访问uu对于连通图，如果第一个被访问的顶点的所有相对于连通图，如果第一个被访问的顶点的所有相邻顶点都被访问了，意味着图中所有顶点都被访邻顶点都被访问了，意味着图中所有顶点都被访问了。问了。即栈空时即栈空时现在学习的是第20页，共50页图的遍历图的遍历 深优深优n n用递归调用实现深度优先遍历算法用递归调用实现深度优先遍历算法void dfs void dfs（g g，v v）1 1访问顶点访问顶点访问顶点访问顶点v v；visit（v）；）；visited v =1;p=gv-next_adjwhile(p!=NULL)w=p-node_index;if(visitedw=0)p=p-next_adj;2 2取得顶点的一个未被访问过的顶点取得顶点的一个未被访问过的顶点取得顶点的一个未被访问过的顶点取得顶点的一个未被访问过的顶点ww；3 dfs3 dfs（g g，ww）；回到）；回到）；回到）；回到2 2；4重复重复2，3直到该顶点所有的相邻顶点都被访问过；直到该顶点所有的相邻顶点都被访问过；dfs(g,w);现在学习的是第21页，共50页12345void dfs（g，v）visited v =1;p=g v-next_adj while(p!=NULL)w=p-node_index;if(visited w =0)dfs(g,w);p=p-next_adj;void dfs（g，2）visited 2 =1;p=g 2-next_adj while(p!=NULL)w=p-node_index;if(visited 3 =0)dfs(g,3);p=p-next_adj;void dfs（g，3）visited 3 =1;p=g 3-next_adj while(p!=NULL)w=p-node_index;if(visited 4 =0)dfs(g,4);p=p-next_adj;void dfs（g，4）visited 4 =1;p=g 4-next_adj while(p!=NULL)w=p-node_index;if(visited w =0)dfs(g,w);p=p-next_adj;void dfs（g，5）visited 5 =1;p=g 5-next_adj while(p!=NULL)w=p-node_index;if(visited w =0)dfs(g,w);p=p-next_adj;void dfs（g，1）visited 1 =1;p=g 1-next_adj while(p!=NULL)w=p-node_index;if(visited 2 =0)dfs(g,2);p=p-next_adj;if(visited 5 =0)dfs(g,5);现在学习的是第22页，共50页图的遍历图的遍历 广优广优n n2.广度优先遍历广度优先遍历uu访问顶点访问顶点v后，接着依次访问后，接着依次访问v的所有邻接顶点，的所有邻接顶点，再依次访问这些邻接顶点的邻接顶点。直到所有再依次访问这些邻接顶点的邻接顶点。直到所有的顶点都被访问过。的顶点都被访问过。125846371 12 23 34 45 56 67 78 8注意：注意：注意：注意：8 8是作为哪个顶是作为哪个顶是作为哪个顶是作为哪个顶点的邻接顶点被访问点的邻接顶点被访问点的邻接顶点被访问点的邻接顶点被访问的？的？的？的？1 12 23 34 45 56 67 7 8 8体会队列操作方式：体会队列操作方式：体会队列操作方式：体会队列操作方式：现在学习的是第23页，共50页图的遍历图的遍历 广优广优n n广度优先遍历的特点广度优先遍历的特点uu“广度广度”：总是在访问了一个顶点后，依次访问：总是在访问了一个顶点后，依次访问它的所有相邻顶点。然后再从它的第一个相邻顶它的所有相邻顶点。然后再从它的第一个相邻顶点开始，访问其所有的相邻顶点。如此逐个顶点点开始，访问其所有的相邻顶点。如此逐个顶点地逐步扩散，直到所有的顶点都被访问。地逐步扩散，直到所有的顶点都被访问。uu广度优先遍历操作具有队列操作的特点，当从队广度优先遍历操作具有队列操作的特点，当从队列中取出最后一个顶点，发现该顶点的所有相邻列中取出最后一个顶点，发现该顶点的所有相邻顶点都被访问过时，意味着图中所有的顶点都已顶点都被访问过时，意味着图中所有的顶点都已被访问过被访问过现在学习的是第24页，共50页生成树与图生成树与图n n3.6.4 图的应用图的应用n n1.生成树定义生成树定义uu假设存在这样一颗树：假设存在这样一颗树：假设存在这样一颗树：假设存在这样一颗树：树结点的集合与图的顶点集合相等树结点的集合与图的顶点集合相等树结点的集合与图的顶点集合相等树结点的集合与图的顶点集合相等树的分支全部由图的边组成。树的分支全部由图的边组成。树的分支全部由图的边组成。树的分支全部由图的边组成。称这颗树是这幅称这颗树是这幅称这颗树是这幅称这颗树是这幅图的生成树图的生成树图的生成树图的生成树uu生成树是图的生成树是图的生成树是图的生成树是图的:子集子集子集子集/子图子图子图子图是一个不包含回路的子图是一个不包含回路的子图是一个不包含回路的子图是一个不包含回路的子图图的生成树是图的生成树是图的生成树是图的生成树是2 21 143 3214321432143不唯一的！不唯一的！不唯一的！不唯一的！唯一的！唯一的！唯一的！唯一的！取决于遍历方法和遍历的起始点取决于遍历方法和遍历的起始点现在学习的是第25页，共50页生成树的示例生成树与图生成树与图对于一个有对于一个有n个顶点个顶点的连通图的连通图G，其生成树包含了其生成树包含了 条边。条边。深度优先搜索得到的生成树深度优先搜索得到的生成树广度优先搜索得到的生成树广度优先搜索得到的生成树n1现在学习的是第26页，共50页权值权值权值权值生成树与图生成树与图n n2.最小费用生成树（最小费用生成树（通信网络、交通网络）uu在图所有生成树中，边的权值总和最小的生成树在图所有生成树中，边的权值总和最小的生成树1245636536642416124563边边边边1 13 31 1462 22 25 53 31 14 443 36 64 42 23 35126 6356 65 56 66 6将边按权将边按权将边按权将边按权值大小排值大小排值大小排值大小排列列列列现在学习的是第27页，共50页生成树与图生成树与图n n算法分析算法分析uu关键技术：关键技术：关键技术：关键技术：为什么在（为什么在（为什么在（为什么在（1,41,4）边选中后不能选（）边选中后不能选（）边选中后不能选（）边选中后不能选（3,63,6）边）边）边）边在选择（在选择（在选择（在选择（3,63,6）边和（）边和（）边和（）边和（2,32,3）边时有什么不同，怎样设置）边时有什么不同，怎样设置）边时有什么不同，怎样设置）边时有什么不同，怎样设置条件以区别？条件以区别？条件以区别？条件以区别？vv当时当时当时当时3 3和和和和6 6位于同一图中，位于同一图中，位于同一图中，位于同一图中，2 2、5 5和和和和3 3位于不同的图中位于不同的图中位于不同的图中位于不同的图中12456365366424161245631 14 44 43 36 64 42 23 35 5回路回路回路回路现在学习的是第28页，共50页生成树与图生成树与图1245631 1）开始时所有的节点都位于不同的图中）开始时所有的节点都位于不同的图中）开始时所有的节点都位于不同的图中）开始时所有的节点都位于不同的图中2）选择一条连接两个不同子图的最短边）选择一条连接两个不同子图的最短边3 3）连接以后两个子图的所有顶点都要改为）连接以后两个子图的所有顶点都要改为）连接以后两个子图的所有顶点都要改为）连接以后两个子图的所有顶点都要改为 在一个子图中在一个子图中4 4）当所有的顶点都位于一个子图中，）当所有的顶点都位于一个子图中，）当所有的顶点都位于一个子图中，）当所有的顶点都位于一个子图中，算法结束。算法结束。权值权值权值权值边边边边1 13 31 14 46 62 22 25 53 31 14 44 43 36 642 23 351 12 26 6思考思考思考思考既然是颗树，如果选择边数为既然是颗树，如果选择边数为既然是颗树，如果选择边数为既然是颗树，如果选择边数为n n1 1个时可不可以结束算法呢？个时可不可以结束算法呢？个时可不可以结束算法呢？个时可不可以结束算法呢？算法的优化算法的优化算法的优化算法的优化现在学习的是第29页，共50页图的最短路径图的最短路径n n3.最短路径最短路径uu图中两个顶点之间有图中两个顶点之间有 条路径条路径uu最短路径：最短路径：是路径中边（弧）的权值总和最小的路径是路径中边（弧）的权值总和最小的路径uu计算机网络中常使用最短路径算法计算最佳路径计算机网络中常使用最短路径算法计算最佳路径uu交通网络中使用最短路径算法计算最短旅途交通网络中使用最短路径算法计算最短旅途多多多多Dijkstra AlgorithmFloyd AlgorithmFloyd Algorithm现在学习的是第30页，共50页A1A2A4A3A526512151 1）初始化时，设）初始化时，设）初始化时，设）初始化时，设A1A1到其它不直连顶点距离为到其它不直连顶点距离为到其它不直连顶点距离为到其它不直连顶点距离为 寻找寻找A1到所有节点的最短路径到所有节点的最短路径A2A3A4A5顶点顶点距离距离路径路径2 2）选择距离最短的路径）选择距离最短的路径）选择距离最短的路径）选择距离最短的路径3 3）观察通过新选择的路径是否能更短地到）观察通过新选择的路径是否能更短地到）观察通过新选择的路径是否能更短地到）观察通过新选择的路径是否能更短地到达其它顶点达其它顶点达其它顶点达其它顶点4 4）选择出的最短路径将不参加下一轮比较）选择出的最短路径将不参加下一轮比较）选择出的最短路径将不参加下一轮比较）选择出的最短路径将不参加下一轮比较5 5）反复）反复）反复）反复2-42-4步，直到不剩有顶点步，直到不剩有顶点步，直到不剩有顶点步，直到不剩有顶点265A2A3A4A1 A2 A33更新更新A1 A2 A33A1 A2 A4 A1 A2 A5 4A1 A2 A3 A44更新更新A1 A2 A3 A44A1 A2 A3 A58A1 A2 A54A1 A2 A3 A4 A5 更新更新Dijkstra Algorithm现在学习的是第31页，共50页拓拓 扑扑 排排 序序按一定顺序进行的活动，可以使用顶点表示活动、顶点之间的有向边表示活动间的先后关系的有向图来表示，这种有向图称为顶点表示活动网络(ActivityOnVertexnetwork，简称AOV网网)。AOV网中的有向边表示了活动之间的制约关系。4.拓拓 扑扑 排排 序序现在学习的是第32页，共50页将AOV网中的所有顶点排列成一个线性序列vi1,vi2,vin，并且这个序列同时满足关系：若在AOV网中从顶点vi到顶点vj存在一条路径，则在线性序列中vi必在vj之前，我们就称这个线性序列为拓拓扑扑序序列列。把对AOV网构造拓扑序列的操作称为拓扑排序。拓扑排序。在实际的意义上，AOV网中存在的有向环就意味着某些活动是以自己为先决条件，这显然是荒谬的。例如对于程序的数据流图而言，AOV网中存在环就意味着程序存在一个死循环。现在学习的是第33页，共50页任何一个无环的AOV网中的所有顶点都可排列在一个拓扑序列里，拓扑排序的基本操作如下：(1)从网中选择一个入度为0的顶点并且输出它。(2)从网中删除此顶点及所有由它发出的边。(3)重复上述两步，直到网中再没有入度为0的顶点为止。现在学习的是第34页，共50页现在学习的是第35页，共50页n 以上的操作会产生两种结果：以上的操作会产生两种结果：n一种是网中的全部顶点都被输出，整个拓扑排序完成；一种是网中的全部顶点都被输出，整个拓扑排序完成；n另另一一种种是是网网中中顶顶点点未未被被全全部部输输出出，剩剩余余的的顶顶点点的的入入度度均均不不为为0，则则说明网中存在有向环。说明网中存在有向环。n用以上操得到了一种拓扑序列：用以上操得到了一种拓扑序列：nC1,C2,C3,C4,C5,C7,C9,C10,C12,C11,C6,C8。n拓扑序列可以是种多现在学习的是第36页，共50页AOV网拓扑排序过程现在学习的是第37页，共50页在邻接表存储结构中实现拓扑排序算法的步骤为：在邻接表存储结构中实现拓扑排序算法的步骤为：(1)扫描顶点表，将入度为0的顶点入栈。(2)当栈非空时执行以下操作：将栈顶顶点vi的序号弹出，并输出之；检查vi的出边表，将每条出边表邻接点域所对应的顶点的入度域值减1，若该顶点入度为0，则将其入栈；(3)若输出的顶点数小于n，则输出“有回路”，否则拓扑排序正常结束。现在学习的是第38页，共50页关关 键键 路路 径径5.关键路径关键路径AOE网络(Activity On Edge network)：有向边：表示一个子工程（活动）有向边：表示一个子工程（活动）边上的权值：表示一个活动持续的时间边上的权值：表示一个活动持续的时间顶顶点点：表表示示事事件件，它它表表示示了了一一种种状状态态，即即它它的的入入边边所所表表示示的的活活动动均均已已完完成，它的出边所表示的活动可以开始。成，它的出边所表示的活动可以开始。这这种种带带权权的的有有向向网网络络称称为为 AOE网网络络(Activity On Edge network)，即即边表示活动网络。边表示活动网络。现在学习的是第39页，共50页一个AOE网络的示例现在学习的是第40页，共50页关键路径：关键路径：从源点到汇点的具有最大路径长度的路径。从源点到汇点的具有最大路径长度的路径。关键活动：关键活动：关键路径上的各个活动。关键路径上的各个活动。明明确确了了哪哪些些活活动动是是关关键键活活动动就就可可以以设设法法提提高高关关键键活活动动的的功功效效，以以便便缩短整个工期。缩短整个工期。现在学习的是第41页，共50页其中E1是网络中以vj为终点的入边集合，dur()是有向边上的权值。vl l(j)(j)的计算可从汇点开始，向源点逆推计算：的计算可从汇点开始，向源点逆推计算：(13.2)其中E2是网络中以vj为起点的出边集合。(1)(2)ve(j)的计算可从从源点源点开始开始利用以下的递推公式求得现在学习的是第42页，共50页ve(1)=0ve(2)=maxve(1)+dur()=max0+3=3ve(3)=maxve(1)+dur()=max0+2=2ve(4)=mawve(2)+dur(),ve(3)+dur()=max3+4,2+3=7ve(5)=maxve(4)+dur(),ve(2)+dur()=max7+4,3+8=11ve(6)=maxve(3)+dur(),ve(4)+dur()=max2+7,7+2=9ve(7)=maxve(5)+dur(),ve(6)+dur()=max11+9,9+6=20vl(7)=ve(7)=20按(1)式和(2)式，可计算出图该AOE网各个事件的最早发生时间和最迟发生时间：现在学习的是第43页，共50页vl(6)=minvl(7)dur()=min206=14vl(5)=minvl(7)dur()=min209=11vl(4)=minvl(5)dur(),vl(6)dur()=min114,112=7vl(3)=minvl(4)dur(),vl(6)dur()=min73,147=4vl(2)=minvl(4)dur(),vl(5)dur()=min74,118=3vl(1)=minvl(2)dur(),vl(3)dur()=min33,42=0现在学习的是第44页，共50页利用利用 ve(i)=e(i)和和l(i)=vl(k)dur()网络的关键路径现在学习的是第45页，共50页关键活动算法主要由以下步骤组成：关键活动算法主要由以下步骤组成：(1)对AOE网进行拓扑排序，同时按拓扑排序顺序求出各顶点事件的最早发生时间ve，若网中有回路，则算法终止，否则执行(2)。(2)按拓扑序列的逆序求出各顶点事件的最迟发生时间vl。(3)根据ve和vl的值求出ai的最早开始时间e(i)和最迟开始时间l(i)。若l(i)=e(i)，则ai为关键活动。因为计算各顶点的ve值是在拓扑排序的过程中进行的，所以可通过对拓扑排序算法进行一些修正来实现求关键路径的算法。现在学习的是第46页，共50页作业作业现在学习的是第47页，共50页现在学习的是第48页，共50页一个网络及其邻接矩阵现在学习的是第49页，共50页Kruskal算法构造最小生成树的过程现在学习的是第50页，共50页