《图最小生成树ppt课件.ppt》由会员分享，可在线阅读，更多相关《图最小生成树ppt课件.ppt（57页珍藏版）》请在三一办公上搜索。
1、1,第九讲,1、图的基本概念复习2 、 最小生成树,2,3,最小生成树,1. 生成树 在一个无向连通图G中，其所有顶点和遍历该图经过的所有边所构成的子图G 称做图G的生成树。一个图可以有多个生成树，从不同的顶点出发，采用不同的遍历顺序，遍历时所经过的边也就不同，例如图7-12的(b) 和(c) 为图7-12 (a) 的两棵生成树。其中 (b) 是通过DFS得到的，称为深度优先生成树；(c) 是通过BFS得到的，称为广度优先生成树。,图7-12 生成树,4,按照生成树的定义，n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。而所有包含n-1 条边及n个顶点的连通图都是无回路的树，所以生成
2、树是连通图中的极小连通子图. 由于使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。如深度优先生成树、广度优先生成树 在图论中，常常将树定义为一个无回路连通图。 对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生成树。求图的最小生成树有很多实际应用。例如，通讯线路铺设造价最优问题就是一个最小生成树问题。,5,假设把n个城市看作图的n个顶点，边表示两个城市之间的线路，每条边上的权值表示铺设该线路所需造价。铺设线路连接n个城市，但不形成回路，这实际上就是图的生成树，而以最少的线路铺设造价连接各个城
3、市，即求线路铺设造价最优问题，实际上就是在图的生成树中选择权值之和最小的生成树。构造最小生成树的算法有很多，下面分别介绍克鲁斯卡尔(Kruskal)算法和普里姆(Prim)算法。,克鲁斯卡尔(Kruskal)算法 克鲁斯卡尔算法是一种按权值递增的次序选择合适的边来构造最小生成树的方法。,6,假设G=（V，E）是一个具有n个顶点的带权无向连通图，T= (U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则构造最小生成树的过程如下：,(1) 置U的初值等于V，TE的初值为空集；,7,(2) 按权值从小到大的顺序依次选取图G中的边，若选取的边未使生成树T形成回路，则加入TE；若选取的边
4、使生成树T形成回路，则将其舍弃。循环执行(2)，直到TE中包含(n-1)条边为止。,8,应用克鲁斯卡尔算法构造最小生成树的过程:,9,10,普里姆(Prim)算法,普里姆算法的基本思想：普里姆算法是另一种构造最小生成树的算法，它是按逐个将顶点连通的方式来构造最小生成树的。,11,从连通网络 N = V, E 中的某一顶点 u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。,以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把该边加入到生成树的边集TE中，把它的顶点加入到集合U中。如此重复执行，直到网络中的所有顶点
5、都加入到生成树顶点集合U中为止。,12,假设G=(V，E)是一个具有n个顶点的带权无向连通图，T(U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则构造G的最小生成树T的步骤如下：,（1）初始状态，TE为空，U=v0，v0V；,（2）在所有uU，vV-U的边(u，v) E中找一条代价最小的边(u，v)并入TE，同时将v并入U；,重复执行步骤（2）n-1次，直到U=V为止。,13,在普里姆算法中，为了便于在集合U和(V-U)之间选取权值最小的边，需要设置两个辅助数组closest和lowcost，分别用于存放顶点的序号和边的权值。 对于每一个顶点vV-U，closestv为U中距
6、离v最近的一个邻接点，即边 (v，closestv) 是在所有与顶点v相邻、且其另一顶点jU的边中具有最小权值的边，其最小权值为lowcostv，即lowcostv=costvclosestv，,14,为实现克鲁斯卡尔算法需要设置一维辅助数组E，按权值从小到大的顺序存放图的边，数组的下标取值从0到e-1（e为图G边的数目）。 假设数组E存放图G中的所有边，且边已按权值从小到大的顺序排列。n为图G的顶点个数，e为图G的边数。,注：克鲁斯卡尔算法的时间复杂度与边数e有关O(eloge) ，该算法适合于求边数较少的带权无向连通图的最小生成树。,15,应用普里姆算法构造最小生成树的过程:,16,17,
7、采用邻接表作为存储结构：设置一个辅助数组closedge： lowcost域：存放在V-U中各个顶点到集合U中的当前最小权值； adjvex域： 记录该边所依附的在U中的顶点,注：普里姆算法的时间复杂度为O(n2),与网中的边数无关，因此适合于求边稠密的网的最小生成树。,18,19,20,21,1.拓扑排序 通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，这些子工程称为活动。这些活动完成时，整个工程也就完成了。 例如，计算机专业学生的课程开设可看成是一个工程，每一门课程就是工程中的活动，图7-21给出了若干门所开设的课程，其中有些课程的开
8、设有先后关系，有些则没有先后关系，有先后关系的课程必须按先后关系开设，如开设数据结构课程之前必须先学完程序设计基础及离散数学，而开设离散数学则必须先并行学完高等数学、程序设计基础课程。,拓扑排序,22,图7-21 课程名称及相应的课程安排次序,图7-22 课程安排的AOV网,在图7-22中，我们用一种有向图来表示课程开设，在这种有向图中，顶点表示活动，有向边表示活动的优先关系，这有向图叫做顶点表示活动的网络(Activity On Vertices)简称为AOV网。,23,AOV网Activity On Vertex Network用顶点表示活动，用弧表示活动间 的优先关系的有向图，称为顶点表
9、 示活动的网。AOV 网中不能有回路拓扑排序： 假设G=(V，E)是一个具有n个顶点的有向图，V中顶点序列vl，v2，vn称做一个拓扑序列(Topological Order)，当且仅当该顶点序列满足下列条件：若在有向图G中存在从顶点vi到vj的一条路径，则在顶点序列中顶点vi必须排在顶点vj之前。通常，在AOV网中，将所有活动排列成一个拓扑序列的过程叫做拓扑排序(Topological Sort)。,24,由于AOV网中有些活动之间没有次序要求，它们在拓扑序列的位置可以是任意的，因此拓扑排序的结果不唯一。,对右图进行拓扑排序，可得一个拓扑序列：C1，C3，C2，C4，C7，C6，C5,也可得
10、到另一个拓扑序列： C2，C7，C1，C3，C4，C5，C6,还可以得到其它的拓扑序列。学生按照任何一个拓扑序列都可以完成所要求的全部课程学习。,在AOV网中不应该出现有向环。因为环的存在意味着某项活动将以自己为先决条件，显然无法形成拓扑序列。,判定网中是否存在环的方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都出现在它的拓扑有序序列中，则该AOV网中一定不存在环。,25,进行拓扑排序的算法：,(1)在AOV网络中选一个没有直接前驱的顶点, 并输出之;,(2)从图中删去该顶点, 同时删去所有它发出的有向边;,重复以上 (1)、(2) 步, 直到全部顶点均已输出，拓扑有序序列形成，拓扑排
11、序完成；或图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。,26,拓扑排序的过程,27,28,最后得到的拓扑有序序列为 C4 , C0 , C3 , C2 , C1 , C5 。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如C4和C2，也排出了先后次序关系。,29,在实现拓扑排序的算法中，采用邻接表作为有向图的存储结构，每个顶点设置一个单链表，每个单链表有一个表头结点，在表头结点中增加一个存放顶点入度的域count，这些表头结点构成一个数组，表头结点定义如下：typedef st
12、ruct /表头结点 Vertex data; /顶点信息 int count; /存放顶点入度 ArcNode *firstarc; /指向第一条弧Vnode;,在执行拓扑排序的过程中，当某个顶点的入度为零(没有前驱顶点)时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1，相当于删除所有以该顶点为尾的弧。为了避免重复检测顶点的入度是否为零，需要设立一个栈来存放入度为零的顶点。执行拓扑排序的算法如下：,30,Status TopologicalSort(ALGraph G) / 算法7.12 / 有向图G采用邻接表存储结构。 / 若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则E
13、RROR。FindInDegree(G, indegree); / 对各顶点求入度indegree0.vernum-1 InitStack(S); for (i=0; inextarc) k = p-adjvex; / 对i号顶点的每个邻接点的入度减1 if (!(-indegreek) Push(S, k); / 若入度减为0，则入栈 if (countG.vexnum) return ERROR; / 该有向图有回路 else return OK; / TopologicalSort,31,【例7-3】请给出图7-24所示的有向图G的拓扑排序过程。,图7-24有向图G及其邻接矩阵,32,【
14、解】依据拓扑排序算法，将图7-24中入度为0的两个顶点l和5相继入栈；顶点5出栈，输出，且以顶点5为尾的弧的另一顶点入度减一，如另一顶点2的入度值由2变为1，另一顶点6的入度值由1变为0。将入度为0的顶点6入栈；顶点6出栈，输出，且以顶点6为尾的弧的另一顶点入度减一，如另一顶点4的入度值由2变为1；依次类推得到拓扑序列：561234，拓扑排序过程栈的变化见图7-25。入度为0的顶点可以按不同顺序入栈，因此还可以得到其它拓扑序列：152364，152634，156234， 512364，516234，512634。,图7-25 拓扑排序过程的栈,33,关键路径,如果在有向无环的带权有向图中 用有
15、向边表示一个工程中的各项活动(Activity) 用边上的权值表示活动的持续时间(Duration) 用顶点表示事件(Event)则这样的有向图叫做用边表示活动的网络，简称AOE (Activity On Edges)网络。AOE网是一个带权的有向无环图。AOE网络在某些工程估算方面非常有用。例如，可以使人们了解： (1) 完成整个工程至少需要多少时间(假设网络中没有环)? (2) 为缩短完成工程所需的时间, 应当加快哪些活动?,34,在AOE网络中, 有些活动顺序进行，有些活动并行进行。 从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所
16、需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。,因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。,35,图7-26就是一个AOE网，该网中有11个活动和9个事件。每个事件表示在它之前的活动已经完成，在它之后的活动可以开始。如事件v5表示a4和a5活动已经完成，a7和a8活动可以开始。每个弧上的权值表示完成相应活动所需要的时间，如完成活动a1需要6天，a8需要7天。,图7-26 AOE网,36,AOE网常用于表示工程的计划或进度。由于实际工程只有一个开始
17、点和一个结束点，因此AOE网存在唯一的入度为0的开始点（又称源点）和唯一的出度为0的结束点（又称汇点），例如下图的AOE网从事件v1开始，以事件v9结束。同时AOE网应当是无环的。,37,定义几个与计算关键活动有关的量：,事件Vi 的最早可能开始时间Ve(i) 是从源点V0 到顶点Vi 的最长路径长度。 事件Vi 的最迟允许开始时间Vli 是在保证汇点Vn-1 在Ven-1 时刻完成的前提下，事件Vi 的允许的最迟开始时间。 活动ak 的最早可能开始时间 ek 设活动ak 在边上，则ek是从源点V0到顶点Vi 的最长路径长度。因此, ek = Vei。 活动ak 的最迟允许开始时间 lk lk
18、是在不会引起时间延误的前提下，该活动允许的最迟开始时间。,38,lk = Vlj - dur()。 其中，dur()是完成ak 所需的时间。 时间余量 lk - ek 表示活动ak 的最早可能开始时间和最迟允许开始时间的时间余量。lk = ek表示活动ak 是没有时间余量的关键活动。为找出关键活动, 需要求各个活动的 ek 与 lk，以判别是否 lk = ek.为求得ek与 lk，需要先求得从源点V0到各个顶点Vi 的 Vei 和 Vli。,39,从Ve0 = 0开始，向前递推 S2, i = 1, 2, , n-1 其中, S2是所有指向顶点Vi 的有向边的集合。 从Vln-1 = Ven-
19、1开始，反向递推 S1, i = n-2, n-3, , 0 其中, S1是所有从顶点Vi 发出的有向边的集合。这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下进行。,40,设活动ak (k = 1, 2, , e)在带权有向边 上, 它的持续时间用dur () 表示，则有 ek = Vei； lk = Vlj - dur()；k = 1, 2, , e。这样就得到计算关键路径的算法。计算关键路径时，可以一边进行拓扑排序一边计算各顶点的Vei。为了简化算法，假定在求关键路径之前已经对各顶点实现了拓扑排序，并按拓扑有序的顺序对各顶点重新进行了编号。算法在求Vei, i=0, 1, ,
20、n-1时按拓扑有序的顺序计算，在求Vli, i=n-1, n-2, , 0时按逆拓扑有序的顺序计算。,41,【例7-4】图7-29是一个具有8个活动和6个事件的AOE网，试求其关键路径。 【解】由ve (i)和vl (i)的递推公式，依次求出所有事件的最早发生时间ve (i)和最迟发生时间vl (i)，如下：,图7-29 AOE网,源点V1的最早发生时间为0，同理最迟发生时间也为0，,由于Ve(i)表示从源点V1到Vi的最长路径长度，因此Ve(2)=3,同理：Ve(3)=2,从V1到V4有两条路经：V1-V2-V4，和V1-V3-V4，其路径长度分别为2+3=5，2+4=6，因此,Ve(4)=
21、6。,42,显然Ve(5)=6,而V1到V6有4条路径，最长路径为V1-V3-V4-V6,路径长度为：8，因此Ve(6)=8.,43,求Vl(i),应该逆序求得，即有Vl(6)=8开始，应用下面的公式：,注意：汇点V6的最早发生时间和最迟发生时间相同。,由于V5与V6只有一条弧相连，因此Vl(5)=Vl(6)-dur=8-1=7。,同理Vl(4)=6, Vl(3)=2,Vl(2)=4,Vl(1)=0。,44,45,求出所有活动的最早开始时间e(i)、最迟开始时间l(i)以及d (i)=l(i)-e(i)，如下：,ek = Vei；即活动所在弧的起点的最早发生时间就是活动ak的最早发生时间，因此
22、,46,由于lk = Vlj - dur()；k = 1, 2, , e。,47,显然关键活动为：a2,a5,a7,48,从以上计算得出，图7-29中AOE网的关键活动为a2，a5，a7，这些活动构成了关键路径，如图7-30所示：,图7-30 AOE网的关键路径,49,注意：1.影响关键活动的因素是多方面的，任何一项活动持续时间的改变都会影响关键路径的改变，,2.关键活动的速度提高是有限度的，只有在不改变网的关键路径的情况下，提高关键活动的速度才有效，,3.关键路径不是唯一的，,4.若网中存在几条关键路径，那么单单提高一条关键路径上的关键活动的速度，还不能导致整个工期的缩短，只有提高同时在几条
23、关键路径上的活动的速度。,50,Status TopologicalOrder(ALGraph G, Stack /for *(p-info)=dut() /while,51,if (countG.vexnum) return ERROR; / 该有向网有回路 else return OK; / TopologicalOrder,52,Status CriticalPath(ALGraph G) / 算法7.14 / G为有向网，输出G的各项关键活动。if (!TopologicalOrder(G, T) return ERROR; for(a=0; anextarc) k=p-adjvex;
24、 dut=p-info; /dut if (vlk-dut nextarc) k=p-adjvex;dut=p-info; ee = vej; el = vlk-dut; tag = (ee=el) ? * : ; printf(j, k, dut, ee, el, tag); / 输出关键活动 return OK; / CriticalPath,53,19下面哪一方法可以判断出一个有向图是否有环（回路）A深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径25已知有向图G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=,G的拓扑序列是（ ）。AV1,V3,V4
25、,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V7 26若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列（ ）。 A存在 B不存在,A,AB,A,54,27一个有向无环图的拓扑排序序列（ ）是唯一的。A一定 B不一定28. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。 AG中有弧 BG中有一条从Vi到Vj的路径 CG中没有弧 DG中有一条从Vj到Vi的路径 29. 在用邻接表表示图时，拓扑排序算法时间复杂度为( )。A. O(n)
26、 B. O(ne) C. O(n*n) D. O(n*n*n),B,D,B,55,30. 关键路径是事件结点网络中（ ）。A从源点到汇点的最长路径 B从源点到汇点的最短路径C最长回路 D最短回路31. 下面关于求关键路径的说法不正确的是（ ）。 A求关键路径是以拓扑排序为基础的 B一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 D关键活动一定位于关键路径上32下列关于AOE网的叙述中，不正确的是（ ）。A关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动提前完成，那么整个工程将会提前
27、完成C所有的关键活动提前完成，那么整个工程将会提前完成D某些关键活动提前完成，那么整个工程将会提前完成,A,C,B,56,33. 有向图G可拓扑排序的判别条件是_。 39设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为_。40AOV网中,结点表示_,边表示_。AOE网中,结点表示_,边表示_。41在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为_。42在 AOV网 中，存在环意味着_，这是_的；对程序的数据流图来说，它表明存在_。 43. 当一个AOV网用邻接表表示时，可按下列方法进行拓扑排序。（1）查邻接表中入度为_的顶点，并进栈；（2）若栈不空，则输出栈顶元素Vj，并退栈；查Vj的直接后继Vk，对Vk入度处理，处理方法是_；（3）若栈空时，输出顶点数小于图的顶点数，说明有_，否则拓扑排序完成。,57,参考答案,33.不存在环 39.O(n+e）40.(1）活动 （2）活动间的优先关系 （3）事件 （4）活动 边上的权代表活动持续时间41.关键路径 42.（1）某项活动以自己为先决条件 （2）荒谬 （3）死循环 43.（1）零 （2）Vk入度减1，若Vk入度己减到零，则Vk顶点入栈 （3）环,
