数据结构 课件 第七章 图2.ppt

《数据结构 课件 第七章 图2.ppt》由会员分享，可在线阅读，更多相关《数据结构 课件 第七章 图2.ppt（63页珍藏版）》请在三一文库上搜索。

1、深度优先搜索遍历算法及广度优先搜索遍历算法中遍历图过程中历经边的集合和顶点集合一起构成连通图的极小连通子图。它是连通图的一颗生成树。 生成树：是一个极小连通子图，它含有图中全部顶点，但只有n-1条边。 由深度优先搜索遍历得到的生成树，称为深度优先生成树，由广度优先搜索遍历得到的生成树，称为广度优先生成树。,7.4.1 生成树及生成森林,7.4 最小生成树,深度遍历：V0 V1 V3 V7 V4 V2 V5 V6,广度遍历：V0 V1 V2 V3 V4 V5 V6 V7,生成森林： 若一个图是非连通图，但有若干个连通分量，则通过深度优先搜索遍历或广度优先搜索遍历，不可以得到生成树，但可以得到生成

2、森林，且若非连通图有n个顶点，m个连通分量，则可以遍历得到m棵生成树，合起来为生成森林，森林中包含n-m条树边。,深度优先生成森林,说明: 一个图可以有许多棵不同的生成树 所有生成树具有以下共同特点： 生成树的顶点个数与图的顶点个数相同 生成树是图的极小连通子图 一个有n个顶点的连通图的生成树有n-1条边 在生成树中再加一条边必然形成回路 生成树中任意两个顶点间的路径是唯一的 含n个顶点n-1条边的图不一定是生成树,7.4.2 最小生成树,1、最小生成树 对于带权的连通图G，其生成树也是带权的。我们把生成树各边的权值总和称为该生成树的权。并且将权最小的生成树称为最小生成树。,2. 求最小生成树

3、,首先明确： 使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。 按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。,即有权图,目标： 在网络的多个生成树中，寻找一个各边权值之和最小的生成树。,构造最小生成树的准则 必须只使用该网络中的边来构造最小生成树； 必须使用且仅使用n-1条边来联结网络中的n个顶点； 不能使用产生回路的边。,1、问题提出 要在n个城市间建立通信联络网， n个城市间，最多可设置n(n-1)/2条线路； n个城市间建立通信网，只需n-1条线路； 问题转化为：如何在可能的线路中选择n-1条，能把 所有城市（顶点）

4、均连起来，且总耗费（各边权值之和）最小。,典型用途：,希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小最小生成树MST(Minimum Cost Spanning Tree),数学模型： 顶点表示城市，有n个； 边表示线路，有n1条； 边的权值表示线路的经济代价； 连通网表示n个城市间通信网。,2、问题分析,7.4.3 构造最小生成树方法(一)：Prim算法,假设G=(V,E)是一个具有n 个顶点的连通网络，G=(U,T)是G的最小生成树，其中U是G的顶点集，T是G的边集，U和T的初值均为空。 1、从V中任取一个顶点（假定为u1），将此顶点并入U中，此时最小生成

5、树顶点集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 Prim算法,P

6、rim方法构造过程,1,U: V-U:,1,4,3,2,5,6,普里姆(Prim)算法,Prim算法可用下述过程描述： （1）Uu1，T=； （2）while （UV）do （u，v）minwuv；uU，vVU TT（u，v） UUv （3）结束。,有关数据的存储结构 设置两个辅助数组： lowcost用来保存集合VU中各顶点与集合U中各顶点构成的边中具有最小权值的边的权值； adjvex用来保存依附于该边的在集合U中的顶点。,普里姆(Prim)算法,普里姆(Prim)算法,0 0 0 0 0 0 0 6 1 5 max max,i adjvex lowcost,0 1 2 3 4 5,i a

7、djvex lowcost,0 1 2 3 4 5,0 2 0 0 2 2 0 5 0 5 6 4,U= v0,U= v0,v2,V-U= v1,V2,V3,V4,V5 ,V-U= v1, V3,V4,V5 ,普里姆(Prim)算法,0 0 0 0 0 0 0 6 1 5 max max,lowcost,0,i,adjvex,0 1 2 3 4 5,U,7.4.4 构造最小生成树方法（二）：Kruskal算法,假设G =（V，E）是一个具有n个顶点的连通网络， G=(U,T)是G 的最小生成树，U的初值等于V，即包含有G中的全部顶点，T的初值为空集。 基本思想：将图G中的边按权值从小到大的顺序

8、依次选取，若选取的边使生成树G不形成环路，则把它并入T中，保留作为生成树G的一条边，若选取的边使生成树G形成环路，则将其舍弃，如此进行下去，直到T中包含n-1条边为止。此时的T即为最小生成树。,7.4.4 克鲁斯卡尔(Kruskal)算法,克鲁斯卡尔算法,有关数据的存储结构 设置一个结构数组arr存储网中所有的边，边的结构类型包括构成的顶点信息和边权值 。 #define MaxEdge typedef struct int v1, v2； int cost； EdgeNode； EdgeNode arrMaxEdge； 事先把数组arr中的各元素按照其cost域值由小到大的顺序排列。,设置一

9、个数组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 ,初始化根结点数组,依次搜索每条边的两个顶点所在树的根结点,不属于同一连通分量，合并，把u1作为u2的根

10、,即把顶点v1根（u1）作为顶点v2 根（u2）的根结点,演 示,7.5 最短路径,1、问题提出与数学模型 问题：在一个交通网络中，如何找到城市A到城市B之间一条距离最近或花费最少的通路？ 用带权的有向图表示一个交通运输网，图中： 顶点表示城市 边表示城市间的交通联系 权表示此线路的长度或所花费的代价 数学模型： 从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径最短路径,8,5,6,2,30,13,7,17,32,9,13,长度,最短路径,8,13,19,21,20,注：最短路径与最小生成树不同，路径上不一定包含n个顶点。,7.5 最短路径,两种最常见的最短路径问

11、题： 一顶点到其余各顶点的最短路径 单源点最短路径用Dijkstra算法 任意两顶点间的最短路径 所有顶点间的最短路径用Floyd算法,7.5 最短路径,1、迪杰斯特拉(Dijkstra)算法思想 按路径长度递增次序产生最短路径算法： 把V分成两组： （1）S：已求出最短路径的顶点的集合； （2） T = V-S：尚未确定最短路径的顶点集合。 将T中顶点按最短路径递增的次序加入到S中。,7.5.1 从某个源点到其余各顶点的最短路径(1),单源点最短路径：是指给定一个出发点（单源点）和一个有向网G=(V,E)，求出源点到其它各顶点之间的最短路径。,2、求最短路径步骤 采用邻接矩阵costNN来存

12、储带权有向图。 1)令 S=V0,T=其余顶点， T中顶点对应的距离值:若存在，为弧上的权值，若不存在，为。 2)从T中选取一个其距离值为最小的顶点W，加入S。 3)对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要长，则修改此距离值。 4)重复上述步骤，直到S中包含所有顶点，即S=V为止,7.5.1 从某个源点到其余各顶点的最短路径(2),13 8 30 32 V2:8 ,13 - 13 30 32 V1:13 ,- - 13 30 22 20 V3:13 ,- - - 19 22 20 V4:19 ,终点 从V0到各终点的最短路径及其长度,V1 V2 V3

13、 V4 V5 V6 Vj,- - - - 21 20 V6:20 ,Dijkstra算法求最短路径的过程,S,V0,V2,V0,V2,V1,V0,V2,V1,V3,V0,V2,V1,V3,V4,V0,V2,V1,V3,V4,V6, ,顶点对之间的最短路径概念 所有顶点对之间的最短路径是指：对于给定的有向网G=(V,E),要对G中任意一对顶点有序对u、v(uv),找出u到v的最短距离。 解决此问题的一个有效方法是:轮流以每一个顶点为源点,重复执行迪杰斯特拉算法n次,即可求得每一对顶点之间的最短路径,总的时间复杂度为O(n3)。 下面将介绍用弗洛伊德(Floyd)算法来实现此功能,时间复杂度仍为O

14、(n3),但该方法比调用n次迪杰斯特拉方法更直观一些。,7.5.2 所有顶点对之间的最短路径,采用邻接矩阵costNN来存储带权有向图。 算法的基本思想是: 设置一个N*N的矩阵ANN，其中除对角线的元素都等于0外，其它元素Aij的值表示顶点i到顶点j的最短路径长度。 运算步骤为：首先，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为，此时, A ij=costij, 以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。,弗洛伊德算法(1),具体做法为： 第一步，让所有边上加入中间顶点

15、V0，取Aij与Ai0+A0j中较小的值作Aij的值. 第二步，让所有边上加入中间顶点V1，取Aij与Ai1+A1j中较小的值，为Aij 的值， 如此进行下去，当第n步完成后，得到 Aij ,即为我们所求结果, A ij表示顶点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),弗洛伊德算法求最短路径的过程,7.6 有向无环图及其应用,7.6.1 有向无环图的概念 一个无环的有向图称做有向无环图（Di

16、rected Acycline Graph），简称DAG图。下面是有向树、DAG图和有向图的例子。,有向树 DAG图 有向图,检查一个有向图是否存在环要比无向图复杂。 对于无向图来说，若深度优先遍历过程中遇到回边(指向已访问过的顶点的边)，则必定存在环； 而对于有向图来说，这条回边很有可能不构成环，它有可能是指向深度优先生成森林中另一棵生成树上顶点的弧。但是，如果从有向图上某个顶点v 出发的遍历，在DFS（v）结束之前出现一条从顶点u到顶点v的回边，由于u 在生成树上是v的子孙，则有向图必定存在包含顶点v和u的环。,7.6 有向无环图及其应用,7.6 有向无环图及其应用,有向无环图也是描述一项

17、工程或系统的进行过程的有效工具。几乎所有的工程（Project）都可分为若干个称作活动（Activity）的子工程，而这些子工程之间，通常受着一定条件的约束，如其中某些子工程的开始必须在另一些子工程完成之后。 对整个工程和系统，人们关心的是两个方面的问题： 一是工程能否顺利进行： 二是估算整个工程完成所必须的最短时间。 下面我们通过对有向图进行拓扑排序和关键路径操作来解决这两个问题。,1、AOV网： 在一个有向图中，若用顶点表示活动，有向边表示活动间先后关系，称该有向图叫做顶点表示活动的网络(Activity On Vertex network)简称为AOV网。 在工程实践中，一个工程项目往往

18、由若干个子项目组成，这些子项目间往往有多种关系： 先后关系 子项目之间无次序要求。 如果从顶点Vi到Vj之间存在有向边,则表示活动i必须先于活动j进行。,7.6.2 AOV网与拓扑排序,在AOV网络中，如果顶点Vi的活动必须在顶点Vj的活动以前进行，则称Vi为Vj的前趋顶点，而称Vj为Vi的后继顶点。这种前趋后继关系有传递性。 AOV网络中一定不能有有向环路。例如在下图那样的有向环路中，V0是V1的前趋顶点，V1是V2的前趋顶点，V2是V3的前趋顶点， V3又是V0的前趋顶点，环路表示顶点之间的先后关系进入了死循环。 因此，对给定的AOV网络首先要判定网络中是否存在环路，只有有向无环路网络在应

19、用中才有实际意义。,7.6.2 AOV网与拓扑排序,课程流程图,有一些课程必须在先学完某些先修课程之后才能开始学习。如数据结构就必须安排在离散数学和程序设计之后 。,7.6.2 AOV网与拓扑排序,拓扑排序的定义 给出有向图G=(V,E)，对于V中的顶点的线性序列(vi1,vi2,.,vin)，如果满足如下条件：若在G中从顶点 vi 到vj有一条路经，则在序列中顶点vi必在顶点 vj之前；则称该序列为 G的一个拓扑序列（Topological order）。构造有向图的一个拓扑序列的过程称为拓扑排序（Topological sort）。 所谓“拓扑排序”就是将AOV网络中的各个顶点(各个活动)

20、排列成一个线性有序序列，使得所有要求的前趋、后继关系都能得到满足。,2、拓扑排序,说明 (1)在AOV网中, 不存在回路。 AOV网所代表的一项工程中活动的集合，为了保证该项工程得以顺利完成，必须保证AOV网中不出现回路；否则，意味着某项活动应以自身作为能否开展的先决条件，这是荒谬的。 (2)拓扑序列不是唯一的。 由于AOV网络中有些顶点之间没有次序要求，它们在拓扑有序序列中的位置可以任意颠倒，所以拓扑排序的结果一般并不是唯一的。 通过拓扑排序还可以判断出此AOV网络是否包含有有向环路，若有向图G所有顶点都在拓扑排序序列中，则AOV网络必定不包含有有向环路。,如图：可以得到不止一个拓扑排序：

21、C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8 C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8 显然，对于任何一项工程中各个活动的安排，必须按拓扑有序序列中的顺序进行才是可行的。,2、拓扑排序,拓扑排序的方法 (1) 在AOV网络中选择一个没有前趋的顶点（入度为0），并把它输出； (2) 从网络中删去该顶点和从该顶点发出的所有有向边； (3) 重复执行上述两步，直到网中所有的入度为0的顶点都被输出 。 如果进行到某一步，网中还有顶点，但无法找到无前趋的顶点（没有入度为0的顶点），则说明此AOV网络中存在有向环路，遇到这种情况，拓扑排序

22、就无法进行了。,拓扑排序的方法,v2,AOV网上实施步骤的例子,拓扑序列为： V1,V4,V6,V3,V5,V2,拓扑排序算法： 以邻接表作存储结构，并且增加一个数据域用于记录顶点入度。,typedef struct vnode int indegree； VertexType vertex； EdgeNode * firstedge； VertexNode；,拓扑排序算法：,算法中可设置一个堆栈，凡是网中入度为0 的顶点都将其入栈。为此，拓扑排序的算法步骤为： 把邻接表中所有入度为0（没有前驱）的顶点进栈 栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；

23、若Vk的入度为0则进栈 重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕。,拓扑排序算法,注意：用邻接表作为它的存储结构，各表头结点的indegree域存放相应顶点的入度值。每个顶点入度初值可随邻接表动态生成过程中累计得到。 采用栈来存放当前未处理过的入度为零点的结点，但并不需要额外增设栈的空间，而是设一个栈顶位置的指针将当前所有未处理过的入度为零的结点连接起来，形成一个静态链式栈。,拓扑排序算法,void Topo_Sort (AlGraph *G) int top = -1; for (i=0;iadjlisti. indegree= 0) G-ad

24、jlisti.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的顶点，即有环,从栈中退出一

25、个顶点并输出，使top指向下一个度为0的顶点。,使ptr指向已删除顶点的邻接表,当前输出顶点的邻接点的入度减1,新的入度为0的顶点进栈,一、AOE网概念 1.定义 若在带权的有向图中,以顶点表示事件,有向边表示活动,边上的权值表示完成该活动的开销(如该活动所需的时间),则称此带权的有向图为用边表示活动的网络,简称AOE网(Activity On Edge),7.6.3 AOE网与关键路径,2.说明 (1) AOV网与AOE网有密切关系又有不同。 如果用他们表示工程，AOV网表示各个子工程之间的优先关系，是定性关系；在AOE网中还要体现完成各个子工程的确切时间，是定量关系。 （2）在AOE网中，

26、只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。只有在进入该顶点的各有向边所代表的活动都已经结束后，该顶点所代表的事件才能发生。 （3）在一个表示工程的AOE网中，应该不存在回路，网中仅存在一个入度为零的顶点，作为开始顶点，它表示了整个工程的开始；网中仅存在一个出度为零的顶点，称为结束顶点，它表示整个工程的结束。,7.5.2 AOE网与关键路径,把工程计划表示为有向图，用顶点表示事件，弧表示活动； 每个事件表示在它之前的活动已完成，在它之后的活动可以开始. 例 设一个工程有11项活动，9个事件 事件 V1表示整个工程开始事件V9表示整个工程结束 整个工程只有一个开始

27、点和一个完成点，在正常情况下，网中只一个入度为零的点（称为源点）和一个出度为零的点（称为汇点）。 问题：（1）完成整项工程至少需要多少时间？ （2）哪些活动是影响工程进度的关键？,AOE网的典型应用,AOE网(Activity On Edge)是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。 路径长度路径上各活动持续时间之和。 关键路径路径长度最长的路径叫关键路径。 Ve(j)表示事件Vj的最早发生时间 Vl(k)表示事件Vk的最迟发生时间 e(i)表示活动ai的最早开始时间 l(i) 表示活动ai的最迟开始时间 l(i)-e(i)表示完成活动ai的时间余量。 关键活

28、动关键路径上的活动叫关键活动，即l(i)=e(i)的活动。,二、关键路径有关术语(1),1.路径长度 AOE网中一条路径的长度是该路径上每个活动所需时间的总和。(不是路径上边的数目) 2.关键路径 AOE网中,从开始顶点到结束顶点之间路径长度中的最大路径为关键路径。由于AOE网中某些子工程（活动）可以同时进行，要保证每个子工程都能完成，完成该工程的最少时间就是该工程AOE网的关键路径长度。 3.事件的最早发生时间ve(j) 事件vj的最早发生时间ve(j)是从开始顶点v1到vj的最长路径长度。,二、关键路径有关术语(2),4.活动的最早开始时间e (i) 活动ai的最早开始时间e (i)是该活

29、动的起点所表示的事件最早发生时间,如果由边(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所需时间,7.时间余量 l(i)-e(i) 活动ai的 l(i)-e(i)是

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

31、li的关键活动,设活动ai用弧表示，其持续时间记为：dut() 则有： （1）e(i)=Ve(j) （2）l(i)=Vl(k)-dut() 、计算事件的最早发生时间ve（j） 从Ve(1)=0开始向后递推,此式的意义为：从指向顶点Vj的各边的活动中取最晚完成的一个活动的完成时间作为Vj的最早出现时间。,此公式的意义为：由从Vk顶点指出的各边所代表的活动中取需最早开始的一个开始时间作为Vk的最迟出现时间。,2、计算事件的最迟发生时间vl（k） 从Vl(n)=Ve(n)开始向前递推,9,8,7,6,4,5,3,2,1,a2=4,a3=5,a5=1,a6=2,a9=4,a1=6,a4=1,a7=9,

32、a8=7,a10=2,a11=4,V1 V2 V3 V4 V5 V6 V7 V8 V9,0 6 4 5 7 7 16 14 18,0 6 6 8 7 10 16 14 18,a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11, ,求关键路径步骤 求Ve(j) 求Vl(k) 求e(i) 求l(i) 计算l(i)-e(i),四、结论： 关键路径上的活动都是关键活动； 缩短非关键活动都不能缩短整个工期； 分析关键路径的目的是找出影响整个工期的关键活动，缩短关键活动的持续时间，可以缩短整个工期； 在有多条关键路径时，缩短那些在所有关键路径上的关键活动，才能缩短整个工期。,以邻接表作存

33、储结构 从源点V1出发，令Ve1=0，按拓扑序列求各顶点的Vej。 从汇点Vn出发，令Vln=Ven，按逆拓扑序列求其余各顶点的Vlk. 根据各顶点的Ve和Vl值，计算每条弧的ei和li，找出eili的关键活动。,算法描述：,输入顶点和弧信息，建立其邻接表； 计算每个顶点的入度； 对其进行拓扑排序； 排序过程中求顶点的Vej； 将得到的拓扑序列进栈（为了得到一个逆拓序列）； 按逆拓扑序列求顶点的Vlk； 计算每条弧的ei和li，找出eili的关键活动。,算法实现：,P208P209,作业,1）画出下图的邻接矩阵和邻接表表示，并写出下图的深度优先搜索遍历序列和广度优先搜索遍历序列。 2)根据普里姆算法思想，画出构造该无向带权图最小生成树的过程。 3）根据克鲁斯卡尔算法思想，画出构造该无向带权图最小生成树的过程。,4）对下图所示的有向带权图，根据迪杰斯特拉算法，画出生成从结点v1到其余各结点最短路径的过程。,