数据结构第5章刘震.ppt

2019/7/28,第五章 图论与贪心算法,主讲老师：刘 震,$5.1 图图的基本概念,图是常用的重要的一类数据结构，上一章的树可以看成是图的特例，树中每个数据元素至多允许一个前驱，只能反映数据元素之间一对多的关系，而图中没有该限制，允许数据元素可以有多个前驱，因此可以反映数据元素之间多对多的关系。,$5.1 图图的基本概念1,有向图 无向图,$4.1 图图的基本概念1,有向图 G=（V，A） 其中，V为顶点的有穷非空集合 A为顶点之间的关系集合,G1=（V，A） V=v1, v2, v3, v4 A=, , , 其中表示从x到y的一条弧（arc），A为弧集合，x为弧尾（tail），y为弧头（head),$5.1 图图的基本概念1,无向图 G=（V，E） 其中,V同有向图，E为顶点之间的关系集合，E为边集合,G2=（V，A） V=v1, v2, v3, v4, v5 E=(v1, v2),(v1, v4),v2, v3),(v3, v4),(v2,v5),(v3,v5) 其中，(x, y)表示x与y之间的一条连线，称为边（edge）,$5.1 图图的基本概念1,图的顶点数为n, 边数为e,请找出n与e的关系,设n为顶点数，e为边或弧的条数 对无向图有： 0=e=n(n-1)/2 有向图有： 0=e=n(n-1),$5.1 图图的基本概念2,完全图: 边达到最大的图,无向完全图：边数为n(n-1)/2的无向图 有向完全图：弧数为n(n-1)的有向图,权：与图的边或弧相关的数 网：边或弧上带有权值的图,$5.1 图图的基本概念3,顶点的度 TD（V） 无向图：为依附于顶点V的边数 有向图：等于以顶点V为弧头的弧数（称为V的入度，记为ID（V）与以顶点V为弧尾的弧的出度，记为OD（V）之和。即：TD（V）=ID（V）+OD（V）,无向图 e= 1/2（TD(vi)） i=1,结论：,有向图 n n e= ID(vi)=OD(vi) i=1 i=1,无向图的度数为依附于顶点v 的边数；有向图的度数等于以 顶点v 为弧头的弧数与以顶点v 为弧尾的弧数之和,$5.1 图图的基本概念4-路径,无向图：顶点v到v的路径是一个顶点序列（v=vi0, vi1, , vim=v） 其中，（vij-1,vij ）E, 1A, 1=j=m,几个概念： 路径长度：路径上边或弧的数目 回路或环：首尾顶点相同的路径，称为回路或环。即： （v=vi0, vi1, , vim=v=v） 简单路径：路径中不含相同顶点的路径 简单回路：除首尾顶点外，路径中不含相同顶点的回路,$5.1 图图的基本概念5-连通,顶点连通：若顶点v到顶点v有路径，则称顶点v与v是连通的 连 通 图 ：包括无向连通图和有向连通图 无向图：若图中任意两个顶点vi,vj都是连通的，则称该图是连通图(vivj) 有向图：若图中任意两个顶点vi,vj，都存在从vi到vj和从vj到vi的路径，则称该有向图为强连通图(vivj) 连通分量： 无向图：无向图中极大连通子图，称为连通分量 有向图：有向图中极大强连通子图，称为强连通分量,G1有两个强连通分量,$5.1 图图的基本概念5-连通,定义：设无向图G是含有n个顶点的连通图， 则图G的生成树是含有n 个顶点，且只有n-1条边的连通子图 三要素： n个顶点 n-1条边 连通,$5.1 图图的基本概念6-生成树,$5.1 图图的基本概念7-子图,子图是图的一部分，它本身也是一 个图。如果有图G=(V，E)和G=(V,E)， 且V是V的子集，E是E的子集，则称G是G的子图。图4-1实际上是中国铁路交通图的一个子图。,$5.1 图图的基本概念8-邻接顶点,邻接顶点 在无向图中，若两个顶点之间有边连接，则这两个顶点互为邻接顶点,$4.2 图图的存储,回忆: 天然气管道铺设问题中, 需要存储社区房屋和商店信息,相互之间是否有通路及管道长度三个信息. 即使部分问题不牵涉管道长度(图的权值), 也至少需要存储图的顶点和边的两方面信息,如何存储?,仍然有顺序存储和链式存储2种方法!,$4.2 图图的存储1-邻接矩阵,一、数组表示法（邻接矩阵）,设图G=（V，E）有n个顶点，则G的邻接矩阵定义为n阶方阵A。 其中：,例如：G1、G2的邻接矩阵,邻接矩阵的特点： 1. 判定两个顶点Vi与Vj是否关联, 只需判Ai,j是否为1； 2. 求顶点的度容易:,$4.2 图图的存储1-邻接矩阵,如果G是带权图，wij是边（vi,vj）或的权，则其邻接 矩阵定义为：,$4.2 图图的存储1-邻接矩阵,请采用邻接矩阵存储右图数据,答: 设G=房屋1,房屋2,房屋3,商场1 4个顶点,则邻接矩阵为,$4.2 图图的存储2-邻接表,1. 无向图邻接表,对图中每个顶点Vi建立一个单链表，链表中的结点表示依附于顶点Vi的边，每个链表结点为两个域：,其中：邻接点域（adjvex）记载与顶点Vi邻接的顶点信息； 链域（nextarc）指向下一个与顶点Vi邻接的链表结点,每个链表附设一个头结点，头结点结构为：,其中：vexdata存放顶点信息（姓名、编号等）； fristarc指向链表的第一个结点。,$4.2 图图的存储2-邻接表,如图G2的邻接表为：,无向图邻接表特点： 1.n个顶点，e条边的无向图，需n个头结点和2e个链表结点 2.顶点Vi的度 TD（Vi）=链表i中的链表结点数,2. 有向图邻接表,与无向图的邻接表结构一样。只是在第i条链表上的结点是以Vi为 弧尾的各个弧头顶点,有向图邻接表特点： 1. n个顶点，e条弧的有向图，需n个表头结点，e 个链表结点 2. 第i条链表上的链表结点数，为Vi的出度(求顶点的出度 易，求入度难）,G1的邻接表,$4.2 图图的存储2-邻接表,3. 有向图逆邻接表,与无向图的邻接表结构一样。只是在第i条链表上的结点是以Vi为弧头的各个弧尾顶点,此时，第i条链表上的结点数，为Vi的入度,G1的逆邻接表,$4.2 图图的存储2-邻接表,$4.2 图图的存储3 十字链表（orthogonal list）,十字链表是将有向图的邻接表和逆邻接表结合起来的一种有向图链式存储结构,有向图的每一条弧有一个弧结点，每一个顶点有一个顶点结点， 其结构为：,2. 整体结构,通过hlink将弧头相同的弧连在一个链表上； 通过tlink将弧尾相同的弧连在一个链表上 而hlink链和tlink链的头结点就是顶点结点,$4.2 图图的存储3 十字链表（orthogonal list）,$4.2 图图的存储3 十字链表（orthogonal list）,4.十字链表的特点：, 顶点结点数=顶点数 弧结点数=弧的条数 求入度：从顶点Vi的firstin出发，沿着弧结点中的hlink所经过的弧结点数。 求出度：从顶点Vi的firstout出发，沿着弧结点中的tlink所经过的弧结点数。,$4.2 图图的存储4-邻接多重表,邻接多重表是无向图的另一种链式存储结构。,图的每一条边有一个边结点，边结点的结构为：,每一个顶点有一个顶点结点，顶点结点结构为：,其中：ivex 和jvex为该边所依附的两个顶点。 ilink指向下一条依附于顶点ivex的边。 jlink指向下一条依附于顶点jvex 的边。 data存放顶点的信息。 firstedge指向第一条依附于该顶点的边结点。,$4.2 图图的存储4-邻接多重表,如图G2的邻接多重表:,邻接多重表特点： 1.顶点结点数为n，边结点数为e 2.对需要得到边的两个顶点的一类操作很方便 （如删除一条边，判一条边是否已访问）,$4.3 图图的遍历,怎么知道图的顶点都被访问了? 怎么知道没有重复访问?,$4.3 图图的遍历,从图中某个顶点出发，沿路径使图中每个顶点被 访问且仅被访问一次的过程，称为遍历图。,两种常用遍历图的方法,深度优先搜索,广度优先搜索,$4.3 图图的遍历,一、深度优先搜索（depth-first-search),1. 深度优先搜索法遍历图的过程为：,1). 访问指定的某顶点V，将V作为当前顶点 2). 访问当前顶点的下一未被访问过的邻接点，并将该顶点作为当前顶点 3). 重复2，直到当前顶点的所有邻接点都被访问过 4). 沿搜索路径回退，退到尚有邻接点未被访问过的某结点，将该结点 作为当前结点，重复2，直到所有顶点被访问过的为止,$4.3 图图的遍历,如图G4：,$4.3 图图的遍历,怎么写程序实现深度优先遍历?,可以采用递归和非递归2种方法 实现相同的深度优先遍历算法!,$4.3 图图的遍历,算法4.1 从顶点v0出发深度优先遍历g中能访问的各个顶点 void dfs(int v0) visitedv0=1; /*访问标志置为 1，表示已被访问*/ w=firstadj(g,v0); /* w是vo的第一个邻接点 */ while (w!=0) if(visitedw=0) dfs(w); /*顶点未被访问，则递归的进行深度遍历 */ w=nextadj(g,v0,w) /*顶点已访问，则取顶点v0在w后面的下一个邻接点 */ ,深度优先遍历的递归算法:,$4.3 图图的遍历,几点说明：,2. firstadj (g,V0)和nextadj(g,V0,w)两个函数的实现与图的具体存储结构有关,$4.3 图图的遍历,算法4.2 图的深度优先遍历算法 void travergraph(g) /* 对图g进行深度优先遍历 */ for(i=1;i=n;i+) visitedi=0; /* 标志数组初始化 */ for(i=1;i=n;i+) if(visitedi=0) dfs(i); /* 深度优先遍历时调 用dfs(i) */ ,思考：travergraph调用 dfs的次数由什么决定？ 图若采用邻接矩阵存储,编写相应的firstadj(g,V0)和nextadj(g,V0,w),算法4.1 从顶点v0出发深度优先遍历g中能访问的各个顶点 void dfs(int v0) visitedv0=1; /*访问标志置为 1，表示已被访问*/ w=firstadj(g,v0); /* w是vo的第一个邻接点 */ while (w!=0) if(visitedw=0) dfs(w); /*顶点未被访问，则递归的进行深度遍历 */ w=nextadj(g,v0,w) /*顶点已访问，则取顶点v0在w后面的下一个邻接点 */ ,$4.3 图图的遍历,如何实现非递归算法?,当然是栈了!,$4.3 图图的遍历,二、广度优先搜索（breadth-first-search),首先访问指定顶点v0，将v0作为当前顶点; 访问当前顶点的所有未访问过的邻接点， 并依次将访问的这些邻接点作为当前顶点; 重复2， 直到所有顶点被访问为止。,对右图广度优先搜索，访问顶点序列为： V1 V2 V3 V4 V5 V6 V7 V8,S,电子科技.计算机学院.数据结构与算法,$4.3 图图的遍历,广度优先遍历的 非递归算法怎么实现?,对每一个当前访问顶点, 一次性访问其所有的邻接点, 您认为采用什么数据结构可以实现非递归算法?,队列!,Smarter!,S,电子科技.计算机学院.数据结构与算法,$4.3 图图的遍历,算法4.3 从顶点v0出发广度优先遍历g中能访问的各个顶点 Void bfs(Graph g,int v0) /* 从v0出发广度优先遍历图g */ visitedv0=1; Enqueue(Q,v0); While (!Empty(Q) v=Dlqueue(Q); /* 取队头元素v */ w=Firstadj(g,v); /* 求v的第一个邻接点 */ while(w!=0) if(visitedw=0) visitedw=1; Enqueue(Q,w); w=Nextadj(g,v,w); /* 求下一个邻接点 */ ,$4.4 图图的应用-最小生成树,右图为一个新兴小镇.其中6个红色小块为社区房屋, 2个白色小块为商店. 现在要铺设天然气管道, 造价和天然气管长度成正比. 如何铺设管道使得所有房屋和商店都通气且造价最低?,$4.4 图图的应用-最小生成树,Idea : 实质是求图的包含所有顶点的具有最少边数的连通图,且边权值和最小.,Target : 1. 求出图的具有最少边数的连通子图 2. 求出上述子图图中边取值和最小的连通子图,$4.4 图图的应用-最小生成树,一、最小生成树概念 1. 设无向连通图G=（V，E）， 其子图G=（V，T）满足： V(G)=V(G) n个顶点 G是连通的 G中无回路 则G是G的生成树,$4.4 图图的应用-最小生成树,具有n个顶点的无向连通图G 其任一生成子图G恰好含n-1条边 生成树不一定唯一,4个顶点选择3条边有 如下5种形状(54= 20种): 其中16种为生成树,（保证了连通）,$4.4 图图的应用-最小生成树,生成树代价,对图中每条边赋于一个权值（代价），则构成一个网， 网的生成树G=(V，T)的代价是T中各边的权值之和， 最小生成树就是网上所有可能的生成树中，代价最小的一类生成树。 最小生成树也不一定唯一。,$4.4 图图的应用-最小生成树,您能够想出更多采用 最小生成树解决问题的实例吗?,$4.4 图图的应用-最小生成树,例1：,N台计算机之间建立通讯网,顶点表示computer,边表示通讯线,权值表示通讯线的代价（通讯 线长度，computer间距离等）,要求：, n台计算机中的任何两台能通过网进行通讯； 使总的代价最小。-求最小生成树T,$4.4 图图的应用-最小生成树,$4.4 图图的应用-最小生成树,Problem : 如何求解带权图的最小生成树?,$4.4 图图的应用-最小生成树,二、最小生成树性质MST,设N=（V，E）是一个连通网， U是顶点集V的一个非空子集。 若（u，v）是一条具有最小权值的边，其中uU,vV-U, 即（u，v）=Mincost(x,y)|xU,yV-U 则必存在一棵包含边（u，v）的最小生成树。,含义：将顶点分为两个不相交的集合U和V-U， 若边（u，v）是连接这两个顶点集的最小权值边，则边（u，v）必然是某最小生成树的边。,$4.4 图图的应用-最小生成树,基本思想： 取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点u 之间必定存在一条边，并且该边的权值在所有连通顶点 u 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n个顶点为止。,普里姆（Prim）最小生成树算法,$4.4 图图的应用-最小生成树,a,b,c,d,e,g,f,例如:,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,g,f,7,14,8,5,3,16,21,所得生成树权值和,= 14+8+3+5+16+21 = 67,$4.4 图图的应用-最小生成树,普里姆（Prim）最小生成树算法,设 N=（V，E）是一个连通网， V=1，2，n是N的顶点集合， 辅助集合U，初值为Uo， 用来存放当前所得到的最小生成树的顶点； 辅助集合TE，初值为， 用来存放当前所得到的最小生成树的边。,$4.4 图图的应用-最小生成树,在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U ，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。,所添加的顶点应满足下列条件:,$4.4 图图的应用-最小生成树,Prim 算法 步骤,1. TE=,U=u0 2. 当UV，重复下列步骤： (1)选取（u0,v0)=mincost(u,v)|uU,vV-U，保证不形成回路 (2)TE=TE+（u0,v0), 边（u0,v0)并入TE (3)U=U+V0，顶点V0 并入U,特点: 以连通为主 选代价最小的邻接边,/* 用prim算法从序号为0的顶点出发构造有vtxnum个顶点的邻接矩阵存储结构的网gn的最小生成树T，并输出T的各条边 */ void minispantree_PRIM(int gnmax,int vtxnum) int v,i,j,k; float min; for(v=1;v0) * / printf(“”,closedgek.vex, k); /* 输出生成树的边 */ closedgek.lowcost=0; /* 顶点k并入U */ for(v=1;vvtxnum;v+) /*新顶点并入U后，重选最小代价边*/ if(gnkvclosedgev.lowcost) Closedgev.lowcost=gnkv; Closedgev.vex=k; ,时间复杂度为O(n2),$4.4 图图的应用-最小生成树,/* 此函数求得k值，使closedgek.lowcost=MIN( closedgev.lowcost | v V-U and closedgev.lowcost0) * / int minimum(closedge) int min,h,k; min=; h=1; for(k=1;kvtxnum;k+) if (closedgek.lowcost!=0 ,$4.4 图图的应用-最小生成树,算法的几点说明: 1. gn为 网的邻接矩阵 即 gni, j=wij 或 为无穷大 2. 辅助数组closedge1n 有两个分量: closedgek.vex存放边(k, j)依附的另一顶点j( jU) closedgek.lowcost存放边(k, j)的权值，当值为0时， 表示顶点k已加入到集合U中。 区别顶点 U或V-U，是根据，.lowcost=0 U . lowcost0 V-U closedgek.vex U 而 k V-U,$4.4 图图的应用-最小生成树,例子：,$4.4 图图的应用-最小生成树,具体做法: 先构造一个只含 n 个顶点的子图 T，然后从权值最小的边开始，若它的添加不使T 中产生回路，则在 T中加上这条边，如此重复，直至加上 n-1 条边为止。,考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。,克鲁斯卡尔（Kruskal）最小生成树算法,$4.4 图图的应用-最小生成树,Kruskal 算法是逐步给生成树T中添加不和T中的边构成回路的当前最小代价边。 特点: 以最小代价边主。 设N=（V，E）是个连通网, 算法步骤为： 1. 置生成树T的初始状态为T=（V，） 2. 当T中边数n-1时, 重复下列步骤: 从E中选取代价最小的边（v, u）, 并删除之; 若（v, u）依附的顶点v和u落在T中不同的连同分量上， 则将边（v, u）并入到T的边集中； 否则，舍去该边，选择下一条代价最小的边.,$4.4 图图的应用-最小生成树,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,a,e,12,d,c,b,g,f,7,14,8,5,3,16,21,例如:,7,12,18,19,$4.4 图图的应用-最小生成树,算法描述,构造非连通图 T=( V, ); k = i = 0; / k 计选中的边数 while (kn-1) +i; 检查边集 E 中第 i 条权值最小的边(u,v); 若(u,v)加入T后不使T中产生回路， 则 输出边(u,v); 且 k+; ,$4.4 图图的应用-最小生成树,普里姆和克鲁斯卡尔最小生成树算法比较,普里姆最小生成树算法 以连通为主 选保证连通的代价最小的邻接边（n-1次） 普里姆算法的时间复杂度与边无关，为O(n2) 适合于求边稠密网的最小生成树。,克鲁斯卡尔最小生成树算法 以最小代价边主 添加不形成回路的当前最小代价边 算法时间复杂度与边相关，为(elog2e) 适合于求边稀疏网的最小生成树,$4.4 图图的应用-拓扑排序,Example Courses needed for a computer science degree at a hypothetical university,How shall we convert this list into a graph?,$4.4 图图的应用-拓扑排序,这种课程安排合理吗? 如果每学期最多安排3门课程, 5学期安排学完所有课程, 如何安排?,Idea :假设以有向图表示一个工程的施工图，则图中不允许出现回路。,$4.4 图图的应用- 拓扑排序topological sort,拓扑排序是一种对非线性结构的有向图进行线性化的重要手段。,检查有向图中是否存在回路的方法之一，是对 有向图进行拓扑排序。,$4.4 图图的应用-拓扑排序,1、AOV网(Activity on vertex network) 一个有向图可用来表示一个施工流程图、一个产品生产流程图、或一个程序框图等。,课程安排,施工从活动 a1、 a2开始，到达活动 a8和 a9时，整个施工结束。 有向图中，顶点表示活动，弧表示活动 ai优先于活动 aj ， 称这类有向图为顶点表示活动的网（AOV网）。,$4.4 图图的应用-拓扑排序,AOV网可解决如下两个问题： （1）判定工程的可行性。显然，有回路，整个工程就无法结束 （2）确定各项活动在整个工程执行中的先后顺序。 称这种先后顺序为拓扑有序序列。,如图有如下拓扑有序序列： a1 a2 a3a4 a6 a5 a7 a8 a9 a2 a6 a1 a3 a4 a5 a7 a9 a8,$4.4 图图的应用-拓扑排序,对于下列有向图,不能求得它的拓扑有序序列。,因为图中存在一个回路 B, C, D,B,D,A,C,$4.4 图图的应用-拓扑排序,我已经知道什么叫 拓扑排序了,但是具体怎么做呢?,一个工程什么时候能够开始?,我的意思是怎么写 算法和程序?,当然是在这个工程之前 的其他工程都已经完成了!,Good! 如何判断一个工程 前面的工程都已经完成?,AOV网中没有 前驱的顶点!,Smart!,$4.4 图图的应用-拓扑排序,拓扑排序算法,算法步骤 (1) 在AOV网中，选取一个没有前驱的顶点输出； (2) 删除该顶点和所有以它为弧尾的弧； (3) 重复以上两步，直到 AOV网中全部顶点都已输出（得到拓扑有序序列） 或者，图中再无没有前驱的顶点（AOV网中有环）,$4.4 图图的应用-拓扑排序,【例4.2】P156： 顶点C0入度为0，选择输出C0，并删除C0及其所有出边得图(b)。这时入度为0的顶点是C1和C3，选择输出C1,并删除C1和它的所有出边，得图(c)。 依次选择C2，C3，C4，C5，C6，C7输出。 最后得到的拓扑序列为C0， C1 ，C2，C3，C4，C5，C6，C7,$4.4 图图的应用-拓扑排序,如何实现算法中的(1)和(2)？ 对于(1)，没有前驱的顶点即入度为0的顶点； 对于(2)，删除以它为弧尾的所有弧，即让该顶点的所有直接后继的入度减1。,由此分析知：拓扑排序算法的实现与顶点的入度有密切关系，因此，在选取存储结构时，应考虑： 能容易得到各顶点的入度； 有利于寻找任一顶点的所有直接后继。 为此，采用邻接表作为AOV网的存储结构，并在头结点中增加一个存放顶点入度的域（indegree）,Void findIndegree(algraph g ,int *indegree) /* 求出图中所有顶点的入度 */ int i; arcnode * p; for(i=0;iadjvex; p=p-nextarc; ,$4.4 图图的应用-拓扑排序,使用栈记载入度为0的顶点（没有前驱或前驱已经输出的顶点） 先将入度为0的顶点入栈； 用栈进行控制： 输出栈顶顶点，并将其后继顶点的入度减1，若为0，则将该顶点入栈； 直到栈空，若输出顶点数=图的顶点数，则图无回路，得到一个拓扑有序序列，否则图存在回路。,$4.4 图图的应用-拓扑排序,$4.4 图图的应用-关键路径,下表给出了某工程各工序之间的优先关系和各工序所需的时问（其中“一”表示无先驱工序），指明完成该工程所需的最短时间。如果因为其他原因,C所需时间变为 4,会不会影响工期? 如果A所需时间变为4,会不会影响工期呢? 哪些工序影响工期,哪些不会影响? 不会影响的范围是多少?,$4.4 图图的应用-关键路径,AOE网（activity on edge） 若有向图中，顶点表示事件，弧表示活动，弧上的权表示完成该活动所需的时间，则称这类有向图为边表示活动的网（AOE网） AOE网中仅有一个入度为0的事件，称为源点，它表示工程的开始；网中也仅有一个出度为0的事件，称为汇点，它表示工程的结束。 每一事件V表示以它为弧头的所有活动已经完成，同时，也表示以它为弧尾的所有活动可以开始。,S,电子科技.计算机学院.数据结构与算法,$4.4 图图的应用-关键路径,AOE网可解决如下问题： 估算工程的最短工期（从源点到汇点至少需要多少时间） 找出哪些活动是影响整个工程进展的关键,有4个事件：V1， V2， V3， V5 V1为源点，V5为汇点 有4个活动：a1, a2, a4, a5 V3表示：a2已完成，a5可以开始,S,电子科技.计算机学院.数据结构与算法,$4.4 图图的应用-关键路径,2、术语 路径长度：路径上各活动持续时间的总和 （即：路径上所有弧的权值之和） 关键路径：从源点到汇点之间路径长度最长的路径， （不一定唯一） 事件Vi的最早发生时间ev(i)：从源点到Vi的最长路径长度 活动 ai的最早开始时间e(i)：等于该活动的弧尾事件Vj的最早发生时间 即若表示活动ai ，则有e(i)=ev(j),S,电子科技.计算机学院.数据结构与算法,$4.4 图图的应用-关键路径,事件 vk 的最迟发生时间 lv(k)：是在不推迟整个工期的前提下，该事件最迟必须发生的时间 活动ai的最迟开始时间l(i)：是该活动的弧头事件的最迟发生时间与该活动的持续时间之差， 即l(i)=lv(k)- ai 的持续时间 关键活动：l(i)=e(i)的活动,由此可见：在AOE网中找关键活动问题可转化为求 l(i)=e(i)，而e(i)=ev(j) l(i)=lv(k) - ai 的持续时间 因此，需先求出事件的最早、最迟发生时间,S,电子科技.计算机学院.数据结构与算法,$4.4 图图的应用-关键路径,3、关键路径算法思想 1） 从ve(1)=0 开始利用下面递推公式，计算出各事件的最早发生时间 其中：p是所有以k为头的弧集合， W表示活动的持续时间 前例中，v(5)=Maxev(2)+W， ev(3)+W =Max6+1,4+1=7,$4.4 图图的应用-关键路径,2） 从lv(n)=ev(n)开始，利用下面递推公式，计算出各事件的最迟发生时间： 其中：S是所有以j为尾的弧集合,前例中，Lv(5)=ev(5)=7 Lv(2)=Lv(5)-1=6 Lv(3)=Lv(5)-1=6 Lv(1)=MinLv(2)-W(，Lv(3)-W =Min6-6,6-4=0,S,电子科技.计算机学院.数据结构与算法,$4.4 图图的应用-关键路径,3） 设活动ai由弧表示，其持续时间为w，则利用下面公式，计算出各活动的最早、最迟开始时间： e(i)=ev(j) l(i)=Lv(k)-w 4） 找出e(i)=l(i)的活动，即为关键活动，诸关键活动组成的从源点到汇点的路径即为关键路径。,S,电子科技.计算机学院.数据结构与算法,例. 求下面AOE网的关键路径,计算结果为： 顶点 ev lv 活动 弧 持续T e l l-e 关键活动 V1 0 0 a1 3 0 1 1 V2 3 4 a2 2 0 0 0 a2 V3 2 2 a3 2 3 4 1 V4 6 6 a4 3 3 4 1 V5 6 7 a5 4 2 2 0 a5 V6 8 8 a6 3 2 5 3 a7 2 6 6 0 a7 Max + Min - a8 1 6 7 1,e(i)=ev(j) l(i)=lv(k)-w,S,电子科技.计算机学院.数据结构与算法,$4.4 图图的应用-关键路径,例. 求下面AOE网的关键路径, 计算 ev(i): 从v0开始, 计算 lv(i): 从v8开始,2,3,2, 关键活动: ai | e ( i ) = l ( i ) 关键路径: = v0v1v4v6v8, 计算 e(i): 从a0开始, 计算 l(i): 从a10开始,S,电子科技.计算机学院.数据结构与算法,$4.4 图图的应用-关键路径,关键路径上的活动都是关键活动。 缩短非关键活动都不能缩短整个工期 如a6缩短为1，则整个工期仍为8。 又如a6推迟3天开始，或拖延3天完成 a6=6）均不影响整个工期 分析关键路径的目的是找出影响整个工期的关键活动，缩短关键活动的持续时间，常可以缩短整个工期。 如a7缩短为1，则整个工期为7。 此时，再缩短任一关键活动均不能缩短整个工期。 即在有多条关键路径时，缩短那些在所有关键路上的关键活动，才能缩短整个工期,S,电子科技.计算机学院.数据结构与算法,int criticalpath(algraph * paoe) /*算法4.7 关键路径算法(P161) */ int i,j,k; int evvexnum,lvvexnum,larcnum,earcnum; arcnode * p; Topo topo; if(toposort(paoe, ,S,电子科技.计算机学院.数据结构与算法,int criticalpath(algraph * paoe) /*算法4.7 */ int i,j,k; int evvexnum,lvvexnum,larcnum,earcnum; arcnode * p; Topo topo; if(toposort(paoe, ,求事件vj的最早发生时间ev(j）是按拓扑有序的次序,S,电子科技.计算机学院.数据结构与算法,int criticalpath(algraph * paoe) /*算法4.7 关键路径算法(P161) */ if(toposort(paoe, ,求事件vj的最迟发生时间lv(j）是按拓扑逆序的次序,S,电子科技.计算机学院.数据结构与算法,int criticalpath(algraph * paoe) /*算法4.7 关键路径算法(P161) */ if(toposort(paoe, ,$4.4 图图的应用 -最短路径（ Shortest Paths ）,如果从峨眉山出发,每年要从九寨沟,黄山,香港,拉斯维加斯等地选择一个旅游景点旅游, 已知各地旅游线路间的机票价格如图所示, 到各个旅游点的机票最低开销是多少?,$4.4 图图的应用 -最短路径（ Shortest Paths ）,怎么求最低开销呢?,观察! 实质就是求图一个顶点到其他顶点的最短路径!,S,电子科技.计算机学院.数据结构与算法,$4.4 图图的应用 -最短路径（ Shortest Paths ）,1.单源点最短路径 是指给定带权有向图D和源点v，求从源点v到D中其余各顶点之间的最短路径 2.所有顶点对之间的最短路径 求D中各顶点对之间的最短路径,在有向图中，寻找从某个源点到其余各个顶点或者每一对顶点之间的最短带权路径的运算，称为最短路径问题。,S,电子科技.计算机学院.数据结构与算法,$4.4 图图的应用 -最短路径（ Shortest Paths ）,【例4.4】图4-30所示带权有向图中从v0到其余各顶点之间的最短路径，如表4-4所示。从图中可见，从v0到v3有两条不同的路径：(v0,v2,v3)和(v0,v4,v3)，前者长度为60，而后者长度为50。因此，后者是从v0到v3的最短路径。而从v0到v1没有路径。,S,电子科技.计算机学院.数据结构与算法,$4.4 图图的应用 -最短路径（ Shortest Paths ）,1. 迪杰特拉（Dijkstra） 算法： 算法思想：按路径长度递增的次序产生到各顶点的最短路径 使用DS： 利用带权邻接矩阵 表示当前找到的从源点V0到每个终点Vi的最短路径长度的辅助向量disti 存储最短路径的向量pathi 表示已找到从V0出发的最短路径的终点的集合S,S,电子科技.计算机学院.数据结构与算法,$4.4 图图的应用 -最短路径（ Shortest Paths ）,算法步骤： 1. 用邻接矩阵初始化dist；置S=V0； 2. 选择Vj,使得：distj=Mindisti|ViV-S Vj 就是当前求得的从V0出发的最短路径的终点，并将Vj并入S； 3. 对V-S上的所有顶点Vk，修改： distk=Mindistj+costj, k, distk 4. 重复2，3， n-1次。,$4.4 图图的应用 -最短路径（ Shortest Paths ）,例子,终点 从v0 到各终点的 dist 值和最短路径,v1,v2,v4,v3,v5,vj,$4.4 图图的应用 -最短路径（ Shortest Paths ）,算法4.8 迪杰斯特拉（Dijkstra）算法（P164） void Dijkstra(Mgraph Gn, int v0,int path,int dist) /* 求有向网Gn的v0顶点到其余顶点v的最短路径， */ int sVEX_NUM; /* s标记已找到最短路径的顶点,初值只包括v0，即s0=1*/ /* dist记录源点到其他各顶点当前的最短距离，其初值为： disti = G.arcs0i i=1，2，n-1*/ for(int v=0; vVEX_NUM; v+) sv = 0; distv = Gn.arcsv0v; if( distv MAXINT ) pathv = v0; else pathv = -1; distv0 = 0; sv0 = 1; /*初始时源点v0S集*/,/* 循环求v0到某个顶点v的最短路径，并将v加入S集*/ /*算法执行时从S以外的顶点集合（V -S）中选出一个顶点w，使distw的值最小。 然后将w加入集合S中，即sw=1；同时调整集合（V-S）中的各个顶点的距离值： 从原来的distj和distw+costwj中选择较小的值作为新的distj。重复上述过程， 直到S中包含图中所有顶点，或再也没有可加入到S中的顶点为止。*/ for(int i=1; iVEX_NUM-1; i+) int min = MAXINT; v=-1; for(int w=0; wVEX_NUM; w+) /* 找出最小的distw */ if(!sw /*if*/ /*for*/ ,2、每一对顶点之间的最短路径 每次以一个顶点为源点，调用Dijkstra算法n次，O（n3）； 弗洛伊德算法(Floyed) 弗洛伊德算法思想：,定义一个n阶方阵序列为D(-1)，D(0)， D(1) ， D(k-1) ， D(n-1) ， 可用如下的数学表达式描述弗洛伊德算法： D(-1)ij=co