数据结构课件第七章图2

1、第七章图 深度优先搜索遍历算法及广度优先搜索遍历算深度优先搜索遍历算法及广度优先搜索遍历算法中遍历图过程中历经边的集合和顶点集合一起构法中遍历图过程中历经边的集合和顶点集合一起构成连通图的成连通图的极小连通子图极小连通子图。它是连通图的一颗生成。它是连通图的一颗生成树。树。生成树：生成树：是一个极小连通子图，它含有图中全部顶是一个极小连通子图，它含有图中全部顶点，但只有点，但只有n-1条边。条边。 由深度优先搜索遍历得到的生成树，称为由深度优先搜索遍历得到的生成树，称为深度深度优先生成树优先生成树，由广度优先搜索遍历得到的生成树，由广度优先搜索遍历得到的生成树，称为称为广度优先生成树广度优先生

2、成树。7.4.1 生成树及生成森林生成树及生成森林7.4 最小生成树最小生成树v0v1v3v4v2v6v5v7v0v1v3v4v2v6v5v7深度优先生成树深度优先生成树v0v1v3v4v2v6v5v7广度优先生成树广度优先生成树v0v1v3v4v2v6v5v7深度遍历：深度遍历：v0 v1 v3 v7 v4 v2 v5 v6广度遍历：广度遍历：v0 v1 v2 v3 v4 v5 v6 v7v0v1v3v4v2v6v5v7第七章图生成森林：生成森林：若一个图是非连通图，但有若干个连通分量，则若一个图是非连通图，但有若干个连通分量，则通过深度优先搜索遍历或广度优先搜索遍历，不可以通过深度优先搜索

3、遍历或广度优先搜索遍历，不可以得到生成树，但可以得到生成森林，且若非连通图有得到生成树，但可以得到生成森林，且若非连通图有n个顶点，个顶点，m个连通分量，则可以遍历得到个连通分量，则可以遍历得到m棵生成棵生成树，合起来为树，合起来为生成森林生成森林，森林中包含，森林中包含n-m条树边。条树边。 ablmcfdeghkijablmcfjdeghki深度优先生成森林深度优先生成森林第七章图n 说明说明: :v 一个图可以有许多棵一个图可以有许多棵不同不同的生成树的生成树v 所有生成树具有以下共同特点：所有生成树具有以下共同特点：l 生成树的顶点个数与图的顶点个数相同生成树的顶点个数与图的顶点个数相

4、同l 生成树是图的极小连通子图生成树是图的极小连通子图l 一个有一个有n个顶点的连通图的生成树有个顶点的连通图的生成树有n-1条边条边l在生成树中再加一条边必然形成回路在生成树中再加一条边必然形成回路l生成树中任意两个顶点间的路径是唯一的生成树中任意两个顶点间的路径是唯一的v 含含n个顶点个顶点n-1条边的图不一定是生成树条边的图不一定是生成树第七章图7.4.2 7.4.2 最小生成树最小生成树1、最小生成树、最小生成树 对于带权的连通图对于带权的连通图g，其生成树也是带权的。我，其生成树也是带权的。我们把生成树各边的权值总和称为该们把生成树各边的权值总和称为该生成树的权生成树的权。并且。并且

5、将权最小的生成树称为将权最小的生成树称为最小生成树最小生成树。2. 求最小生成树求最小生成树首先明确：首先明确： 使用不同的遍历图的方法，可以得到不同的生成树；使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。从不同的顶点出发，也可能得到不同的生成树。 按照生成树的定义，按照生成树的定义，n n 个顶点的个顶点的连通网络连通网络的生成树有的生成树有 n n 个顶点、个顶点、n-n-1 1 条边。条边。即有权图即有权图第七章图目标：目标： 在网络的多个生成树中，寻找一个各边权值在网络的多个生成树中，寻找一个各边权值之和最小的生成树。之和最小的生成树。构造最小

6、生成树的准则构造最小生成树的准则v必须只使用该网络中的边来构造最小生成树；必须只使用该网络中的边来构造最小生成树；v必须使用且仅使用必须使用且仅使用n n-1-1条边条边来联结网络中的来联结网络中的n n个个顶点；顶点；v不能使用产生回路的边不能使用产生回路的边。第七章图1、问题提出、问题提出要在要在n个城市间建立通信联络网，个城市间建立通信联络网， n个城市间，最多可设置个城市间，最多可设置n(n-1)/2条线路；条线路； n个城市间建立通信网，只需个城市间建立通信网，只需n-1条线路；条线路； 问题转化为：如何在可能的线路中选择问题转化为：如何在可能的线路中选择n-1条，条，能把能把 所有

7、城市（顶点）均连起来，且总耗费（各边所有城市（顶点）均连起来，且总耗费（各边权值之和）最小。权值之和）最小。典型用途：典型用途：希望找到一棵生成树，它的每条边上的权值之希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小和（即建立该通信网所需花费的总代价）最小最小生成树最小生成树mst(minimum cost spanning tree)1654327131791812752410数学模型：数学模型：顶点顶点表示城市，有表示城市，有n n个；个；边边表示线路，有表示线路，有n1n1条；条；边的权值边的权值表示线路的经济代价；表示线路的经济代价；连通网连通网表示表示

8、n n个城市间通信网。个城市间通信网。2、问题分析、问题分析第七章图7.4.3 7.4.3 构造最小生成树方法构造最小生成树方法( (一一) )：primprim算算法法假设假设g=(v,e)是一个具有是一个具有n 个顶点的连通网络，个顶点的连通网络，g=(u,t)是是g的最小生成树，其中的最小生成树，其中u是是g的顶点集，的顶点集，t是是g的边集，的边集，u和和t的初值均为空。的初值均为空。1、从、从v中任取一个顶点（假定为中任取一个顶点（假定为u1），将此顶点），将此顶点并入并入u中，此时最小生成树顶点集中，此时最小生成树顶点集u=u1；2、从那些、从那些其一个端点已在其一个端点已在u中中

9、，另一个端点仍在另一个端点仍在u外外(v-u)的所有边中，找一条最短（即权值最小）的所有边中，找一条最短（即权值最小）的边，假定该边为的边，假定该边为(u,v),其中其中uu，v (v-u),并把并把该边该边(u,v)和顶点和顶点v分别并入分别并入g的边集的边集t和顶点集和顶点集u；第七章图3、如此进行下去，每次往生成树里并入一个顶点、如此进行下去，每次往生成树里并入一个顶点和一条边，直到和一条边，直到n-1次后，把所有次后，把所有n 个顶点都并入个顶点都并入生成树生成树g的顶点集的顶点集u中，此时中，此时u=v，t中包含有中包含有（n-1）条边；条边；这样，这样， g就是最后得到的最小生成树

10、。就是最后得到的最小生成树。普里姆算法中每次选取的边两端，总是一个已普里姆算法中每次选取的边两端，总是一个已连通顶点（在连通顶点（在u集合内）和一个未连通顶点（在集合内）和一个未连通顶点（在u集合外），故这个边选取后一定能将未连通顶点连集合外），故这个边选取后一定能将未连通顶点连通而又保证不会形成环路。通而又保证不会形成环路。7.4.3 prim7.4.3 prim算法算法primprim方法构造过程方法构造过程1654326513566425131163141643142116432142516543214253u:v-u:143256第七章图普里姆普里姆(prim)(prim)算算法法 p

11、rim算法可用下述过程描述：算法可用下述过程描述： （1）uu1，t=； （2）while （uv）do （u，v）minwuv；uu，vvu tt（u，v） uuv （3）结束。）结束。第七章图 有关数据的存储结构有关数据的存储结构设置两个辅助数组：设置两个辅助数组：lowcost用来保存集合用来保存集合vu中各顶点与集合中各顶点与集合u中各顶点构成的边中具有最小权值的边的权值；中各顶点构成的边中具有最小权值的边的权值；adjvex用来保存依附于该边的在集合用来保存依附于该边的在集合u中的顶中的顶点。点。 普里姆普里姆(prim)(prim)算算法法第七章图普里姆普里姆(prim)(prim

12、)算算法法 0 0 0 0 0 00 0 0 0 0 0 0 6 0 6 1 1 5 max max 5 max max iadjvexlowcost 0 1 2 3 4 5 iadjvexlowcost 0 1 2 3 4 5 0 2 0 0 2 20 2 0 0 2 2 0 5 0 5 6 0 5 0 5 6 4 4u= v0u= v0,v2v v2 2v v0 0v v3 3v v5 5v v4 4v v1 uv v2 2v v0 0v v3 3v v5 5v v4 4v v1 uv-u= v1,v2,v3,v4,v5 v-u= v1,

13、 v3,v4,v5 第七章图普里姆普里姆(prim)(prim)算算法法 0 0 0 0 0 00 0 0 0 0 0 0 6 0 6 1 1 5 max max 5 max max lowcostlowcost00 0 2 0 0 2 20 2 0 0 2 2 0 5 0 5 6 0 5 0 5 6 4 4 adjvexadjvexlowcostlowcost0,20,2 0 2 0 5 2 20 2 0 5 2 2 0 5 0 0 5 0 2 2 6 0 6 0 adjvexlowcostlowcost0,2,50,2,5 0 2 0 5 2 20 2 0 5 2 2 0 0 5 5 0

14、0 6 0 0 0 6 0 adjvexadjvexlowcostlowcost0,2,5,30,2,5,3 0 2 0 5 1 20 2 0 5 1 2 0 0 0 0 0 0 0 0 3 3 0 0 adjvex adjvexlowcostlowcost0,2,5,3,10,2,5,3,1 0 2 0 5 1 20 2 0 5 1 2 0 0 0 0 0 0 0 0 0 0 0 0 adjvexlowcostlowcost0,2,5,3,1,40,2,5,3,1,4i iadjvexadjvex 0 1 2 3 4 5 0 1 2 3 4 5 u u第七章图7.4.4 7.4.4 构造最小

15、生成树方法（二）：构造最小生成树方法（二）：kruskalkruskal算法算法假设假设g =（v，e）是一个具有）是一个具有n个顶点的连通网络，个顶点的连通网络， g=(u,t)是是g 的最小生成树，的最小生成树，u的初值等于的初值等于v，即包含有，即包含有g中的全部顶点，中的全部顶点，t的初值为空集。的初值为空集。基本思想：将图基本思想：将图g中的边按权值中的边按权值从小到大的顺序从小到大的顺序依次选依次选取，若选取的边使生成树取，若选取的边使生成树g不形成环路不形成环路，则把它并入，则把它并入t中，保留作为生成树中，保留作为生成树g的一条边，若选取的边使生成树的一条边，若选取的边使生成树

16、g形成环路，则将其舍弃，如此进行下去，直到形成环路，则将其舍弃，如此进行下去，直到t中包中包含含n-1条边为止。此时的条边为止。此时的t即为最小生成树。即为最小生成树。第七章图1654326513566425165432135427.4.4 克鲁斯卡尔克鲁斯卡尔(kruskal)算法算法第七章图克鲁斯卡尔克鲁斯卡尔算算法法 有关数据的存储结构有关数据的存储结构设置一个结构设置一个结构数组数组arr存储网中所有的边，边的结构存储网中所有的边，边的结构类型包括构成的顶点信息和边权值类型包括构成的顶点信息和边权值 。#define maxedge typedef struct int v1, v2；

17、int cost； edgenode；edgenode arrmaxedge； 事先把数组事先把数组arr中的各元素按照其中的各元素按照其cost域值由小到大域值由小到大的顺序排列。的顺序排列。第七章图 设置一个设置一个数组数组fn，其初值为，其初值为fi=i，表示各个顶，表示各个顶点在点在不同的连通分量不同的连通分量上。然后，依次取出上。然后，依次取出arr数组中数组中的每条边的两个顶点，查找它们所属的连通分量，的每条边的两个顶点，查找它们所属的连通分量，设设u1和和u2为两顶点所在的树的根结点在为两顶点所在的树的根结点在f中的序号中的序号，若，若u1不等于不等于u2，表明这条边的两个顶点不

18、属于同，表明这条边的两个顶点不属于同连通一分量，则将这条边作为最小生成树的边输出连通一分量，则将这条边作为最小生成树的边输出，并合并它们所属的两个连通分量。，并合并它们所属的两个连通分量。克鲁斯卡尔克鲁斯卡尔算算法法第七章图克鲁斯卡尔克鲁斯卡尔算算法法void kruskal(edgetype arr,int n)for (i=0;in;i+) fi=i;i=0;j=0;while(imaxedge & jn-1) u1=farri.v1;u2=farri.v2;if (u1!=u2)fu2=u1;i+;printf(%3d%3dn,arri.v1,arri.v2);j+;初始化根结点数组初始

19、化根结点数组依次搜索每条边的两个依次搜索每条边的两个顶点所在树的根结点顶点所在树的根结点不属于同一连通不属于同一连通分量，合并，把分量，合并，把u1作为作为u2的根的根即把顶点即把顶点v1根（根（u1）作为顶点）作为顶点v2 根（根（u2）的根结点）的根结点演演 示示第七章图1 1、问题提出与数学模型、问题提出与数学模型问题：在一个交通网络中，如何找到城市问题：在一个交通网络中，如何找到城市a a到城市到城市b b之间一条距离最近或花费最少的通路？之间一条距离最近或花费最少的通路？ 用带权的有向图表示一个交通运输网，图中：用带权的有向图表示一个交通运输网，图中： 顶点顶点表示城市表示城市 边边

20、表示城市间的交通联系表示城市间的交通联系 权权表示此线路的长度或所花费的代价表示此线路的长度或所花费的代价数学模型：数学模型： 从某顶点出发，沿图的边到达另一顶点所经过从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径的路径中，各边上权值之和最小的一条路径最最短路径短路径第七章图51643208562301371732913长度长度最短路径最短路径813192120注：最短路径与最小生成树不同，路径上不一定包含注：最短路径与最小生成树不同，路径上不一定包含n个顶点。个顶点。第七章图两种最常见的最短路径问题：两种最常见的最短路径问题：一顶点到其余各顶点的最短路径一顶点

21、到其余各顶点的最短路径单源点最短路径用单源点最短路径用dijkstra算法算法任意两顶点间的最短路径任意两顶点间的最短路径所有顶点间的最短路径用所有顶点间的最短路径用floyd算法算法第七章图1、迪杰斯特拉、迪杰斯特拉(dijkstra)算法思想算法思想按按路径长度递增次序路径长度递增次序产生最短路径算法：产生最短路径算法：把把v分成两组：分成两组：（1）s：已求出最短路径的顶点的集合；：已求出最短路径的顶点的集合；（2） t = v-s：尚未确定最短路径的顶点集合：尚未确定最短路径的顶点集合。 将将t中顶点按最短路径递增的次序加入到中顶点按最短路径递增的次序加入到s中中。7.5.1 从某个源

22、点到其余各顶点的最短路径从某个源点到其余各顶点的最短路径(1)单源点最短路径：单源点最短路径：是指给定一个出发点（单源点）是指给定一个出发点（单源点）和一个有向网和一个有向网g=(v,e)，求出源点到其它各顶点之，求出源点到其它各顶点之间的最短路径。间的最短路径。第七章图2、求最短路径步骤、求最短路径步骤采用邻接矩阵采用邻接矩阵costnn来存储带权有向图。来存储带权有向图。1)令令 s=v0,t=其余顶点其余顶点， t中顶点对应的距离值中顶点对应的距离值:若存在若存在，为，为弧上的权值弧上的权值，若不存在若不存在，为为 。2)从从t中选取一个其距离值为最小的顶点中选取一个其距离值为最小的顶点

23、w，加入，加入s。3)对对t中顶点的距离值进行修改：若加进中顶点的距离值进行修改：若加进w作中间顶作中间顶点，从点，从v0到到vi的距离值比不加的距离值比不加w的路径要的路径要长长，则修改此，则修改此距离值距离值。4)重复上述步骤，直到重复上述步骤，直到s中包含所有顶点，即中包含所有顶点，即s=v为止为止7.5.1 从某个源点到其余各顶点的最短路径从某个源点到其余各顶点的最短路径(2)138 30 32v2:813-1330 32v1:13-13302220v3:13-192220v4:19终点终点 从从v0到各终点的最短路径及其长度到各终点的最短路径及其长度v1v2v3v4v5v6vj-21

24、20v6:20516432085623013717329dijkstradijkstra算法算法求最短路径的过程求最短路径的过程 sv0,v2 v0,v2,v1v0,v2,v1,v3v0,v2,v1,v3,v4v0,v2,v1,v3,v4,v6第七章图顶点对之间的最短路径概念顶点对之间的最短路径概念 所有顶点对之间的最短路径是指：对于给定的有所有顶点对之间的最短路径是指：对于给定的有向网向网g=(v,e),要对要对g中任意一对顶点有序对中任意一对顶点有序对u、v(uv),找出找出u到到v的最短距离。的最短距离。解决此问题的一个有效方法是解决此问题的一个有效方法是:轮流以每一个顶轮流以每一个顶点

25、为源点点为源点,重复执行迪杰斯特拉算法重复执行迪杰斯特拉算法n次次,即可求得每一即可求得每一对顶点之间的最短路径对顶点之间的最短路径,总的时间复杂度为总的时间复杂度为o(n3)。下面将介绍用弗洛伊德下面将介绍用弗洛伊德(floyd)算法来实现此功能算法来实现此功能,时间复杂度仍为时间复杂度仍为o(n3),但该方法比调用但该方法比调用n次迪杰斯特拉次迪杰斯特拉方法更直观一些。方法更直观一些。7.5.2 7.5.2 所有顶点对之间的最短路径所有顶点对之间的最短路径第七章图采用邻接矩阵采用邻接矩阵costnn来存储带权有向图。来存储带权有向图。算法的基本思想算法的基本思想是是: 设置一个设置一个n*

26、n的矩阵的矩阵ann，其中除对角线的元素都等于，其中除对角线的元素都等于0外，其它元素外，其它元素aij的值表示顶点的值表示顶点i到顶点到顶点j的最短路径长度。的最短路径长度。运算步骤为：运算步骤为：首先，以任意两个顶点之间的有向边的权值作为首先，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为路径长度，没有有向边时，路径长度为，此时，此时, a ij=costij, 以后逐步尝试在原路径中加入其它顶点作为中间顶点，如以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则果增加中间顶点后，得到的路径比原来的路径长度减少了，

27、则以此新路径代替原路径，修改矩阵元素。以此新路径代替原路径，修改矩阵元素。弗洛伊德算法弗洛伊德算法(1)(1)第七章图具体做法为：具体做法为： 第一步，让所有边上加入中间顶点第一步，让所有边上加入中间顶点v0，取，取aij与与ai0+a0j中较小的值作中较小的值作aij的值的值.第二步，让所有边上加入中间顶点第二步，让所有边上加入中间顶点v1，取，取aij与与ai1+a1j中较小的值，为中较小的值，为aij 的值，的值，如此进行下去，当第如此进行下去，当第n步完成后，得到步完成后，得到 aij ,即为我们即为我们所求结果所求结果, a ij表示顶点表示顶点i到顶点到顶点j的最短距离。的最短距离

28、。因此，弗洛伊德算法可以描述为因此，弗洛伊德算法可以描述为: a(-1)ij=costij; /cost为图的邻接矩阵为图的邻接矩阵 a(k)ij=mina(k-1) ij, a(k-1) ik+a(k-1) kj其中其中 k=0,1,2, n-1弗洛伊德算法弗洛伊德算法(2)(2)第七章图d(-1)012041160230p(-1)012abacbabccad012p012d(0)0120411602370p(0)012abacbabcca cabd(1)012046602370p(1)012ab abcbabcca cabd(2)012046502370p(2)012ab abcbcabc

29、ca cabv1v2v0642113acb弗洛伊德弗洛伊德算法算法求最短路径的过程求最短路径的过程第七章图7.6.1 7.6.1 有向无环图的概念有向无环图的概念 一个一个无环的有向图无环的有向图称做有向无环图（称做有向无环图（directed directed acyclineacycline graph graph），简称），简称dagdag图。下面是有向树、图。下面是有向树、dag图和有向图的例子。图和有向图的例子。 有向树有向树 dag图图 有向图有向图第七章图检查一个有向图是否存在环要比无向图复杂。检查一个有向图是否存在环要比无向图复杂。对于无向图来说，若深度优先遍历过程中对于无向图

30、来说，若深度优先遍历过程中遇到遇到回边回边( (指向已访问过的顶点的边指向已访问过的顶点的边) )，则必定存在环；，则必定存在环；而对于有向图来说，这条回边很有可能不构成而对于有向图来说，这条回边很有可能不构成环，它有可能是指向深度优先生成森林中另一棵生环，它有可能是指向深度优先生成森林中另一棵生成树上顶点的弧。但是，如果从有向图上某个顶点成树上顶点的弧。但是，如果从有向图上某个顶点v 出发的遍历，出发的遍历，在在dfs（v）结束之前出现一条从顶点）结束之前出现一条从顶点u到顶点到顶点v的回边的回边，由于，由于u 在生成树上是在生成树上是v的子孙，则的子孙，则有向图必定存在包含顶点有向图必定存

31、在包含顶点v和和u的环。的环。 第七章图有向无环图也是描述一项工程或系统的进行过程的有有向无环图也是描述一项工程或系统的进行过程的有效工具。几乎所有的效工具。几乎所有的工程（工程（project）都可分为若干个称作都可分为若干个称作活动（活动（activity）的子工程，而这些子工程之间，通常受）的子工程，而这些子工程之间，通常受着一定条件的约束，如其中某些子工程的开始必须在另一着一定条件的约束，如其中某些子工程的开始必须在另一些子工程完成之后。些子工程完成之后。对整个工程和系统，人们关心的是两个方面的问题：对整个工程和系统，人们关心的是两个方面的问题：一是工程能否顺利进行：一是工程能否顺利进

32、行：二是估算整个工程完成所必须的最短时间。二是估算整个工程完成所必须的最短时间。 下面我们通过对有向图进行下面我们通过对有向图进行拓扑排序拓扑排序和和关键路径关键路径操作操作来解决这两个问题。来解决这两个问题。 第七章图1、aov网：网：在一个有向图中，若用顶点表示活动，有向边表在一个有向图中，若用顶点表示活动，有向边表示活动间先后关系，称该有向图叫做示活动间先后关系，称该有向图叫做顶点表示活动的顶点表示活动的网络网络(activity on vertex network)简称为简称为aov网。网。在工程实践中，一个工程项目往往由若干个子项在工程实践中，一个工程项目往往由若干个子项目组成，这些

33、子项目间往往有多种关系：目组成，这些子项目间往往有多种关系：先后关系先后关系子项目之间无次序要求。子项目之间无次序要求。如果从顶点如果从顶点vi到到vj之间存在有向边之间存在有向边,则表则表示活动示活动i必须先于活动必须先于活动j进行。进行。 7.6.2 aov网与拓扑排序网与拓扑排序第七章图 在在aov网络中，如果顶点网络中，如果顶点vi的活动必须在顶点的活动必须在顶点vj的的活动以前进行，则称活动以前进行，则称vi为为vj的前趋顶点，而称的前趋顶点，而称vj为为vi的的后继顶点。这种前趋后继关系有传递性。后继顶点。这种前趋后继关系有传递性。 aov网络中网络中一定不能有有向环路一定不能有有

34、向环路。例如在下图那。例如在下图那样的有向环路中，样的有向环路中，v0是是v1的前趋顶点，的前趋顶点，v1是是v2的前趋顶的前趋顶点，点，v2是是v3的前趋顶点，的前趋顶点， v3又是又是v0的前趋顶点，环路表的前趋顶点，环路表示顶点之间的先后关系进入了死循环。示顶点之间的先后关系进入了死循环。 因此，对给定的因此，对给定的aov网络网络首先要判定网络中是否首先要判定网络中是否存在环路存在环路，只有有向无环路网络在应用中才有实际意义。，只有有向无环路网络在应用中才有实际意义。v3v2v0v1 7.6.2 aov网与拓扑排序网与拓扑排序第七章图课程流程图课程流程图c1c2c3c4c5c6c7c8

35、c9c10c11c12程序设计程序设计离散数学离散数学数据结构数据结构汇编语言汇编语言算法分析算法分析计算机体系计算机体系编译方法编译方法操作系统操作系统高等数学高等数学线性代数线性代数电子电路电子电路数值分析数值分析无无 c1c1,c2c1c3,c4c11c5,c3c3,c6无无c9c9c9,c10,c1课程编号课程编号 课程名称课程名称 先决条件先决条件 c4c1c2c3c12c9c10c11c6c7c8c5有一些课程必须在先学完某些先有一些课程必须在先学完某些先修课程之后才能开始学习。如修课程之后才能开始学习。如数据结构数据结构就必须安排在就必须安排在离离散数学散数学和和程序设计程序设计

36、之后之后 。 7.6.2 aov网与拓扑排序网与拓扑排序第七章图拓扑排序的定义拓扑排序的定义给出有向图给出有向图g=(v,e)，对于，对于v中的顶点的线性序列中的顶点的线性序列(vi1,vi2,.,vin)，如果满足如下条件：若在，如果满足如下条件：若在g中从顶点中从顶点 vi 到到vj有一条路经，则在序列中顶点有一条路经，则在序列中顶点vi必在顶点必在顶点 vj之前；之前；则称该序列为则称该序列为 g的一个拓扑序列（的一个拓扑序列（topological order）。构造有向图的一个拓扑序列的过程称为）。构造有向图的一个拓扑序列的过程称为拓扑拓扑排序排序（topological sort）

37、。）。所谓所谓“拓扑排序拓扑排序”就是将就是将aov网络中的各个顶点网络中的各个顶点(各个活动各个活动)排列成一个排列成一个线性有序序列，使得所有要求线性有序序列，使得所有要求的前趋、后继关系都能得到满足。的前趋、后继关系都能得到满足。 2、拓扑排序、拓扑排序说明说明(1)在在aov网中网中, 不存在回路。不存在回路。 aov网所代表的一项工程中活动的集合，为了保网所代表的一项工程中活动的集合，为了保证该项工程得以顺利完成，必须保证证该项工程得以顺利完成，必须保证aov网中不出现网中不出现回路；否则，意味着某项活动应以自身作为能否开展的回路；否则，意味着某项活动应以自身作为能否开展的先决条件，

38、这是荒谬的。先决条件，这是荒谬的。 (2)拓扑序列不是唯一的。拓扑序列不是唯一的。 由于由于aov网络中有些顶点之间没有次序要求，它网络中有些顶点之间没有次序要求，它们在拓扑有序序列中的位置可以任意颠倒，所以拓扑们在拓扑有序序列中的位置可以任意颠倒，所以拓扑排序的结果一般排序的结果一般并不是唯一的并不是唯一的。通过拓扑排序还可以判断出此通过拓扑排序还可以判断出此aov网络是否包含网络是否包含有有向环路，若有向图有有向环路，若有向图g所有顶点都在拓扑排序序列所有顶点都在拓扑排序序列中中，则，则aov网络必定不包含有有向环路。网络必定不包含有有向环路。第七章图如图：可以得到不止一个如图：可以得到不

39、止一个拓扑排序：拓扑排序：c1-c2-c3-c4-c5-c7-c9-c10-c11-c6-c12-c8 c9-c10-c11-c6-c1-c12-c4-c2-c3-c5-c7-c8 显然，对于任何一项工程显然，对于任何一项工程中各个活动的安排，必须按拓中各个活动的安排，必须按拓扑有序序列中的顺序进行才是扑有序序列中的顺序进行才是可行的。可行的。 c4c1c2c3c12c9c10c11c6c7c8c5 2、拓扑排序、拓扑排序第七章图拓扑排序的方法拓扑排序的方法 (1) 在在aov网络中选择一个没有前趋的顶点（网络中选择一个没有前趋的顶点（入入度为度为0），并把它输出；），并把它输出； (2) 从

40、网络中删去该顶点和从该顶点发出的所有从网络中删去该顶点和从该顶点发出的所有有向边；有向边； (3) 重复执行上述两步，直到网中所有的入度为重复执行上述两步，直到网中所有的入度为0的顶点都被输出的顶点都被输出 。 如果进行到某一步，网中还有顶点，但无法找到如果进行到某一步，网中还有顶点，但无法找到无前趋的顶点（没有入度为无前趋的顶点（没有入度为0的顶点），则说明此的顶点），则说明此aov网络中存在有向环路，遇到这种情况，拓扑排序网络中存在有向环路，遇到这种情况，拓扑排序就无法进行了。就无法进行了。拓扑排序的方法拓扑排序的方法第七章图v2v3v1v4v6v5v2v2v5v2v3v5v2v3v4v6

41、v5v2v3v6v5输出输出v1输出输出v4输出输出v6输出输出v3输出输出v5aovaov网上实施步骤的例子网上实施步骤的例子输出输出v2拓扑序列为：拓扑序列为：v1,v4,v6,v3,v5,v2v2v3v1v4v6v5第七章图拓扑排序算法：拓扑排序算法：以以邻接表邻接表作存储结构，作存储结构，并且并且增加一个数据域用于记增加一个数据域用于记录顶点入度。录顶点入度。 indegreevertexfirstedgev1v2v3v4v5v60122indegreefirstedge 5 5 4 3adjvex next3 2 5 2 40123456v1v2v3v4v5v6vertextyped

42、ef struct vnodeint indegree；vertextype vertex；edgenode * firstedge；vertexnode；拓扑排序算法：拓扑排序算法：第七章图算法中可设置一个堆栈，凡是网中入度为算法中可设置一个堆栈，凡是网中入度为0 0 的顶的顶点都将其入栈。为此，拓扑排序的算法步骤为：点都将其入栈。为此，拓扑排序的算法步骤为：v 把邻接表中所有入度为把邻接表中所有入度为0（没有前驱）的顶点进（没有前驱）的顶点进栈栈v 栈非空时，输出栈顶元素栈非空时，输出栈顶元素vj并退栈；在邻接表中并退栈；在邻接表中查找查找vj的直接后继的直接后继vk，把，把vk的入度减的

43、入度减1；若；若vk的入的入度为度为0则进栈则进栈v 重复上述操作直至栈空为止。若栈空时输出的顶重复上述操作直至栈空为止。若栈空时输出的顶点个数不是点个数不是n，则有向图有环；否则，拓扑排序完毕，则有向图有环；否则，拓扑排序完毕。 拓扑排序算法拓扑排序算法第七章图注意：用邻接表作为它的存储结构，各表头结点注意：用邻接表作为它的存储结构，各表头结点的的indegree域存放相应顶点的入度值。每个顶点域存放相应顶点的入度值。每个顶点入度初值可随邻接表动态生成过程中累计得到。入度初值可随邻接表动态生成过程中累计得到。采用栈来存放当前未处理过的入度为零点的采用栈来存放当前未处理过的入度为零点的结点，但

44、并不需要额外增设栈的空间，而是结点，但并不需要额外增设栈的空间，而是设一设一个栈顶位置的指针将当前所有未处理过的入度为个栈顶位置的指针将当前所有未处理过的入度为零的结点连接起来，零的结点连接起来，形成一个静态链式栈。形成一个静态链式栈。 第七章图拓扑排序算法拓扑排序算法void topo_sort (algraph *g)int top = -1;for (i=0;iadjlisti. indegree= 0)g-adjlisti.indegree = top;top = i;下一页栈顶指针初始化栈顶指针初始化依次将入度为依次将入度为0的的顶点压入链式栈顶点压入链式栈第七章图拓扑排序算法拓扑排

45、序算法for (i=0;iadjlisttop.indegree;printf(% c,g-adjlistj.vertex);ptr=g-adjlistj.firstedge;while (ptr!=null) k=ptr-adjvex;g-adjlistk.indegree-;if(g-adjlistk.indegree=0)g-adjlistk.indegree=top;top=k;ptr=ptr-next;无度为无度为0的顶点，即有环的顶点，即有环从栈中退出一个顶点从栈中退出一个顶点并输出，使并输出，使top指向下指向下一个度为一个度为0的顶点。的顶点。使使ptr指向已删指向已删除顶点的

46、邻接表除顶点的邻接表当前输出顶点的当前输出顶点的邻接点的入度减邻接点的入度减1新的入度为新的入度为0的顶的顶点进栈点进栈第七章图一、一、aoe网概念网概念1.定义定义若在带权的有向图中若在带权的有向图中,以以顶点顶点表示事件表示事件,有向有向边表示活边表示活动动,边上的权值边上的权值表示完成该活动的开销表示完成该活动的开销(如该活动所需的时如该活动所需的时间间),则称此带权的有向图为用边表示活动的网络则称此带权的有向图为用边表示活动的网络,简称简称aoe网网(activity on edge)7.6.3 aoe网与关键路径网与关键路径987645321a1=6a2=4a3=5a4=1a5=1a

47、6=2a7=9a8=7a9=4a10=2a11=4第七章图2.说明说明(1) aov网与网与aoe网有密切关系又有不同。网有密切关系又有不同。如果用他们表示工程，如果用他们表示工程，aov网表示各个子工程之网表示各个子工程之间的优先关系，是定性关系；在间的优先关系，是定性关系；在aoe网中还要体现完网中还要体现完成各个子工程的确切时间，是定量关系。成各个子工程的确切时间，是定量关系。（2）在）在aoe网中，只有在某网中，只有在某顶点所代表的事件顶点所代表的事件发生后，发生后，从该顶点出发的各有向边所代表的活动才能开始。只从该顶点出发的各有向边所代表的活动才能开始。只有在进入该顶点的各有向边所代

48、表的活动都已经结束有在进入该顶点的各有向边所代表的活动都已经结束后，该顶点所代表的事件才能发生。后，该顶点所代表的事件才能发生。（3）在一个表示工程的）在一个表示工程的aoe网中，应该网中，应该不存在回路不存在回路，网中仅存在一个入度为零的顶点，作为网中仅存在一个入度为零的顶点，作为开始顶点开始顶点，它，它表示了整个工程的开始；网中仅存在一个出度为零的表示了整个工程的开始；网中仅存在一个出度为零的顶点，称为顶点，称为结束顶点结束顶点，它表示整个工程的结束。，它表示整个工程的结束。7.5.2 aoe网与关键路径网与关键路径第七章图 把工程计划表示为有向图，用顶点表示事件，弧表示活动；把工程计划表

49、示为有向图，用顶点表示事件，弧表示活动；每个事件表示在它之前的活动已完成，在它之后的活动可以开始每个事件表示在它之前的活动已完成，在它之后的活动可以开始.例例 设一个工程有设一个工程有11项活动，项活动，9个事件个事件事件事件 v1表示整个工程开始表示整个工程开始事件事件v9表示整个工程结束表示整个工程结束整个工程只有一个开始点和一个完成点整个工程只有一个开始点和一个完成点，在正常情况下，网，在正常情况下，网中只一个入度为零的点（称为源点）和一个出度为零的点（称为中只一个入度为零的点（称为源点）和一个出度为零的点（称为汇点）。汇点）。问题：（问题：（1）完成整项工程至少需要多少时间？）完成整项

50、工程至少需要多少时间？ （2）哪些活动是影响工程进度的关键？）哪些活动是影响工程进度的关键？aoeaoe网的典型应用网的典型应用987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4第七章图aoe网网(activity on edge)是一个带权的有向无环图，是一个带权的有向无环图，其中其中顶点顶点表示事件，表示事件，弧弧表示活动，表示活动，权权表示活动持续时间表示活动持续时间。v路径长度路径长度路径上各活动持续时间之和路径上各活动持续时间之和。v关键路径关键路径路径长度最长的路径叫关键路径路径长度最长的路径叫关键路径。vve(j)表示事

51、件表示事件vj的最早发生时间的最早发生时间vvl(k)表示事件表示事件vk的最迟发生时间的最迟发生时间ve(i)表示活动表示活动ai的最早开始时间的最早开始时间vl(i) 表示活动表示活动ai的最迟开始时间的最迟开始时间vl(i)-e(i)表示完成活动表示完成活动ai的时间余量的时间余量。v关键活动关键活动关键路径上的活动叫关键活动，即关键路径上的活动叫关键活动，即l(i)=e(i)的活动的活动。4321a1=6a2=4a4=2a5=1二、关键路径有关术语二、关键路径有关术语(1)第七章图1.路径长度路径长度aoe网中一条路径的长度是该路径上每个活动所网中一条路径的长度是该路径上每个活动所需时

52、间的总和。需时间的总和。(不是路径上边的数目不是路径上边的数目)2.关键路径关键路径aoe网中网中,从开始顶点到结束顶点之间路径长度从开始顶点到结束顶点之间路径长度中的最大路径为中的最大路径为关键路径关键路径。由于。由于aoe网中某些子工程网中某些子工程（活动）可以同时进行，要保证每个子工程都能完成，（活动）可以同时进行，要保证每个子工程都能完成，完成该工程的最少时间就是该工程完成该工程的最少时间就是该工程aoe网的网的关键路径关键路径长度长度。3.事件的最早发生时间事件的最早发生时间ve(j)事件事件vj的最早发生时间的最早发生时间ve(j)是从开始顶点是从开始顶点v1到到vj的最长路径长度

53、。的最长路径长度。二、关键路径有关术语二、关键路径有关术语(2)jkai4.活动的最早开始时间活动的最早开始时间e (i)活动活动ai的最早开始时间的最早开始时间e (i)是该活动的起点所表示的事是该活动的起点所表示的事件最早发生时间件最早发生时间,如果由边如果由边(vj,vk)表示活动表示活动ai,则有则有e(i)=ve(j)。5.事件的最迟发生时间事件的最迟发生时间vl(k)事件事件vk的最迟发生时间的最迟发生时间vl(k)是在不推迟整个工程完成是在不推迟整个工程完成(即保证结束顶点即保证结束顶点vn在在ve(n)时刻发生时刻发生)的前提下的前提下,该事件最迟必该事件最迟必须发生的时间。须

54、发生的时间。vl(k)为为ve(n)减去顶点减去顶点vk到结束顶点到结束顶点vn的最的最长路径的长度。长路径的长度。6.活动的最迟开始时间活动的最迟开始时间l(i)活动活动ai的最迟开始时间的最迟开始时间l(i)是该活动的终点所表示的事件是该活动的终点所表示的事件最迟发生时间与该活动的所需时间之差。如果由边最迟发生时间与该活动的所需时间之差。如果由边(vj,vk)表表示活动示活动ai,则有则有l(i)=vl(k) ai所需时间所需时间jkai第七章图7.时间余量时间余量 l(i)-e(i) 活动活动ai的的 l(i)-e(i)是该活动完成的时间余量。它是是该活动完成的时间余量。它是在不增加完成

55、整个工程所需时间的情况下，活动在不增加完成整个工程所需时间的情况下，活动ai可以可以拖延的时间。拖延的时间。8.关键活动关键活动 e(i)= l(i) 当一活动的时间余量当一活动的时间余量=0，说明该活动必须如期完成，说明该活动必须如期完成，否则就会拖延完成整个工程的进度。若活动否则就会拖延完成整个工程的进度。若活动ai的时间余的时间余量量=0，则称该活动为，则称该活动为关键活动关键活动。当时间余量。当时间余量0，活动，活动ai不是关键活动，只要拖延的时间不超过时间余量，就不不是关键活动，只要拖延的时间不超过时间余量，就不会影响整个工程的进度；但如果拖延的时间超过时间余会影响整个工程的进度；但如果拖延的时间超过时间余量，则关键活动就可能发生变化。量，则关键活动就可能发生变化。二、关键路径有关术语二、关键路径有关术语(3)jkai第七章图三、关键路径的求解方法三、关键路径的求解方法如何找如何找e(i)=l(i)的关键活动？的关键活动？ 求事件求事件j的最早发生时间：的最早发生时间：vej 求事件求事件k的最迟发生时间：的最迟发生时间：vlk 计算每条