第七章图深深度度优优先先搜搜索索遍遍历历算算法法及及广广度度优优先先搜搜索索遍遍历历算算法法中中遍遍历历图图过过程程中中历历经经边边的的集集合合和和顶顶点点集集合合一一起起构构成成连连通通图图的的极极小小连连通通子子图图。它它是是连连通通图图的的一一颗颗生生成成树。树。生生成成树树：是是一一个个极极小小连连通通子子图图，它它含含有有图图中中全全部部顶顶点，但只有点，但只有n-1条边。条边。由由深深度度优优先先搜搜索索遍遍历历得得到到的的生生成成树树，称称为为深深度度优优先先生生成成树树，由由广广度度优优先先搜搜索索遍遍历历得得到到的的生生成成树树，称为称为广度优先生成树广度优先生成树。7.4.1生成树及生成森林生成树及生成森林7.4最小生成树最小生成树V0V1V3V4V2V6V5V7V0V1V3V4V2V6V5V7深度优先生成树深度优先生成树V0V1V3V4V2V6V5V7广度优先生成树广度优先生成树V0V1V3V4V2V6V5V7深度遍历：深度遍历：V0V1V3V7V4V2V5V6广度遍历：广度遍历：V0V1V2V3V4V5V6V7V0V1V3V4V2V6V5V7第七章图生成森林：生成森林：若一个图是非连通图，但有若干个连通分量，则若一个图是非连通图，但有若干个连通分量，则通过深度优先搜索遍历或广度优先搜索遍历，不可以通过深度优先搜索遍历或广度优先搜索遍历，不可以得到生成树，但可以得到生成森林，且若非连通图有得到生成树，但可以得到生成森林，且若非连通图有n个顶点，个顶点，m个连通分量，则可以遍历得到个连通分量，则可以遍历得到m棵生成树，棵生成树，合起来为合起来为生成森林生成森林，森林中包含，森林中包含n-m条树边。条树边。ABLMCFDEGHKIJABLMCFJDEGHKI深度优先生成森林深度优先生成森林第七章图n 说明说明: :v 一个图可以有许多棵一个图可以有许多棵不同不同的生成树的生成树v 所有生成树具有以下共同特点：所有生成树具有以下共同特点：l生成树的顶点个数与图的顶点个数相同生成树的顶点个数与图的顶点个数相同l生成树是图的极小连通子图生成树是图的极小连通子图l一个有一个有n个顶点的连通图的生成树有个顶点的连通图的生成树有n-1条边条边l在生成树中再加一条边必然形成回路在生成树中再加一条边必然形成回路l生成树中任意两个顶点间的路径是唯一的生成树中任意两个顶点间的路径是唯一的v含含n个顶点个顶点n-1条边的图不一定是生成树条边的图不一定是生成树第七章图7.4.2 7.4.2 最小生成树最小生成树1、最小生成树、最小生成树对于带权的连通图对于带权的连通图G，其生成树也是带权的。我们，其生成树也是带权的。我们把生成树各边的权值总和称为该把生成树各边的权值总和称为该生成树的权生成树的权。并且将权。并且将权最小的生成树称为最小的生成树称为最小生成树最小生成树。2. 求最小生成树求最小生成树首先明确：首先明确：使用不同的遍历图的方法，可以得到不同的生成树；使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。从不同的顶点出发，也可能得到不同的生成树。按照生成树的定义，按照生成树的定义，n n 个顶点的个顶点的连通网络连通网络的生成树有的生成树有 n n 个顶点、个顶点、n-n-1 1 条边。条边。即有权图即有权图第七章图目标：目标： 在网络的多个生成树中，寻找一个各边权值在网络的多个生成树中，寻找一个各边权值之和最小的生成树。之和最小的生成树。构造最小生成树的准则构造最小生成树的准则v必须只使用该网络中的边来构造最小生成树；必须只使用该网络中的边来构造最小生成树；v必须使用且仅使用必须使用且仅使用n n-1-1条边条边来联结网络中的来联结网络中的n n个个顶点；顶点；v不能使用产生回路的边不能使用产生回路的边。第七章图1、问题提出、问题提出要在要在n个城市间建立通信联络网，个城市间建立通信联络网，n个城市间，最多可设置个城市间，最多可设置n(n-1)/2条线路；条线路；n个城市间建立通信网，只需个城市间建立通信网，只需n-1条线路；条线路；问题转化为：如何在可能的线路中选择问题转化为：如何在可能的线路中选择n-1条，条，能把能把所有城市（顶点）均连起来，且总耗费（各边所有城市（顶点）均连起来，且总耗费（各边权值之和）最小。权值之和）最小。典型用途：典型用途：希望找到一棵生成树，它的每条边上的权值之希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小和（即建立该通信网所需花费的总代价）最小最小生成树最小生成树MST(Minimum Cost Spanning Tree)1654327131791812752410数学模型：数学模型：顶点顶点表示城市，有表示城市，有n n个；个；边边表示线路，有表示线路，有n1n1条；条；边的权值边的权值表示线路的经济代价；表示线路的经济代价；连通网连通网表示表示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中中，另一个端点仍在另一个端点仍在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就是最后得到的最小生成树。就是最后得到的最小生成树。普里姆算法中每次选取的边两端，总是一个已普里姆算法中每次选取的边两端，总是一个已连通顶点（在连通顶点（在U集合内）和一个未连通顶点（在集合内）和一个未连通顶点（在U集合外），故这个边选取后一定能将未连通顶点连集合外），故这个边选取后一定能将未连通顶点连通而又保证不会形成环路。通而又保证不会形成环路。7.4.3 Prim7.4.3 Prim算法算法PrimPrim方法构造过程方法构造过程1654326513566425131163141643142116432142516543214253U:V-U:143256第七章图普里姆普里姆(Prim)(Prim)算算法法 Prim算法可用下述过程描述：算法可用下述过程描述：（1）Uu1，T=；（2）while（UV）do （u，v）minwuv；uU，vVUTT（u，v）UUv（3）结束。结束。第七章图 有关数据的存储结构有关数据的存储结构设置两个辅助数组：设置两个辅助数组：lowcost用来保存集合用来保存集合VU中各顶点与集合中各顶点与集合U中各顶点构成的边中具有最小权值的边的权值；中各顶点构成的边中具有最小权值的边的权值；adjvex用来保存依附于该边的在集合用来保存依附于该边的在集合U中的顶中的顶点。点。普里姆普里姆(Prim)(Prim)算算法法第七章图普里姆普里姆(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 iadjvexlowcost 01 2 3 4 5iadjvexlowcost0 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 13652165546U UV V2 2V V0 0V V3 3V V5 5V V4 4V V1 13652165546U UV-U=v1,V2,V3,V4,V5V-U=v1,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 6 0 0 adjvexlowcostlowcost0,2,50,2,5 0 2 0 5 2 20 2 0 5 2 2 0 0 5 5 0 0 6 0 0 6 0 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 adjvexadjvexlowcostlowcost0,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 构造最小生成树方法（二）：构造最小生成树方法（二）：KruskalKruskal算法算法假设假设G=（V，E）是一个具有是一个具有n个顶点的连通网络，个顶点的连通网络，G=(U,T)是是G的最小生成树，的最小生成树，U的初值等于的初值等于V，即包含有即包含有G中的全部顶点，中的全部顶点，T的初值为空集。的初值为空集。基本思想：将图基本思想：将图G中的边按权值中的边按权值从小到大的顺序从小到大的顺序依次选依次选取，若选取的边使生成树取，若选取的边使生成树G不形成环路不形成环路，则把它并入，则把它并入T中，保留作为生成树中，保留作为生成树G的一条边，若选取的边使生成树的一条边，若选取的边使生成树G形成环路，则将其舍弃，如此进行下去，直到形成环路，则将其舍弃，如此进行下去，直到T中包中包含含n-1条边为止。此时的条边为止。此时的T即为最小生成树。即为最小生成树。第七章图1654326513566425165432135427.4.4克鲁斯卡尔克鲁斯卡尔(Kruskal)算法算法第七章图克鲁斯卡尔克鲁斯卡尔算算法法 有关数据的存储结构有关数据的存储结构设置一个结构设置一个结构数组数组arr存储网中所有的边，边的结构存储网中所有的边，边的结构类型包括构成的顶点信息和边权值类型包括构成的顶点信息和边权值。#defineMaxEdgetypedefstructintv1,v2；intcost；EdgeNode；EdgeNodearrMaxEdge；事先把数组事先把数组arr中的各元素按照其中的各元素按照其cost域值由小到大域值由小到大的顺序排列。的顺序排列。第七章图设置一个设置一个数组数组fn，其初值为，其初值为fi=i，表示各个顶，表示各个顶点在点在不同的连通分量不同的连通分量上。然后，依次取出上。然后，依次取出arr数组中数组中的每条边的两个顶点，查找它们所属的连通分量，的每条边的两个顶点，查找它们所属的连通分量，设设u1和和u2为两顶点所在的树的根结点在为两顶点所在的树的根结点在f中的序号，中的序号，若若u1不等于不等于u2，表明这条边的两个顶点不属于同连，表明这条边的两个顶点不属于同连通一分量，则将这条边作为最小生成树的边输出，通一分量，则将这条边作为最小生成树的边输出，并合并它们所属的两个连通分量。并合并它们所属的两个连通分量。克鲁斯卡尔克鲁斯卡尔算算法法第七章图克鲁斯卡尔克鲁斯卡尔算算法法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+;初始化根结点数组初始化根结点数组依次搜索每条边的两个依次搜索每条边的两个顶点所在树的根结点顶点所在树的根结点不属于同一连通不属于同一连通分量，合并，把分量，合并，把u1作为作为u2的根的根即把即把顶点顶点v1根（根（u1）作为顶点作为顶点v2根（根（u2）的根结点的根结点演演示示第七章图7.5 7.5 7.5 7.5 最短路径最短路径最短路径最短路径1 1、问题提出与数学模型、问题提出与数学模型问题：在一个交通网络中，如何找到城市问题：在一个交通网络中，如何找到城市A A到城市到城市B B之间一条距离最近或花费最少的通路？之间一条距离最近或花费最少的通路？ 用带权的有向图表示一个交通运输网，图中：用带权的有向图表示一个交通运输网，图中： 顶点顶点表示城市表示城市 边边表示城市间的交通联系表示城市间的交通联系 权权表示此线路的长度或所花费的代价表示此线路的长度或所花费的代价数学模型：数学模型： 从某顶点出发，沿图的边到达另一顶点所经过从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径的路径中，各边上权值之和最小的一条路径最最短路径短路径第七章图51643208562301371732913长度长度最短路径最短路径813192120注：最短路径与最小生成树不同，路径上不一定包含注：最短路径与最小生成树不同，路径上不一定包含n个顶点。个顶点。7.5 7.5 7.5 7.5 最短路径最短路径最短路径最短路径第七章图两种最常见的最短路径问题：两种最常见的最短路径问题：一顶点到其余各顶点的最短路径一顶点到其余各顶点的最短路径单源点最短路径用单源点最短路径用Dijkstra算法算法任意两顶点间的最短路径任意两顶点间的最短路径所有顶点间的最短路径用所有顶点间的最短路径用Floyd算法算法7.5 7.5 7.5 7.5 最短路径最短路径最短路径最短路径第七章图1、迪杰斯特拉、迪杰斯特拉(Dijkstra)算法思想算法思想按按路径长度递增次序路径长度递增次序产生最短路径算法：产生最短路径算法：把把V分成两组：分成两组：（1）S：已求出最短路径的顶点的集合已求出最短路径的顶点的集合；（2）T=V-S：尚未确定最短路径的顶点集合尚未确定最短路径的顶点集合。将将T中顶点按最短路径递增的次序加入到中顶点按最短路径递增的次序加入到S中中。7.5.1从某个源点到其余各顶点的最短路径从某个源点到其余各顶点的最短路径(1)单源点最短路径：单源点最短路径：是指给定一个出发点（单源点）是指给定一个出发点（单源点）和一个有向网和一个有向网G=(V,E)，求出源点到其它各顶点之，求出源点到其它各顶点之间的最短路径。间的最短路径。第七章图2、求最短路径步骤、求最短路径步骤采用邻接矩阵采用邻接矩阵costNN来存储带权有向图。来存储带权有向图。1)令令S=V0,T=其余顶点其余顶点，T中顶点对应的距离值中顶点对应的距离值:若存在若存在，为，为弧上的权值弧上的权值，若不存在若不存在，为为 。2)从从T中选取一个其距离值为最小的顶点中选取一个其距离值为最小的顶点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-2120V6: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的最短距离。的最短距离。解解决决此此问问题题的的一一个个有有效效方方法法是是:轮轮流流以以每每一一个个顶顶点点为为源源点点,重重复复执执行行迪迪杰杰斯斯特特拉拉算算法法n次次,即即可可求求得得每每一对顶点之间的最短路径一对顶点之间的最短路径,总的时间复杂度为总的时间复杂度为O(n3)。下下面面将将介介绍绍用用弗弗洛洛伊伊德德(Floyd)算算法法来来实实现现此此功功能能,时时间间复复杂杂度度仍仍为为O(n3),但但该该方方法法比比调调用用n次次迪迪杰杰斯斯特拉方法更直观一些。特拉方法更直观一些。7.5.2 7.5.2 所有顶点对之间的最短路径所有顶点对之间的最短路径第七章图采用邻接矩阵采用邻接矩阵costNN来存储带权有向图。来存储带权有向图。算法的基本思想算法的基本思想是是: 设置一个设置一个N*N的矩阵的矩阵ANN，其中除对角线的元素都等于其中除对角线的元素都等于0外，其它元素外，其它元素Aij的值表示顶点的值表示顶点i到顶点到顶点j的最短路径长度。的最短路径长度。运算步骤为：运算步骤为：首先，以任意两个顶点之间的有向边的权值作为首先，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为路径长度，没有有向边时，路径长度为，此时，此时,Aij=costij, 以以后后逐逐步步尝尝试试在在原原路路径径中中加加入入其其它它顶顶点点作作为为中中间间顶顶点点，如如果果增增加加中中间间顶顶点点后后，得得到到的的路路径径比比原原来来的的路路径径长长度度减减少少了了，则则以此新路径代替原路径，修改矩阵元素。以此新路径代替原路径，修改矩阵元素。弗洛伊德算法弗洛伊德算法(1)(1)第七章图具体做法为：具体做法为： 第一步，让所有边上加入中间顶点第一步，让所有边上加入中间顶点V0，取，取Aij与与Ai0+A0j中较小的值作中较小的值作Aij的值的值.第二步，让所有边上加入中间顶点第二步，让所有边上加入中间顶点V1，取，取Aij与与Ai1+A1j中较小的值，为中较小的值，为Aij的值，的值，如此进行下去，当第如此进行下去，当第n步完成后，得到步完成后，得到Aij,即为我们即为我们所求结果所求结果,Aij表示顶点表示顶点i到顶点到顶点j的最短距离。的最短距离。因此，弗洛伊德算法可以描述为因此，弗洛伊德算法可以描述为: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 ABCBCABCCA CABV1V2V0642113ACB弗洛伊德弗洛伊德算法算法求最短路径的过程求最短路径的过程第七章图7.6 7.6 7.6 7.6 有向无环图及其应有向无环图及其应有向无环图及其应有向无环图及其应用用用用7.6.1 7.6.1 有向无环图的概念有向无环图的概念 一个一个无环的有向图无环的有向图称做有向无环图（称做有向无环图（Directed Directed AcyclineAcycline Graph Graph），简称），简称DAGDAG图。下面是有向树、图。下面是有向树、DAG图和有向图的例子。图和有向图的例子。有向树有向树DAG图图有向图有向图第七章图检查一个有向图是否存在环要比无向图复杂。检查一个有向图是否存在环要比无向图复杂。对于无向图来说，若深度优先遍历过程中对于无向图来说，若深度优先遍历过程中遇到遇到回边回边( (指向已访问过的顶点的边指向已访问过的顶点的边) )，则必定存在环；，则必定存在环；而对于有向图来说，这条回边很有可能不构成而对于有向图来说，这条回边很有可能不构成环，它有可能是指向深度优先生成森林中另一棵生环，它有可能是指向深度优先生成森林中另一棵生成树上顶点的弧。但是，如果从有向图上某个顶点成树上顶点的弧。但是，如果从有向图上某个顶点v出发的遍历，出发的遍历，在在DFS（v）结束之前出现一条从顶点结束之前出现一条从顶点u到顶点到顶点v的回边的回边，由于，由于u在生成树上是在生成树上是v的子孙，则有的子孙，则有向图必定存在包含顶点向图必定存在包含顶点v和和u的环。的环。7.6 7.6 7.6 7.6 有向无环图及其应有向无环图及其应有向无环图及其应有向无环图及其应用用用用第七章图7.6 7.6 7.6 7.6 有向无环图及其应有向无环图及其应有向无环图及其应有向无环图及其应用用用用有向无环图也是描述一项工程或系统的进行过程的有有向无环图也是描述一项工程或系统的进行过程的有效工具。几乎所有的效工具。几乎所有的工程（工程（Project）都可分为若干个称作都可分为若干个称作活动（活动（Activity）的子工程，而这些子工程之间，通常受着的子工程，而这些子工程之间，通常受着一定条件的约束，如其中某些子工程的开始必须在另一些一定条件的约束，如其中某些子工程的开始必须在另一些子工程完成之后。子工程完成之后。对整个工程和系统，人们关心的是两个方面的问题：对整个工程和系统，人们关心的是两个方面的问题：一是工程能否顺利进行：一是工程能否顺利进行：二是估算整个工程完成所必须的最短时间。二是估算整个工程完成所必须的最短时间。下面我们通过对有向图进行下面我们通过对有向图进行拓扑排序拓扑排序和和关键路径关键路径操作操作来解决这两个问题。来解决这两个问题。第七章图1、AOV网：网：在一个有向图中，若用顶点表示活动，有向边表在一个有向图中，若用顶点表示活动，有向边表示活动间先后关系，称该有向图叫做示活动间先后关系，称该有向图叫做顶点表示活动的顶点表示活动的网络网络(ActivityOnVertexnetwork)简称为简称为AOV网。网。在工程实践中，一个工程项目往往由若干个子项在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系：目组成，这些子项目间往往有多种关系：先后关系先后关系子项目之间无次序要求。子项目之间无次序要求。如果从顶点如果从顶点Vi到到Vj之间存在有向边之间存在有向边,则表则表示活动示活动i必须先于活动必须先于活动j进行。进行。 7.6.2AOV网与拓扑排序网与拓扑排序第七章图在在AOV网络中，如果顶点网络中，如果顶点Vi的活动必须在顶点的活动必须在顶点Vj的的活动以前进行，则称活动以前进行，则称Vi为为Vj的前趋顶点，而称的前趋顶点，而称Vj为为Vi的的后继顶点。这种前趋后继关系有传递性。后继顶点。这种前趋后继关系有传递性。AOV网络中网络中一定不能有有向环路一定不能有有向环路。例如在下图那。例如在下图那样的有向环路中，样的有向环路中，V0是是V1的前趋顶点，的前趋顶点，V1是是V2的前趋顶的前趋顶点，点，V2是是V3的前趋顶点，的前趋顶点，V3又是又是V0的前趋顶点，环路表的前趋顶点，环路表示顶点之间的先后关系进入了死循环。示顶点之间的先后关系进入了死循环。因此，对给定的因此，对给定的AOV网络网络首先要判定网络中是否首先要判定网络中是否存在环路存在环路，只有有向无环路网络在应用中才有实际意义。，只有有向无环路网络在应用中才有实际意义。v3v2v0v1 7.6.2AOV网与拓扑排序网与拓扑排序第七章图课程流程图课程流程图C1C2C3C4C5C6C7C8C9C10C11C12程序设计程序设计离散数学离散数学数据结构数据结构汇编语言汇编语言算法分析算法分析计算机体系计算机体系编译方法编译方法操作系统操作系统高等数学高等数学线性代数线性代数电子电路电子电路数值分析数值分析无无C1C1,C2C1C3,C4C11C5,C3C3,C6无无C9C9C9,C10,C1课程编号课程编号 课程名称课程名称 先决条件先决条件 C4C1C2C3C12C9C10C11C6C7C8C5有一些课程必须在先学完某些先有一些课程必须在先学完某些先修课程之后才能开始学习。如修课程之后才能开始学习。如数据结构数据结构就必须安排在就必须安排在离离散数学散数学和和程序设计程序设计之后之后。 7.6.2AOV网与拓扑排序网与拓扑排序第七章图拓扑排序的定义拓扑排序的定义给出有向图给出有向图G=(V,E)，对于对于V中的顶点的线性序列中的顶点的线性序列(vi1,vi2,.,vin)，如果满足如下条件：若在如果满足如下条件：若在G中从顶中从顶点点vi到到vj有一条路经，则在序列中顶点有一条路经，则在序列中顶点vi必在顶点必在顶点vj之前；则称该序列为之前；则称该序列为G的一个拓扑序列（的一个拓扑序列（Topologicalorder）。构造有向图的一个拓扑序列的过程称为）。构造有向图的一个拓扑序列的过程称为拓扑拓扑排序排序（Topologicalsort）。）。所谓所谓“拓扑排序拓扑排序”就是将就是将AOV网络中的各个顶点网络中的各个顶点(各个活动各个活动)排列成一个排列成一个线性有序序列，使得所有要求线性有序序列，使得所有要求的前趋、后继关系都能得到满足。的前趋、后继关系都能得到满足。 2、拓扑排序、拓扑排序说明说明(1)在在AOV网中网中,不存在回路。不存在回路。AOV网所代表的一项工程中活动的集合，为了保网所代表的一项工程中活动的集合，为了保证该项工程得以顺利完成，必须保证证该项工程得以顺利完成，必须保证AOV网中不出现网中不出现回路；否则，意味着某项活动应以自身作为能否开展的回路；否则，意味着某项活动应以自身作为能否开展的先决条件，这是荒谬的。先决条件，这是荒谬的。(2)拓扑序列不是唯一的。拓扑序列不是唯一的。由于由于AOV网络中有些顶点之间没有次序要求，它网络中有些顶点之间没有次序要求，它们在拓扑有序序列中的位置可以任意颠倒，所以拓扑们在拓扑有序序列中的位置可以任意颠倒，所以拓扑排序的结果一般排序的结果一般并不是唯一的并不是唯一的。通过拓扑排序还可以判断出此通过拓扑排序还可以判断出此AOV网络是否包含网络是否包含有有向环路，若有向图有有向环路，若有向图G所有顶点都在拓扑排序序列所有顶点都在拓扑排序序列中中，则，则AOV网络必定不包含有有向环路。网络必定不包含有有向环路。第七章图如图：可以得到不止一个如图：可以得到不止一个拓扑排序：拓扑排序：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)从网络中删去该顶点和从该顶点发出的所有从网络中删去该顶点和从该顶点发出的所有有向边；有向边；(3)重复执行上述两步，直到网中所有的入度为重复执行上述两步，直到网中所有的入度为0的顶点都被输出的顶点都被输出。如果进行到某一步，网中还有顶点，但无法找到如果进行到某一步，网中还有顶点，但无法找到无前趋的顶点（没有入度为无前趋的顶点（没有入度为0的顶点），则说明此的顶点），则说明此AOV网络中存在有向环路，遇到这种情况，拓扑排序网络中存在有向环路，遇到这种情况，拓扑排序就无法进行了。就无法进行了。拓扑排序的方法拓扑排序的方法第七章图v2v3v1v4v6v5v2v2v5v2v3v5v2v3v4v6v5v2v3v6v5输出输出V1输出输出V4输出输出V6输出输出V3输出输出V5AOVAOV网上实施步骤的例子网上实施步骤的例子输出输出V2拓扑序列为：拓扑序列为：V1,V4,V6,V3,V5,V2v2v3v1v4v6v5第七章图拓扑排序算法：拓扑排序算法：以以邻接表邻接表作存储结构，作存储结构，并且并且增加一个数据域用于记增加一个数据域用于记录顶点入度。录顶点入度。indegreevertexfirstedgev1v2v3v4v5v60122indegreefirstedge5543adjvex next325240123456v1v2v3v4v5v6vertextypedefstructvnodeintindegree；VertexTypevertex；EdgeNode*firstedge；VertexNode；拓扑排序算法：拓扑排序算法：第七章图算法中可设置一个堆栈，凡是网中入度为算法中可设置一个堆栈，凡是网中入度为0 0 的顶的顶点都将其入栈。为此，拓扑排序的算法步骤为：点都将其入栈。为此，拓扑排序的算法步骤为：v把邻接表中所有入度为把邻接表中所有入度为0（没有前驱）的顶点进（没有前驱）的顶点进栈栈v栈非空时，输出栈顶元素栈非空时，输出栈顶元素Vj并退栈；在邻接表中并退栈；在邻接表中查找查找Vj的直接后继的直接后继Vk，把把Vk的入度减的入度减1；若；若Vk的入的入度为度为0则进栈则进栈v重复上述操作直至栈空为止。若栈空时输出的顶重复上述操作直至栈空为止。若栈空时输出的顶点个数不是点个数不是n，则有向图有环；否则，拓扑排序完毕则有向图有环；否则，拓扑排序完毕。拓扑排序算法拓扑排序算法第七章图注意：用邻接表作为它的存储结构，各表头结点注意：用邻接表作为它的存储结构，各表头结点的的indegree域存放相应顶点的入度值。每个顶点域存放相应顶点的入度值。每个顶点入度初值可随邻接表动态生成过程中累计得到。入度初值可随邻接表动态生成过程中累计得到。采用栈来存放当前未处理过的入度为零点的采用栈来存放当前未处理过的入度为零点的结点，但并不需要额外增设栈的空间，而是结点，但并不需要额外增设栈的空间，而是设一设一个栈顶位置的指针将当前所有未处理过的入度为个栈顶位置的指针将当前所有未处理过的入度为零的结点连接起来，零的结点连接起来，形成一个静态链式栈。形成一个静态链式栈。 第七章图拓扑排序算法拓扑排序算法void Topo_Sort (AlGraph *G)int top = -1;for (i=0;iadjlisti. indegree= 0)G-adjlisti.indegree = top;top = i;下一页栈顶指针初始化栈顶指针初始化依次将入度为依次将入度为0的的顶点压入链式栈顶点压入链式栈第七章图拓扑排序算法拓扑排序算法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指向已删指向已删除顶点的邻接表除顶点的邻接表当前输出顶点的邻当前输出顶点的邻接点的入度减接点的入度减1新的入度为新的入度为0的顶的顶点进栈点进栈第七章图一、一、AOE网概念网概念1.定义定义若在带权的有向图中若在带权的有向图中,以以顶点顶点表示事件表示事件,有向有向边表示边表示活动活动,边上的权值边上的权值表示完成该活动的开销表示完成该活动的开销(如该活动所需如该活动所需的时间的时间),则称此带权的有向图为用边表示活动的网络则称此带权的有向图为用边表示活动的网络,简简称称AOE网网(ActivityOnEdge)7.6.3AOE网与关键路径网与关键路径987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4第七章图2.说明说明(1)AOV网与网与AOE网有密切关系又有不同。网有密切关系又有不同。如果用他们表示工程，如果用他们表示工程，AOV网表示各个子工程之网表示各个子工程之间的优先关系，是定性关系；在间的优先关系，是定性关系；在AOE网中还要体现完网中还要体现完成各个子工程的确切时间，是定量关系。成各个子工程的确切时间，是定量关系。（2）在）在AOE网网中，只有在某中，只有在某顶点所代表的事件顶点所代表的事件发生后，发生后，从该顶点出发的各有向边所代表的活动才能开始。只从该顶点出发的各有向边所代表的活动才能开始。只有在进入该顶点的各有向边所代表的活动都已经结束有在进入该顶点的各有向边所代表的活动都已经结束后，该顶点所代表的事件才能发生。后，该顶点所代表的事件才能发生。（3）在一个表示工程的）在一个表示工程的AOE网中，应该网中，应该不存在回路不存在回路，网中仅存在一个入度为零的顶点，作为网中仅存在一个入度为零的顶点，作为开始顶点开始顶点，它，它表示了整个工程的开始；网中仅存在一个出度为零的表示了整个工程的开始；网中仅存在一个出度为零的顶点，称为顶点，称为结束顶点结束顶点，它表示整个工程的结束。，它表示整个工程的结束。7.5.2AOE网与关键路径网与关键路径第七章图把工程计划表示为有向图，用顶点表示事件，弧表示活动；把工程计划表示为有向图，用顶点表示事件，弧表示活动；每个事件表示在它之前的活动已完成，在它之后的活动可以开始每个事件表示在它之前的活动已完成，在它之后的活动可以开始.例例设一个工程有设一个工程有11项活动，项活动，9个事件个事件事件事件V1表示整个工程开始表示整个工程开始事件事件V9表示整个工程结束表示整个工程结束整个工程只有一个开始点和一个完成点整个工程只有一个开始点和一个完成点，在正常情况下，网，在正常情况下，网中只一个入度为零的点（称为源点）和一个出度为零的点（称为中只一个入度为零的点（称为源点）和一个出度为零的点（称为汇点）。汇点）。问题：（问题：（1）完成整项工程至少需要多少时间？）完成整项工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？）哪些活动是影响工程进度的关键？AOEAOE网的典型应用网的典型应用987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4第七章图AOE网网(ActivityOnEdge)是一个带权的有向无环图，是一个带权的有向无环图，其中其中顶点顶点表示事件，表示事件，弧弧表示活动，表示活动，权权表示活动持续时间表示活动持续时间。v路径长度路径长度路径上各活动持续时间之和路径上各活动持续时间之和。v关键路径关键路径路径长度最长的路径叫关键路径路径长度最长的路径叫关键路径。vVe(j)表示事件表示事件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网中网中一条路径的长度是该路径上每个活动所一条路径的长度是该路径上每个活动所需时间的总和。需时间的总和。(不是路径上边的数目不是路径上边的数目)2.关键路径关键路径AOE网中网中,从开始顶点到结束顶点之间路径长度从开始顶点到结束顶点之间路径长度中的最大路径为中的最大路径为关键路径关键路径。由于。由于AOE网中某些子工程网中某些子工程（活动）可以同时进行，要保证每个子工程都能完成，（活动）可以同时进行，要保证每个子工程都能完成，完成该工程的最少时间就是该工程完成该工程的最少时间就是该工程AOE网的网的关键路径关键路径长度长度。3.事件的最早发生时间事件的最早发生时间ve(j)事件事件vj的最早发生时间的最早发生时间ve(j)是从开始顶点是从开始顶点v1到到vj的最长路径长度。的最长路径长度。二、关键路径有关术语二、关键路径有关术语(2)jkai4.活动的最早开始时间活动的最早开始时间e(i)活动活动ai的最早开始时间的最早开始时间e(i)是该活动的起点所表示的事是该活动的起点所表示的事件最早发生时间件最早发生时间,如果由边如果由边(vj,vk)表示活动表示活动ai,则有则有e(i)=ve(j)。5.事件的最迟发生时间事件的最迟发生时间vl(k)事件事件vk的最迟发生时间的最迟发生时间vl(k)是在不推迟整个工程完成是在不推迟整个工程完成(即保证结束顶点即保证结束顶点vn在在ve(n)时刻发生时刻发生)的前提下的前提下,该事件最迟该事件最迟必须发生的时间。必须发生的时间。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)是该活动完成的时间余量。它是在是该活动完成的时间余量。它是在不增加完成整个工程所需时间的情况下，活动不增加完成整个工程所需时间的情况下，活动ai可以拖可以拖延的时间。延的时间。8.关键活动关键活动e(i)=l(i)当一活动的时间余量当一活动的时间余量=0，说明该活动必须如期完成，说明该活动必须如期完成，否则就会拖延完成整个工程的进度。若活动否则就会拖延完成整个工程的进度。若活动ai的时间余的时间余量量=0，则称该活动为，则称该活动为关键活动关键活动。当时间余量。当时间余量0，活动，活动ai不是关键活动，只要拖延的时间不超过时间余量，就不不是关键活动，只要拖延的时间不超过时间余量，就不会影响整个工程的进度；但如果拖延的时间超过时间余会影响整个工程的进度；但如果拖延的时间超过时间余量，则关键活动就可能发生变化。量，则关键活动就可能发生变化。二、关键路径有关术语二、关键路径有关术语(3)jkai第七章图三、关键路径的求解方法三、关键路径的求解方法如何找如何找e(i)=l(i)的关键活动？的关键活动？求事件求事件j的最早发生时间：的最早发生时间：Vej求事件求事件k的最迟发生时间：的最迟发生时间：Vlk计算每条弧计算每条弧(活动活动)的的ei和和li找出找出ei=li的关键活动的关键活动jkai设活动设活动ai用弧用弧表示，其持续时间记为：表示，其持续时间记为：dut()则有：则有：（1）e(i)=Ve(j)（2）l(i)=Vl(k)-dut()、计算事件的最早发生时间、计算事件的最早发生时间ve（j）从从Ve(1)=0开始开始向向后后递推递推jkai此式的意义为：从指向此式的意义为：从指向顶点顶点V Vj j的的各边的活动中取最各边的活动中取最晚完成的一个活动的完成时晚完成的一个活动的完成时间作为间作为V Vj j的的最早出现时间最早出现时间。 此公式的意义为：由从此公式的意义为：由从V Vk k顶点指出的各边所代表的活动顶点指出的各边所代表的活动中取需最早开始的一个开始时中取需最早开始的一个开始时间作为间作为V Vk k的最迟出现时间。的最迟出现时间。 2、计算事件的最迟发生时间、计算事件的最迟发生时间vl（k）从从Vl(n)=Ve(n)开始向开始向前前递推递推jkai987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9顶点顶点VeVl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活动活动ell-e 00002266046258377077071031616014140033求关键路径步骤求关键路径步骤 求求Ve(jVe(j) ) 求求Vl(kVl(k) ) 求求e(i)e(i) 求求l(i)l(i) 计算计算l(i)-e(i)l(i)-e(i)第七章图四、结论：四、结论：u 关键路径上的活动都是关键活动；关键路径上的活动都是关键活动；u 缩短非关键活动都不能缩短整个工期；缩短非关键活动都不能缩短整个工期；u 分析关键路径的目的是找出影响整个工期的关分析关键路径的目的是找出影响整个工期的关键活动，缩短关键活动的持续时间，可以缩短整键活动，缩短关键活动的持续时间，可以缩短整个工期；个工期；u 在有多条关键路径时，缩短那些在所有关键路在有多条关键路径时，缩短那些在所有关键路径上的关键活动，才能缩短整个工期。径上的关键活动，才能缩短整个工期。第七章图以邻接表作存储结构以邻接表作存储结构从源点从源点V1出发，令出发，令Ve1=0，按拓扑序，按拓扑序列求各顶点的列求各顶点的Vej。从汇点从汇点Vn出发，令出发，令Vln=Ven，按逆，按逆拓扑序列求其余各顶点的拓扑序列求其余各顶点的Vlk.根据各顶点的根据各顶点的Ve和和Vl值，计算每条弧的值，计算每条弧的ei和和li，找出，找出eili的关键活动。的关键活动。算法描述：算法描述：第七章图输入顶点和弧信息，建立其邻接表；输入顶点和弧信息，建立其邻接表；计算每个顶点的入度；计算每个顶点的入度；对其进行拓扑排序；对其进行拓扑排序；排序过程中求顶点的排序过程中求顶点的Vej；将得到的拓扑序列进栈（为了得到一个逆拓将得到的拓扑序列进栈（为了得到一个逆拓序列）；序列）；按逆拓扑序列求顶点的按逆拓扑序列求顶点的Vlk；计算每条弧的计算每条弧的ei和和li，找出，找出eili的的关键活动。关键活动。算法实现：算法实现：P208P209作业作业1）画出下图的邻接矩阵和邻接表表示，并写出下图）画出下图的邻接矩阵和邻接表表示，并写出下图的深度优先搜索遍历序列和广度优先搜索遍历序列。的深度优先搜索遍历序列和广度优先搜索遍历序列。2)根据普里姆算法思想，画出构造该无向带权图最小根据普里姆算法思想，画出构造该无向带权图最小生成树的过程。生成树的过程。3）根据克鲁斯卡尔算法思想，画出构造该无向带权）根据克鲁斯卡尔算法思想，画出构造该无向带权图最小生成树的过程。图最小生成树的过程。AGCEBFD1349781542869第七章图4）对下图所示的有向带权图，根据）对下图所示的有向带权图，根据迪杰斯特拉算迪杰斯特拉算法，画出生成从结点法，画出生成从结点v1到其余各结点最短路径的到其余各结点最短路径的过过程。程。10378122542121610V2V6V4V3V1V5