图最小生成树ppt课件.ppt

《图最小生成树ppt课件.ppt》由会员分享，可在线阅读，更多相关《图最小生成树ppt课件.ppt（57页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、1第九讲第九讲1 1、图的基本概念复、图的基本概念复习习2 2 、 最小生成树最小生成树2317823456(a)17823456(b)17823456(c)4按照生成树的定义，按照生成树的定义，n 个顶点的连通网络的生成树有个顶点的连通网络的生成树有 n 个顶个顶点、点、n- -1 条边。条边。而所有包含而所有包含n-1 n-1 条边及条边及n n个顶点的连通图都个顶点的连通图都是无回路的树，所以生成树是连通图中的极小连通子图是无回路的树，所以生成树是连通图中的极小连通子图. . 由于使用不同的遍历图的方法，可以得到不同的生成树；从由于使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶

2、点出发，也可能得到不同的生成树。如深度优先生成不同的顶点出发，也可能得到不同的生成树。如深度优先生成树、广度优先生成树树、广度优先生成树 在图论中，常常将树定义为一个无回路连通图。在图论中，常常将树定义为一个无回路连通图。 对于一个带权的无向连通图，其每个生成树所有边上的权对于一个带权的无向连通图，其每个生成树所有边上的权值之和可能不同，我们把所有边上权值之和最小的生成树称为值之和可能不同，我们把所有边上权值之和最小的生成树称为图的最小生成树。求图的最小生成树有很多实际应用。例如，图的最小生成树。求图的最小生成树有很多实际应用。例如，通讯线路铺设造价最优问题就是一个最小生成树问题。通讯线路铺设

3、造价最优问题就是一个最小生成树问题。5 假设把假设把n n个城市看作图的个城市看作图的n n个顶点，边表示两个城市之间的线个顶点，边表示两个城市之间的线路，每条边上的权值表示铺设该线路所需造价。铺设线路连接路，每条边上的权值表示铺设该线路所需造价。铺设线路连接n n个城市，但不形成回路，这实际上就是图的生成树，而以最少个城市，但不形成回路，这实际上就是图的生成树，而以最少的线路铺设造价连接各个城市，即求线路铺设造价最优问题，的线路铺设造价连接各个城市，即求线路铺设造价最优问题，实际上就是在图的生成树中选择权值之和最小的生成树。构造实际上就是在图的生成树中选择权值之和最小的生成树。构造最小生成树

4、的算法有很多，下面分别介绍克鲁斯卡尔最小生成树的算法有很多，下面分别介绍克鲁斯卡尔( (KruskalKruskal) )算法和普里姆算法和普里姆( (Prim)Prim)算法。算法。 克鲁斯卡尔算法是一种按权值递增的次序选择合适的边来构造最克鲁斯卡尔算法是一种按权值递增的次序选择合适的边来构造最小生成树的方法。小生成树的方法。6假设假设G=G=（V V，E E）是一个具有是一个具有n n个顶点个顶点的带权无向连通图，的带权无向连通图，T= (UT= (U，TE)TE)是是G G的最小生成树，其中的最小生成树，其中U U是是T T的顶点集，的顶点集，TETE是是T T的边集，则构造最小生成树的

5、的边集，则构造最小生成树的过程如下：过程如下：(1) (1) 置置U U的初值等于的初值等于V V，TETE的初值为空的初值为空集；集；7(2) (2) 按权值从小到大的顺序依次选取按权值从小到大的顺序依次选取图图G G中的边，若选取的边未使生成树中的边，若选取的边未使生成树T T形成回路，则加入形成回路，则加入TETE；若选取的边使若选取的边使生成树生成树T T形成回路，则将其舍弃。循环形成回路，则将其舍弃。循环执行执行(2)(2)，直到，直到TETE中包含中包含( (n-1)n-1)条边为条边为止。止。 8910 普里姆算法的基本思想：普里姆算法的基本思想：普里姆算法普里姆算法是另一种构造

6、最小生成树的算法，它是另一种构造最小生成树的算法，它是按逐个将顶点连通的方式来构造最是按逐个将顶点连通的方式来构造最小生成树的。小生成树的。11从连通网络从连通网络 N N = = V V, , E E 中的某一顶点中的某一顶点 u u0 0 出出发，选择与它关联的具有最小权值的边发，选择与它关联的具有最小权值的边( (u u0, 0, v v) )，将其顶点加入到生成树的顶点集合将其顶点加入到生成树的顶点集合U U中。中。以后每一步从一个顶点在以后每一步从一个顶点在U U中，而另一个顶点不中，而另一个顶点不在在U U中的各条边中选择权值最小的边中的各条边中选择权值最小的边( (u u, ,

7、v v),),把该把该边加入到生成树的边集边加入到生成树的边集TETE中，把它的顶点加入到中，把它的顶点加入到集合集合U U中。如此重复执行，直到网络中的所有顶中。如此重复执行，直到网络中的所有顶点都加入到生成树顶点集合点都加入到生成树顶点集合U U中为止。中为止。12假设假设G=(VG=(V，E)E)是一个具有是一个具有n n个顶点的带权无向连个顶点的带权无向连通图，通图，T(UT(U，TE)TE)是是G G的最小生成树，其中的最小生成树，其中U U是是T T的顶的顶点集，点集，TETE是是T T的边集，则构造的边集，则构造G G的最小生成树的最小生成树T T的步的步骤如下：骤如下：（1 1

8、）初始状态，）初始状态，TETE为空，为空，U=v0U=v0，v0Vv0V；（2）在所有在所有uU，vV-U的边的边(u，v) E中找一条中找一条代价最小的边代价最小的边(u，v)并入并入TE，同时将同时将v并入并入U；重复执行步骤（重复执行步骤（2 2）n-1n-1次，直到次，直到U=VU=V为止。为止。13在普里姆算法中，为了便于在集合在普里姆算法中，为了便于在集合U U和和( (V-U)V-U)之之间选取权值最小的边，需要设置两个辅助数组间选取权值最小的边，需要设置两个辅助数组closestclosest和和lowcostlowcost，分别用于存放顶点的序号分别用于存放顶点的序号和边的

9、权值。和边的权值。 对于每一个顶点对于每一个顶点vV-UvV-U，closestvclosestv 为为U U中中距 离距 离 v v 最 近 的 一 个 邻 接 点 ， 即 边最 近 的 一 个 邻 接 点 ， 即 边 ( ( v v ，closestvclosestv) ) 是在所有与顶点是在所有与顶点v v相邻、且其另一相邻、且其另一顶点顶点jUjU的边中具有最小权值的边，其最小权的边中具有最小权值的边，其最小权值为值为lowcostvlowcostv ，即即lowcostvlowcostv=costvclosestvcostvclosestv， 14为实现克鲁斯卡尔算法需要设置一维辅助

10、数组E，按权值从小到大的顺序存放图的边，数组的下标取值从0到e-1（e为图G边的数目）。 假设数组E存放图G中的所有边，且边已按权值从小到大的顺序排列。n为图G的顶点个数，e为图G的边数。 注：克鲁斯卡尔算法的时间复杂度与边数注：克鲁斯卡尔算法的时间复杂度与边数e e有关有关O(elogeO(eloge) ) ，该算法适合于求边数较少，该算法适合于求边数较少的带权无向连通图的最小生成树。的带权无向连通图的最小生成树。151617普里姆算法的时间复杂度为普里姆算法的时间复杂度为O(nO(n2 2),),与网中与网中的边数无关，因此适合于求边稠密的网的最小的边数无关，因此适合于求边稠密的网的最小生

11、成树。生成树。18192021 通常我们把计划、施工过程、生产流程、程序流程等都当成通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，这一个工程，一个大的工程常常被划分成许多较小的子工程，这些子工程称为活动。这些活动完成时，整个工程也就完成了。些子工程称为活动。这些活动完成时，整个工程也就完成了。 例如，计算机专业学生的课程开设可看成是一个工程，每一例如，计算机专业学生的课程开设可看成是一个工程，每一门课程就是工程中的活动，图门课程就是工程中的活动，图7-217-21给出了若干门所开设的课程，给出了若干门所开设的课程，其中有些课程的开设有先

12、后关系，有些则没有先后关系，有先其中有些课程的开设有先后关系，有些则没有先后关系，有先后关系的课程必须按先后关系开设，如开设数据结构课程之前后关系的课程必须按先后关系开设，如开设数据结构课程之前必须先学完程序设计基础及离散数学，而开设离散数学则必须必须先学完程序设计基础及离散数学，而开设离散数学则必须先并行学完高等数学、程序设计基础课程。先并行学完高等数学、程序设计基础课程。22课程代号 课程名称 先修课程 Cl 高等数学 无 C2 程序语言 无 C3 离散数学 C1 C4 数据结构 C2，C3 C5 编译原理 C2，C4 C6 操作系统 C4，C7 C7 计算机组成原理 C2图图7-22 7

13、-22 课程安排的课程安排的AOVAOV网网C1C7C2C5C4C3C6在图在图7-227-22中，我们用一中，我们用一种有向图来表示课程开种有向图来表示课程开设，在这种有向图中，设，在这种有向图中，顶点表示活动，有向边顶点表示活动，有向边表示活动的优先关系，表示活动的优先关系，这有向图叫做顶点表示这有向图叫做顶点表示活动的网络活动的网络(Activity(Activity On Vertices)On Vertices)简称为简称为。23拓扑排序：拓扑排序： 假设假设G=(VG=(V，E)E)是一个具有是一个具有n n个顶点的有向图，个顶点的有向图，V V中顶点序列中顶点序列v vl l，v

14、 v2 2，v vn n称做一个拓扑序列称做一个拓扑序列(Topological Order)(Topological Order)，当且仅当当且仅当该顶点序列满足下列条件：若在有向图该顶点序列满足下列条件：若在有向图G G中存在从顶点中存在从顶点v vi i到到v vj j的的一条路径，则在顶点序列中顶点一条路径，则在顶点序列中顶点v vi i必须排在顶点必须排在顶点v vj j之前。通常，之前。通常，在在AOVAOV网中，网中，将所有活动排列成一个拓扑序列的过程叫做将所有活动排列成一个拓扑序列的过程叫做拓扑排拓扑排序序(Topological Sort)(Topological Sort)

15、。24 由于由于AOVAOV网中有些活动之间没有次序要求，它们在拓扑序列的网中有些活动之间没有次序要求，它们在拓扑序列的位置可以是任意的，因此拓扑排序的结果不唯一。位置可以是任意的，因此拓扑排序的结果不唯一。C1C7C2C5C4C3C6对右图进行拓扑排序，可得一个拓扑序列：C1，C3，C2，C4，C7，C6，C5也可得到另一个拓扑序列： C2，C7，C1，C3，C4，C5，C6还可以得到其它的拓扑序列。学生按照任何一个拓扑序列都可以完成所要求的全部课程学习。在AOV网中不应该出现有向环。因为环的存在意味着某项活动将以自己为先决条件，显然无法形成拓扑序列。 判定网中是否存在环的方法：对有向图构造

16、其顶点的拓扑有序序列，若网中所有顶点都出现在它的拓扑有序序列中，则该AOV网中一定不存在环。 25进行拓扑排序的算法：(1)在AOV网络中选一个没有直接前驱的顶点, 并输出之;(2)从图中删去该顶点, 同时删去所有它发出的有向边;重复以上 (1)、(2) 步, 直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。26272829在实现拓扑排序的算法中，采用邻接表邻接表作为有向图的存储结构，每个顶点设置一个单链表，每个单链表有一个表头结点，在表头结点

17、中增加一个存放顶点入度的域count，这些表头结点构成一个数组，表头结点定义如下：typedef struct /表头结点表头结点 Vertex data; /顶点信息顶点信息 int count; /存放顶点入度存放顶点入度 ArcNode *firstarc; /指向第一条弧指向第一条弧Vnode;在执行拓扑排序的过程中，当某个顶点的入度为零在执行拓扑排序的过程中，当某个顶点的入度为零( (没有前驱没有前驱顶点顶点) )时，就将此顶点输出，同时将该顶点的所有后继顶点的入度时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减减1 1，相当于删除所有以该顶点为尾的弧。为了避免重复检测顶点，相

18、当于删除所有以该顶点为尾的弧。为了避免重复检测顶点的入度是否为零，需要设立一个栈来存放入度为零的顶点。的入度是否为零，需要设立一个栈来存放入度为零的顶点。执行执行拓扑排序的算法如下：拓扑排序的算法如下：30Status TopologicalSort(ALGraph G) / 算法7.12 / 有向图G采用邻接表存储结构。 / 若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则ERROR。FindInDegree(G, indegree); / 对各顶点求入度indegree0.vernum-1 InitStack(S); for (i=0; inextarc) k = p-adjvex

19、; / 对i号顶点的每个邻接点的入度减1 if (!(-indegreek) Push(S, k); / 若入度减为0，则入栈 if (countG.vexnum) return ERROR; / 该有向图有回路 else return OK; / TopologicalSort31 【例例7-37-3】请给出图请给出图7-247-24所示的有向图所示的有向图G G的拓扑排序过程。的拓扑排序过程。图图7-24有向图有向图G及其邻接矩阵及其邻接矩阵 132405160122(b)432624顶点 入度 指针(a)16543232 图图7-25 拓扑排序过程的栈拓扑排序过程的栈 top=11top

20、=12top=13top=11top=216top=14top=0top=2153334在AOE网络中, 有些活动顺序进行，有些活动并行进行。 从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。35图图7-26 AOE网网 95274a1=6a10=2a6=2a3=5a4=1a5=11a2=4386a11=

21、4a9=4a7=9a8=73695274a1=6a10=2a6=2a3=5a4=1a5=11a2=4386a11=4a9=4a7=9a8=737是从源点是从源点V0 到顶点到顶点Vi 的最长路径长度。的最长路径长度。是在保证汇点是在保证汇点Vn-1 在在Ven-1 时刻完成的前提下，事件时刻完成的前提下，事件Vi 的允许的允许的最迟开始时间。的最迟开始时间。设活动设活动ak 在边在边上，则上，则ek是从源点是从源点V0到顶点到顶点Vi 的最长的最长路径长度。因此路径长度。因此, ek = Vei。lk是在不会引起时间延误的前提下，该活动允许的最迟开始是在不会引起时间延误的前提下，该活动允许的最

22、迟开始时间。时间。38lk = Vlj - dur()。 其中，其中，dur()是完成是完成ak 所需的时间。所需的时间。39 , ) ,( ijjVVdurjVemaxiVe, ) ,( jijVVdurjVlminiVl40设活动设活动ak (k = 1, 2, , e)在带权有向边在带权有向边 上上, 它的持续时间它的持续时间用用dur () 表示，则有表示，则有 ek = Vei； lk = Vlj - - dur()；k = 1, 2, , e。这样就得到计算这样就得到计算关键路径的算法。关键路径的算法。计算关键路径时，可以一边进行拓扑排序一边计算各顶点的计算关键路径时，可以一边进行

23、拓扑排序一边计算各顶点的Vei。为了简化算法，假定在求关键路径之前已经对各顶点实现了拓为了简化算法，假定在求关键路径之前已经对各顶点实现了拓扑排序，并按拓扑有序的顺序对各顶点重新进行了编号。算法扑排序，并按拓扑有序的顺序对各顶点重新进行了编号。算法在求在求Vei, i=0, 1, , n-1时按拓扑有序的顺序计算，在求时按拓扑有序的顺序计算，在求Vli, i=n-1, n-2, , 0时按逆拓扑有序的顺序计算。时按逆拓扑有序的顺序计算。41【例7-4】图7-29是一个具有8个活动和6个事件的AOE网，试求其关键路径。 【解】由ve (i)和vl (i)的递推公式，依次求出所有事件的最早发生时间

24、ve (i)和最迟发生时间vl (i)，如下：图图7-29 AOEAOE网网 64253a1=3a8=1a6=3a2=2a3=2a4=3a5=41a7=2源点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)=6。42显然Ve(5)=6,而V1到V6有4条路径，最长路径为V1-V3-V4-V6路径长度为：8，因此Ve(6)=8.64253a1=3a8=1a6=3a2=2a3=2a4=3a5

25、=41a7=243求Vl(i),应该逆序求得，即有Vl(6)=8开始，应用下面的公式：注意：汇点V6的最早发生时间和最迟发生时间相同。由于V5与V6只有一条弧相连，因此Vl(5)=Vl(6)-dur=8-1=7。64253a1=3a8=1a6=3a2=2a3=2a4=3a5=41a7=2同理Vl(4)=6, Vl(3)=2,Vl(2)=4,Vl(1)=0。4464253a1=3a8=1a6=3a2=2a3=2a4=3a5=41a7=245 求出所有活动的最早开始时间求出所有活动的最早开始时间e(i)e(i)、最迟开始时间最迟开始时间l(i)l(i)以及以及d d (i)=l(i)-e(i)(i

26、)=l(i)-e(i)，如下：如下：ek = Vei；即活动所在弧的起点的最早发生时间就是活动；即活动所在弧的起点的最早发生时间就是活动ak的最的最早发生时间，因此早发生时间，因此64253a1=3a8=1a6=3a2=2a3=2a4=3a5=41a7=246由于lk = Vlj - dur()；k = 1, 2, , e。64253a1=3a8=1a6=3a2=2a3=2a4=3a5=41a7=247显然关键活动为：a2,a5,a748 从以上计算得出，图从以上计算得出，图7-297-29中中AOEAOE网的关键活动为网的关键活动为a a2 2，a a5 5，a a7 7，这些活动构成了关键

27、路径，如图这些活动构成了关键路径，如图7-307-30所示：所示： 图图7-30 7-30 AOEAOE网的关键路径网的关键路径643a2=2a5=41a7=249注意注意：1.影响关键活动的因素是多方面的，任何一项活动持续时间的改变都会影响关键路径的改变，2.关键活动的速度提高是有限度的，只有在不改变网的关键路径的情况下，提高关键活动的速度才有效，3.关键路径不是唯一的，4.若网中存在几条关键路径，那么单单提高一条关键路径上的关键活动的速度，还不能导致整个工期的缩短，只有提高同时在几条关键路径上的活动的速度。50Status TopologicalOrder(ALGraph G, Stack

28、 &T) / 算法7.13 / 有向网G采用邻接表存储结构，求各顶点事件的最早发生时间ve(全局变量)。 / T为拓扑序列定点栈，S为零入度顶点栈。 / 若G无回路，则用栈T返回G的一个拓扑序列，且函数值为OK，否则为ERROR。FindInDegree(G, indegree); / 对各顶点求入度indegree0.vernum-1 for (int j=0; jG.vexnum; +j) / 建零入度顶点栈S if (indegreej=0) Push(S, j); / 入度为0者进栈 InitStack(T);/建拓扑序列顶点栈T count = 0; for(int i=0; ine

29、xtarc) k = p-adjvex; / 对j号顶点的每个邻接点的入度减1 if (-indegreek = 0) Push(S, k); / 若入度减为0，则入栈 if (vej+p-info vek) vek = vej+p-info; /for *(p-info)=dut() /while51if (countG.vexnum) return ERROR; / 该有向网有回路 else return OK; / TopologicalOrder52Status CriticalPath(ALGraph G) / 算法7.14 / G为有向网，输出G的各项关键活动。if (!Topol

30、ogicalOrder(G, T) return ERROR; for(a=0; anextarc) k=p-adjvex; dut=p-info; /dut if (vlk-dut vlj) vlj = vlk-dut; for (j=0; jnextarc) k=p-adjvex;dut=p-info; ee = vej; el = vlk-dut; tag = (ee=el) ? * : ; printf(j, k, dut, ee, el, tag); / 输出关键活动 return OK; / CriticalPath5319下面哪一方法可以判断出一个有向图是否有环（回路）A深度优先

31、遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径25已知有向图G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=,G的拓扑序列是（ ）。AV1,V3,V4,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 ABA5427一个有向无环图的拓扑排序序列（ ）是唯一的。A一定 B不一定28. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的

32、是（ ）。 AG中有弧 BG中有一条从Vi到Vj的路径 CG中没有弧 DG中有一条从Vj到Vi的路径 29. 在用邻接表表示图时，拓扑排序算法时间复杂度为( )。A. O(n) B. O(ne) C. O(n*n) D. O(n*n*n) BDB5530. 关键路径是事件结点网络中（ ）。A从源点到汇点的最长路径 B从源点到汇点的最短路径C最长回路 D最短回路31. 下面关于求关键路径的说法不正确的是（ ）。 A求关键路径是以拓扑排序为基础的 B一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 D

33、关键活动一定位于关键路径上32下列关于AOE网的叙述中，不正确的是（ ）。A关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动提前完成，那么整个工程将会提前完成C所有的关键活动提前完成，那么整个工程将会提前完成D某些关键活动提前完成，那么整个工程将会提前完成ACB5633. 有向图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）环