第03基本数据结构与运算精选文档.ppt

《第03基本数据结构与运算精选文档.ppt》由会员分享，可在线阅读，更多相关《第03基本数据结构与运算精选文档.ppt（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第03基本数据结构与运算基本数据结构与运算本讲稿第一页，共五十页3.6.1 图的基本概念图的基本概念BACD63215数据结构数据结构 B=B=（D D，R R）图：图：G=G=（V V，E E）顶点顶点:图中的数据元素图中的数据元素V V：表示：表示顶顶点的非空有限集合。点的非空有限集合。E E：表示两个：表示两个顶顶点之间关系的集合。点之间关系的集合。图的定义、术语图的定义、术语本讲稿第二页，共五十页图图有向图有向图无向图无向图在有向图中，在有向图中，V 表示从表示从V V1 1到到V V3 3的一条弧。的一条弧。V V1 1为弧尾或初始点，为弧尾或初始点，V V3 3为弧头或终端点。为

2、弧头或终端点。在无向图中，在无向图中，(V(V1 1，V V3 3)表示表示V V1 1和和V V3 3之间的一条边之间的一条边。V1V3V2V4V1V3V2V4图的定义、术语图的定义、术语本讲稿第三页，共五十页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)表示同一条边表示同一条边图的定义、术语图的定义、术语本讲稿第四页，共五十页BACD63215权权：与图的边或弧

3、相关的数。：与图的边或弧相关的数。顶点的度顶点的度：依附于该顶点的边数或弧数。：依附于该顶点的边数或弧数。出度出度：（仅对有向图）以该顶点为尾的弧数。：（仅对有向图）以该顶点为尾的弧数。入度入度：（仅对有向图）以该顶点为头的弧数。：（仅对有向图）以该顶点为头的弧数。路径路径：顶点：顶点A A与顶点与顶点C C之间存在一条路径。路径上边或弧的数目之间存在一条路径。路径上边或弧的数目 称为该路径的路径长度。称为该路径的路径长度。连通图连通图：无向图任意两顶点都有路径（：无向图任意两顶点都有路径（没有孤立顶点）没有孤立顶点）没有孤立顶点）没有孤立顶点）强连通图强连通图：有向图有向图任意两顶点都有路径

4、任意两顶点都有路径网网网网：带权的图称为网：带权的图称为网：带权的图称为网：带权的图称为网图的定义、术语图的定义、术语本讲稿第五页，共五十页图的存储图的存储 邻接矩阵邻接矩阵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:表示无弧表示无弧任意顶点的出度是该

5、行元素之和任意顶点的出度是该行元素之和任意顶点的出度是该行元素之和任意顶点的出度是该行元素之和任意顶点的入度是该列元素之和任意顶点的入度是该列元素之和任意顶点的入度是该列元素之和任意顶点的入度是该列元素之和本讲稿第六页，共五十页图的存储图的存储 邻接矩阵邻接矩阵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无向图的邻接矩阵是对

6、称的无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的无向图的邻接矩阵是对称的本讲稿第七页，共五十页图的存储图的存储 邻接矩阵的实现邻接矩阵的实现n n图的邻接矩阵实现图的邻接矩阵实现typedef struct graph_mtypedef struct graph_melemtype nodeMAXNUM;elemtype nodeMAXNUM;int arcsMAXNUMMAXNUM;int arcsMAXNUMMAXNUM;graph_m;graph_m;顶点集合顶点集合顶点集合顶点集合边的邻接矩阵边的邻接矩阵边的邻接矩阵边的邻接矩阵二维数组二维数组本讲稿第八页，共五十页图的存储图的存储

7、 邻接表邻接表n n2.邻接表法邻接表法uu一个邻接表由两种结构组成一个邻接表由两种结构组成存放各顶点元素的数组，头结点存放各顶点元素的数组，头结点各顶点各自的邻接链表，邻接结点各顶点各自的邻接链表，邻接结点2143231 data2data3data4data134124233data顶点号顶点号元素域元素域邻接链表邻接链表头指针头指针2邻接顶点号邻接顶点号下一邻接结点下一邻接结点本讲稿第九页，共五十页图的存储（课堂练习）图的存储（课堂练习）n n请写出下面这副图的邻接表请写出下面这副图的邻接表uu1）给顶点编号）给顶点编号uu2）建立顶点数组）建立顶点数组uu3）建立各顶点的邻接链表）建立

8、各顶点的邻接链表注意，此图为有向图注意，此图为有向图2 21 13 34 45 51datadata2datadata3datadata4datadata5datadata2313514本讲稿第十页，共五十页图的存储图的存储 邻接表的实现邻接表的实现n n邻接表的定义邻接表的定义uu头结点的定义头结点的定义uu邻接结点的定义邻接结点的定义顶点号顶点号元素域元素域与头结点与头结点与头结点与头结点相邻的顶点相邻的顶点相邻的顶点相邻的顶点typedef struct headnodetypedef struct headnodeint node_index;int node_index;elemty

9、pe data;elemtype data;struct adj_node*next_adj;struct adj_node*next_adj;headnode;headnode;顶点号顶点号下一个与头结点相邻的下一个与头结点相邻的下一个与头结点相邻的下一个与头结点相邻的顶点的邻接结点顶点的邻接结点顶点的邻接结点顶点的邻接结点typedef struct adj_nodetypedef struct adj_nodeint node_index;int node_index;struct adj_node*next_adj;struct adj_node*next_adj;adj_node;a

10、dj_node;本讲稿第十一页，共五十页图的存储图的存储 邻接表邻接表uu图邻接表的定义图邻接表的定义typedef struct graph_ltypedef struct graph_lheadnode node_listMAXNUM;headnode node_listMAXNUM;int node_num;int node_num;graph_l;graph_l;231 data2data3data4data13412423本讲稿第十二页，共五十页图的存储图的存储 邻接表邻接表2143231 data2data3data4data1341242321431 data2data3data

11、4data134134注意：有向图与无向图的区别注意：有向图与无向图的区别注意：有向图与无向图的区别注意：有向图与无向图的区别本讲稿第十三页，共五十页图的存储图的存储n n图的邻接表存储法的特点图的邻接表存储法的特点uu优点优点节省存储空间节省存储空间边的插入和删除操作比较简便边的插入和删除操作比较简便uu缺点缺点结构复杂结构复杂vv具有两种不同的基本组成单元具有两种不同的基本组成单元本讲稿第十四页，共五十页图的存储图的存储n n3.边带权值的图的存储边带权值的图的存储uu1）在邻接矩阵中的实现）在邻接矩阵中的实现0 2 3 520 1 031 0 15 0 1 0a44=a44=a i j

12、a i j：记录边的权值；为：记录边的权值；为：记录边的权值；为：记录边的权值；为0 0表示无边表示无边表示无边表示无边12432 23 35 51 11 1本讲稿第十五页，共五十页图的存储图的存储n n3.边带权值的图的存储边带权值的图的存储uu2）在邻接表中的实现）在邻接表中的实现在邻接结点结构中增加一个权值域在邻接结点结构中增加一个权值域1 data2data3data4data233211354102331顶点号顶点号边权值边权值1 12 24 43 33 32 25 51 11 110103 3本讲稿第十六页，共五十页图的遍历图的遍历n3.6.3 图的遍历图的遍历n n问题：问题：u

13、u1）对于连通图，从一个顶点出发沿着所有可能）对于连通图，从一个顶点出发沿着所有可能的路径，是否可以将所有的顶点遍历到。的路径，是否可以将所有的顶点遍历到。uu2）图中有回路，遍历算法可能产生死循环。）图中有回路，遍历算法可能产生死循环。n n有重复的路径称为有重复的路径称为回路回路2143本讲稿第十七页，共五十页图的遍历图的遍历 深优深优n n1.深度优先遍历深度优先遍历uu（1）从一个未访问过的顶点开始，访问它的一个）从一个未访问过的顶点开始，访问它的一个未访问过的相邻顶点。未访问过的相邻顶点。uu（2）如果顶点的所有相邻顶点都是已访问过的，）如果顶点的所有相邻顶点都是已访问过的，则需要回

14、溯到之前的一个顶点，选取它的另一个则需要回溯到之前的一个顶点，选取它的另一个未被访问的相邻顶点。未被访问的相邻顶点。uu（3）对于前两个步骤是递归的）对于前两个步骤是递归的本讲稿第十八页，共五十页图的遍历图的遍历 深优深优n n1.深度优先遍历深度优先遍历uu（1）从一个未访问过的顶点开始，访问它的一个）从一个未访问过的顶点开始，访问它的一个未访问过的相邻顶点。未访问过的相邻顶点。uu（2）如果顶点的所有相邻顶点都是已访问过的，）如果顶点的所有相邻顶点都是已访问过的，则需要回溯到之前的一个顶点，选取它的另一个则需要回溯到之前的一个顶点，选取它的另一个未被访问的相邻顶点。未被访问的相邻顶点。uu

15、（3）对于前两个步骤是递归的）对于前两个步骤是递归的1258463717365284回到回到8173652841 3 6 8 4 2 5 7或者按以下顺序遍历：或者按以下顺序遍历：或者按以下顺序遍历：或者按以下顺序遍历：注意使用栈支持递归：注意使用栈支持递归：注意使用栈支持递归：注意使用栈支持递归：本讲稿第十九页，共五十页图的遍历图的遍历 深优深优n n深度优先遍历的特点深度优先遍历的特点uu“深度深度”：总是访问顶点的：总是访问顶点的一个一个相邻顶点，好像相邻顶点，好像是沿着图中的一条路径走到是沿着图中的一条路径走到“底底”，然后后退一，然后后退一点，再选一条路。如此点，再选一条路。如此“进

16、进退退进进退退”，直到所有，直到所有顶点都被访问顶点都被访问uu对于连通图，如果第一个被访问的顶点的所有相对于连通图，如果第一个被访问的顶点的所有相邻顶点都被访问了，意味着图中所有顶点都被访邻顶点都被访问了，意味着图中所有顶点都被访问了。问了。即栈空时即栈空时本讲稿第二十页，共五十页图的遍历图的遍历 深优深优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_ind

17、ex;if(visitedw=0)p=p-next_adj;2 2取得顶点的一个未被访问过的顶点取得顶点的一个未被访问过的顶点取得顶点的一个未被访问过的顶点取得顶点的一个未被访问过的顶点ww；3 dfs3 dfs（g g，ww）；回到）；回到）；回到）；回到2 2；4 4重复重复重复重复2 2，3 3直到该顶点所有的相邻顶点都被访问过；直到该顶点所有的相邻顶点都被访问过；直到该顶点所有的相邻顶点都被访问过；直到该顶点所有的相邻顶点都被访问过；dfs(g,w);本讲稿第二十一页，共五十页12345void dfs（g，v）visited v =1;p=g v-next_adj while(p!=

18、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;

19、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

20、(visited 5 =0)dfs(g,5);本讲稿第二十二页，共五十页图的遍历图的遍历 广优广优n n2.广度优先遍历广度优先遍历uu访问顶点访问顶点v后，接着依次访问后，接着依次访问v的所有邻接顶点，的所有邻接顶点，再依次访问这些邻接顶点的邻接顶点。直到所有再依次访问这些邻接顶点的邻接顶点。直到所有的顶点都被访问过。的顶点都被访问过。125846371 12 23 34 45 56 67 78 8注意：注意：注意：注意：8 8是作为哪个顶是作为哪个顶是作为哪个顶是作为哪个顶点的邻接顶点被访问点的邻接顶点被访问点的邻接顶点被访问点的邻接顶点被访问的？的？的？的？1 12 23 34 45 5

21、6 67 78 8体会队列操作方式：体会队列操作方式：体会队列操作方式：体会队列操作方式：本讲稿第二十三页，共五十页图的遍历图的遍历 广优广优n n广度优先遍历的特点广度优先遍历的特点uu“广度广度”：总是在访问了一个顶点后，依次访问：总是在访问了一个顶点后，依次访问它的所有相邻顶点。然后再从它的第一个相邻顶它的所有相邻顶点。然后再从它的第一个相邻顶点开始，访问其所有的相邻顶点。如此逐个顶点点开始，访问其所有的相邻顶点。如此逐个顶点地逐步扩散，直到所有的顶点都被访问。地逐步扩散，直到所有的顶点都被访问。uu广度优先遍历操作具有队列操作的特点，当从队广度优先遍历操作具有队列操作的特点，当从队列中

22、取出最后一个顶点，发现该顶点的所有相邻列中取出最后一个顶点，发现该顶点的所有相邻顶点都被访问过时，意味着图中所有的顶点都已顶点都被访问过时，意味着图中所有的顶点都已被访问过被访问过本讲稿第二十四页，共五十页生成树与图生成树与图n n3.6.4 图的应用图的应用n n1.生成树定义生成树定义uu假设存在这样一颗树：假设存在这样一颗树：假设存在这样一颗树：假设存在这样一颗树：树结点的集合与图的顶点集合相等树结点的集合与图的顶点集合相等树结点的集合与图的顶点集合相等树结点的集合与图的顶点集合相等树的分支全部由图的边组成。树的分支全部由图的边组成。树的分支全部由图的边组成。树的分支全部由图的边组成。称

23、这颗树是这幅称这颗树是这幅称这颗树是这幅称这颗树是这幅图的生成树图的生成树图的生成树图的生成树uu生成树是图的生成树是图的生成树是图的生成树是图的:子集子集子集子集/子图子图子图子图是一个不包含回路的子图是一个不包含回路的子图是一个不包含回路的子图是一个不包含回路的子图图的生成树是图的生成树是图的生成树是图的生成树是2 21 14 43 3214321432143不唯一的！不唯一的！不唯一的！不唯一的！唯一的！唯一的！唯一的！唯一的！取决于遍历方法和遍历的起始点取决于遍历方法和遍历的起始点本讲稿第二十五页，共五十页生成树的示例生成树与图生成树与图对于一个有对于一个有n个顶点个顶点的连通图的连通

24、图G，其生成树包含了其生成树包含了 条边。条边。深度优先搜索得到的生成树深度优先搜索得到的生成树广度优先搜索得到的生成树广度优先搜索得到的生成树n1本讲稿第二十六页，共五十页权值权值权值权值生成树与图生成树与图n n2.最小费用生成树（最小费用生成树（通信网络、交通网络）uu在图所有生成树中，边的权值总和最小的生成树在图所有生成树中，边的权值总和最小的生成树1245636536642416124563边边边边1 13 31 14 46 62 22 25 53 31 14 44 43 36 64 42 23 35 51 12 26 63 35 56 65 56 66 6将边按将边按将边按将边按权

25、值大权值大权值大权值大小排列小排列小排列小排列本讲稿第二十七页，共五十页生成树与图生成树与图n n算法分析算法分析uu关键技术：关键技术：关键技术：关键技术：为什么在（为什么在（为什么在（为什么在（1,41,4）边选中后不能选（）边选中后不能选（）边选中后不能选（）边选中后不能选（3,63,6）边）边）边）边在选择（在选择（在选择（在选择（3,63,6）边和（）边和（）边和（）边和（2,32,3）边时有什么不同，怎样设置条件以区）边时有什么不同，怎样设置条件以区）边时有什么不同，怎样设置条件以区）边时有什么不同，怎样设置条件以区别？别？别？别？vv当时当时当时当时3 3和和和和6 6位于同一图

26、中，位于同一图中，位于同一图中，位于同一图中，2 2、5 5和和和和3 3位于不同的图中位于不同的图中位于不同的图中位于不同的图中12456365366424161245631 14 44 43 36 64 42 23 35 5回路回路回路回路本讲稿第二十八页，共五十页生成树与图生成树与图1245631 1）开始时所有的节点都位于不同的图中）开始时所有的节点都位于不同的图中）开始时所有的节点都位于不同的图中）开始时所有的节点都位于不同的图中2 2）选择一条连接两个不同子图的最短边）选择一条连接两个不同子图的最短边）选择一条连接两个不同子图的最短边）选择一条连接两个不同子图的最短边3 3）连接以

27、后两个子图的所有顶点都要改为）连接以后两个子图的所有顶点都要改为）连接以后两个子图的所有顶点都要改为）连接以后两个子图的所有顶点都要改为 在一个子图中在一个子图中在一个子图中在一个子图中4 4）当所有的顶点都位于一个子图中，）当所有的顶点都位于一个子图中，）当所有的顶点都位于一个子图中，）当所有的顶点都位于一个子图中，算法结束。算法结束。算法结束。算法结束。权值权值权值权值边边边边1 13 31 14 46 62 22 25 53 31 14 44 43 36 64 42 23 35 51 12 26 6思考思考思考思考既然是颗树，如果选择边数为既然是颗树，如果选择边数为既然是颗树，如果选择边

28、数为既然是颗树，如果选择边数为n n1 1个时个时个时个时可不可以结束算法呢？可不可以结束算法呢？可不可以结束算法呢？可不可以结束算法呢？算法的优化算法的优化算法的优化算法的优化本讲稿第二十九页，共五十页图的最短路径图的最短路径n n3.最短路径最短路径uu图中两个顶点之间有图中两个顶点之间有 条路径条路径uu最短路径：最短路径：是路径中边（弧）的权值总和最小的路径是路径中边（弧）的权值总和最小的路径uu计算机网络中常使用最短路径算法计算最佳路径计算机网络中常使用最短路径算法计算最佳路径uu交通网络中使用最短路径算法计算最短旅途交通网络中使用最短路径算法计算最短旅途多多多多Dijkstra A

29、lgorithmDijkstra AlgorithmFloyd AlgorithmFloyd Algorithm本讲稿第三十页，共五十页A1A2A4A3A526512151 1）初始化时，设）初始化时，设）初始化时，设）初始化时，设A1A1到其它不直连顶点距离为到其它不直连顶点距离为到其它不直连顶点距离为到其它不直连顶点距离为 寻找寻找A1到所有节点的最短路径到所有节点的最短路径A2A3A4A5顶点顶点距离距离路径路径2 2）选择距离最短的路径）选择距离最短的路径）选择距离最短的路径）选择距离最短的路径3 3）观察通过新选择的路径是否能更短）观察通过新选择的路径是否能更短）观察通过新选择的路径

30、是否能更短）观察通过新选择的路径是否能更短地到达其它顶点地到达其它顶点地到达其它顶点地到达其它顶点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 更新更新D

31、ijkstra Algorithm本讲稿第三十一页，共五十页拓拓 扑扑 排排 序序按一定顺序进行的活动，可以使用顶点表示活动、顶点之间的有向边表示活动间的先后关系的有向图来表示，这种有向图称为顶点表示活动网络(ActivityOnVertexnetwork，简称AOV网网)。AOV网中的有向边表示了活动之间的制约关系。4.拓拓 扑扑 排排 序序本讲稿第三十二页，共五十页将AOV网中的所有顶点排列成一个线性序列vi1,vi2,vin，并且这个序列同时满足关系：若在AOV网中从顶点vi到顶点vj存在一条路径，则在线性序列中vi必在vj之前，我们就称这个线性序列为拓拓扑扑序序列列。把对AOV网构造拓

32、扑序列的操作称为拓扑排序。拓扑排序。在实际的意义上，AOV网中存在的有向环就意味着某些活动是以自己为先决条件，这显然是荒谬的。例如对于程序的数据流图而言，AOV网中存在环就意味着程序存在一个死循环。本讲稿第三十三页，共五十页任何一个无环的AOV网中的所有顶点都可排列在一个拓扑序列里，拓扑排序的基本操作如下：(1)从网中选择一个入度为0的顶点并且输出它。(2)从网中删除此顶点及所有由它发出的边。(3)重复上述两步，直到网中再没有入度为0的顶点为止。本讲稿第三十四页，共五十页本讲稿第三十五页，共五十页n 以上的操作会产生两种结果：以上的操作会产生两种结果：n一种是网中的全部顶点都被输出，整个拓扑排

33、序完成；一种是网中的全部顶点都被输出，整个拓扑排序完成；n另另一一种种是是网网中中顶顶点点未未被被全全部部输输出出，剩剩余余的的顶顶点点的的入入度度均均不不为为0，则则说说明网中存在有向环。明网中存在有向环。n用以上操得到了一种拓扑序列：用以上操得到了一种拓扑序列：nC1,C2,C3,C4,C5,C7,C9,C10,C12,C11,C6,C8。n拓扑序列可以是种多本讲稿第三十六页，共五十页AOV网拓扑排序过程本讲稿第三十七页，共五十页在邻接表存储结构中实现拓扑排序算法的步骤为：在邻接表存储结构中实现拓扑排序算法的步骤为：(1)扫描顶点表，将入度为0的顶点入栈。(2)当栈非空时执行以下操作：将栈

34、顶顶点vi的序号弹出，并输出之；检查vi的出边表，将每条出边表邻接点域所对应的顶点的入度域值减1，若该顶点入度为0，则将其入栈；(3)若输出的顶点数小于n，则输出“有回路”，否则拓扑排序正常结束。本讲稿第三十八页，共五十页关关 键键 路路 径径5.关键路径关键路径AOE网络(Activity On Edge network)：有向边：表示一个子工程（活动）有向边：表示一个子工程（活动）边上的权值：表示一个活动持续的时间边上的权值：表示一个活动持续的时间顶顶点点：表表示示事事件件，它它表表示示了了一一种种状状态态，即即它它的的入入边边所所表表示示的的活活动动均均已已完成，它的出边所表示的活动可以

35、开始。完成，它的出边所表示的活动可以开始。这这种种带带权权的的有有向向网网络络称称为为 AOE网网络络(Activity On Edge network)，即即边表示活动网络。边表示活动网络。本讲稿第三十九页，共五十页一个AOE网络的示例本讲稿第四十页，共五十页关键路径：关键路径：从源点到汇点的具有最大路径长度的路径。从源点到汇点的具有最大路径长度的路径。关键活动：关键活动：关键路径上的各个活动。关键路径上的各个活动。明明确确了了哪哪些些活活动动是是关关键键活活动动就就可可以以设设法法提提高高关关键键活活动动的的功功效效，以以便便缩缩短短整整个工期。个工期。本讲稿第四十一页，共五十页其中E1是

36、网络中以vj为终点的入边集合，dur()是有向边上的权值。vl l(j)(j)的计算可从汇点开始，向源点逆推计算：的计算可从汇点开始，向源点逆推计算：(13.2)其中E2是网络中以vj为起点的出边集合。(1)(2)ve(j)的计算可从从源点源点开始开始利用以下的递推公式求得本讲稿第四十二页，共五十页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,

37、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网各个事件的最早发生时间和最迟发生时间：本讲稿第四十三页，共五十页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()=min

38、73,147=4vl(2)=minvl(4)dur(),vl(5)dur()=min74,118=3vl(1)=minvl(2)dur(),vl(3)dur()=min33,42=0本讲稿第四十四页，共五十页利用利用 ve(i)=e(i)和和l(i)=vl(k)dur()网络的关键路径本讲稿第四十五页，共五十页关键活动算法主要由以下步骤组成：关键活动算法主要由以下步骤组成：(1)对AOE网进行拓扑排序，同时按拓扑排序顺序求出各顶点事件的最早发生时间ve，若网中有回路，则算法终止，否则执行(2)。(2)按拓扑序列的逆序求出各顶点事件的最迟发生时间vl。(3)根据ve和vl的值求出ai的最早开始时间e(i)和最迟开始时间l(i)。若l(i)=e(i)，则ai为关键活动。因为计算各顶点的ve值是在拓扑排序的过程中进行的，所以可通过对拓扑排序算法进行一些修正来实现求关键路径的算法。本讲稿第四十六页，共五十页作业作业本讲稿第四十七页，共五十页本讲稿第四十八页，共五十页一个网络及其邻接矩阵本讲稿第四十九页，共五十页Kruskal算法构造最小生成树的过程本讲稿第五十页，共五十页