数据结构第18讲_最小生成树与拓扑排序.ppt

《数据结构第18讲_最小生成树与拓扑排序.ppt》由会员分享，可在线阅读，更多相关《数据结构第18讲_最小生成树与拓扑排序.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第7 7章章 图图7.1 7.1 图的定义和术语图的定义和术语7.2 7.2 图的存储结构图的存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 图的连通性问题图的连通性问题7.5 7.5 有向无环图及其应用有向无环图及其应用7.6 7.6 最短路径最短路径7.4 7.4 图的连通性问题图的连通性问题1 1）无向图的无向图的连通分量和连通分量和生成树生成树2 2）最小生成树最小生成树3 3）普里姆算法）普里姆算法4 4）克鲁斯卡尔算法）克鲁斯卡尔算法例：例：图及其生成树图及其生成树65665513420 对于带权的连通图对于带权的连通图(连通网连通网)G G，其生成树也是其生成树也是带权

2、的，将权最小的生成树称为带权的，将权最小的生成树称为最小生成树最小生成树。连通网最小生成树的意义？连通网最小生成树的意义？如何构造最小生成树？如何构造最小生成树？对于带权的连通图对于带权的连通图(连通网连通网)G G，其生成树也是其生成树也是带权的，将权最小的生成树称为带权的，将权最小的生成树称为最小生成树最小生成树。连通网最小生成树的意义？连通网最小生成树的意义？如何构造最小生成树？如何构造最小生成树？最小生成树的最小生成树的MSTMST性质：性质：假设假设 N=N=（V,EV,E）是一个连通网，）是一个连通网，U U是顶点是顶点集集 V V 的一个非空子集。若（的一个非空子集。若（u,vu

3、,v）是一条具有最）是一条具有最小权值（代价）的边，其中小权值（代价）的边，其中 u Uu U，vVvV-U-U，则，则必存在一棵包含边（必存在一棵包含边（u,vu,v）的最小生成树。）的最小生成树。656655134207.4 7.4 图的连通性问题图的连通性问题1 1）无向图的无向图的连通分量和连通分量和生成树生成树2 2）最小生成树最小生成树3 3）普里姆算法）普里姆算法4 4）克鲁斯卡尔算法）克鲁斯卡尔算法3.3.普里姆（普里姆（PrimPrim）算法）算法基本思想：基本思想：(1)(1)假设假设 G=(V,E)G=(V,E)是一个具有是一个具有 n n 个顶点的连通个顶点的连通网络，

4、网络，T=(UT=(U，TE)TE)是是 G G 的最小生成树，其中的最小生成树，其中 U U 是是 T T 的顶点集，的顶点集，TE TE 是是 T T 的边集，的边集，U U 和和 TE TE 的初值均为空；的初值均为空；(2)(2)从从 V V 中任取一个顶点（假定为中任取一个顶点（假定为 V V1 1），将此顶），将此顶点并入点并入 U U中，此时最小生成树顶点集中，此时最小生成树顶点集 U=VU=V1 1；(3)(3)从那些其中一个端点已在从那些其中一个端点已在 U U 中，另一端点仍中，另一端点仍在在 U U 外的所有边中，找一条最短（即权值最外的所有边中，找一条最短（即权值最小）

5、的边，设该边为小）的边，设该边为(V Vi i,V,Vj j)，其中，其中 V Vi iUU，V Vj jVV-U-U，并把该边和顶点，并把该边和顶点 V Vj j分别并入分别并入 T T 的边的边集集 TE TE 和顶点集和顶点集 U U；(4)(4)如此进行下去，每次往生成树里并入一个顶点如此进行下去，每次往生成树里并入一个顶点和一条边，直到和一条边，直到 n-1 n-1 次后，把所有次后，把所有 n n 个顶点个顶点都并入生成树都并入生成树 T T 的顶点集的顶点集 U U 中，此时中，此时 U=VU=V，TETE中包含有（中包含有（n-1n-1）条边；这样，）条边；这样，T T 就是最

6、后就是最后得到的最小生成树。得到的最小生成树。实现该算法需附设一个辅助数组实现该算法需附设一个辅助数组closedgeclosedge，以记录从以记录从 U U 到到 V-U V-U 具有最小代价的边。对每个具有最小代价的边。对每个顶点顶点 v vi iVV-U-U，在辅助数组中存在一个相应分量，在辅助数组中存在一个相应分量closedgei-1(closedgei-1(下标从下标从0 0开始开始)，它包括两个域。，它包括两个域。其中：其中：lowcostlowcost存储该边上的权。显然，存储该边上的权。显然，closedgei-1.lowcostclosedgei-1.lowcost =M

7、incost(uMincost(u，v vi i)|uU)|uU 即即v vi i到已生成子树的最短距离等于到到已生成子树的最短距离等于到U U中所有中所有顶点中的最小边的权值。顶点中的最小边的权值。vexvex域域存储该边依附的在存储该边依附的在U U中的顶点。中的顶点。例例：求下图：求下图最小生成树。最小生成树。假设开始顶点就选为顶点假设开始顶点就选为顶点1 1，故有故有U=1U=1，V-U=2V-U=2，3 3，4 4，5 5，66 (a)无向网无向网64V1V1V2V2V4V4V3V36213V5V55V6V6556(b)U=1 V-U=2,3,4,5,6(b)U=1 V-U=2,3,

8、4,5,61 12 23 34 45 56 66 65 51 15 53 31 12 24 45 56 61 14 45 56 6(c)U=1,3 V-U=2,4,5,6(c)U=1,3 V-U=2,4,5,63 31 1 2 24 45 56 6 4 42 21 15 5 6 6(d)U=1,3,6 V-(d)U=1,3,6 V-U=2,4,5U=2,4,53 31 12 24 45 56 64 42 21 15 56 6(e)U=1,3,6,4 V-U=2,5(e)U=1,3,6,4 V-U=2,5(f)U=1,3,6,4,2 V-U=5(f)U=1,3,6,4,2 V-U=51 12 2

9、4 43 35 56 64 42 21 15 53 3(g)U=1,3,6,4,2,5 V-U=54213124356(a)无向网无向网64V1V1V2V2V4V4V3V36213V5V55V6V6556基于邻接矩阵的普里姆算法基于邻接矩阵的普里姆算法 structstruct VertaxTypeVertaxType adjvexadjvex;/;/顶点编号顶点编号 VRTypeVRType lowcostlowcost;/=;/=Mincost(u,vMincost(u,vi i|u|uU U)closedgeMAX_VERTEX_NUMclosedgeMAX_VERTEX_NUM;Voi

10、d Void MiniSpanTree_PRIM(MGraphMiniSpanTree_PRIM(MGraph G,G,VertexTypeVertexType u)u)k=k=LocateVexLocateVex(G,u);(G,u);/顶点顶点u u为构造生成树的起始点为构造生成树的起始点,返回顶点返回顶点u u在图中的位置在图中的位置 for(j=0;jfor(j=0;jG.vexnumG.vexnum;+j);+j)/辅助数组初始化辅助数组初始化 if(j!=k)if(j!=k)closedgejclosedgej=u,=u,G.arcskj.adjG.arcskj.adj;close

11、dgek.lowcostclosedgek.lowcost=0;=0;/初始，初始，U Uuu边边k，j的权值的权值 for(i=1;ifor(i=1;iG.vexnumG.vexnum;+i);+i)/在其余顶点中选择在其余顶点中选择 k=k=minimum(closedgeminimum(closedge););/求出求出T T的下一结点的下一结点(k)(k)printf(closedgek.adjvexprintf(closedgek.adjvex,G.vexskG.vexsk););/输出生成树的边输出生成树的边 closedgek.lowcostclosedgek.lowcost=0

12、;=0;/第第k k顶点并入顶点并入U U集集 for(j=0;jfor(j=0;jG.vexnumG.vexnum;+j);+j)if(if(G.arcskj.adjG.arcskj.adj closedgej.lowcostclosedgej.lowcost)/新顶点并入新顶点并入U U后重新选择最小边后重新选择最小边 closedgejclosedgej=G.vexsk,G.arcskj.adjG.vexsk,G.arcskj.adj;/for/for /MiniSpanTree_PRIMMiniSpanTree_PRIMT(n)=O(nT(n)=O(n2 2)4.4.克鲁斯卡尔（克鲁斯

13、卡尔（KruskalKruskal）算法）算法基本思想基本思想 为使生成树上总的权值最小，应使每条边上为使生成树上总的权值最小，应使每条边上的权值尽可能小，自然应从权值最小的边选起，的权值尽可能小，自然应从权值最小的边选起，直至选出直至选出n-1n-1条权值最小的边为止，同时这条权值最小的边为止，同时这n-1n-1条条边必须不构成回路。因此，并非每一条当前权值边必须不构成回路。因此，并非每一条当前权值最小的边都可选。最小的边都可选。4.4.克鲁斯卡尔（克鲁斯卡尔（KruskalKruskal）算法）算法具体做法具体做法 先构造一个只含先构造一个只含 n n个顶点的森林，然后依权个顶点的森林，然

14、后依权值从小到大从连通网中选择边加入到森林中去，值从小到大从连通网中选择边加入到森林中去，并使森林中不产生回路，直至森林变成一棵树为并使森林中不产生回路，直至森林变成一棵树为止。止。例例：对下图中无向网，用克鲁斯卡尔算法求最小：对下图中无向网，用克鲁斯卡尔算法求最小生成树的过程。生成树的过程。2 22 21 15 56 61 13 34 4 无向网无向网64621355564 46 65 53 31 12 2345一般来讲：一般来讲：普里姆算法的时间复杂度为普里姆算法的时间复杂度为 O(nO(n2 2)，适于稠，适于稠密图；密图；克鲁斯卡尔算法需对克鲁斯卡尔算法需对 e e 条边按权值进行排条

15、边按权值进行排序，其时间复杂度为序，其时间复杂度为 O(elogeO(eloge)，适于稀疏图。，适于稀疏图。第第7 7章章 图图7.1 7.1 图的定义和术语图的定义和术语7.2 7.2 图的存储结构图的存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 图的连通性问题图的连通性问题7.5 7.5 有向无环图及其应用有向无环图及其应用7.6 7.6 最短路径最短路径7.5 7.5 有向无环图及其应用有向无环图及其应用 有向无环图有向无环图(directed(directed acyclineacycline graph)graph)简简称称DAGDAG图，是描述一项工程或系统的进行过程的

16、图，是描述一项工程或系统的进行过程的有效工具。有效工具。对整个工程和系统，人们关心的是两个方面对整个工程和系统，人们关心的是两个方面的问题：一是工程能否顺利进行；二是估算整个的问题：一是工程能否顺利进行；二是估算整个工程完成所必须的最短时间。工程完成所必须的最短时间。有向无环图的应用：有向无环图的应用：n拓扑排序拓扑排序n关键路径关键路径 在工程实践中，一个工程项目往往由若干个在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系：子项目组成，这些子项目间往往有多种关系：先后关系，即必须在一子项目完成后，才先后关系，即必须在一子项目完成后，才能开始实施另一个子项目；能开始

17、实施另一个子项目；子项目之间无次序要求，即两个子项目可子项目之间无次序要求，即两个子项目可以同时进行，互不影响。以同时进行，互不影响。我们用一种有向图来表示上述问题。在我们用一种有向图来表示上述问题。在这种有向图中，顶点表示活动，有向边表示这种有向图中，顶点表示活动，有向边表示活动的优先关系，这种有向图叫做顶点表示活动的优先关系，这种有向图叫做顶点表示活动的网络活动的网络(Activity On Vertex Network)(Activity On Vertex Network)简称为简称为AOVAOV网网。7.5.1 7.5.1 拓扑排序拓扑排序课程编号课程编号课程名称课程名称先导课程编号

18、先导课程编号C1C1程序设计基础程序设计基础无无C2C2离散数学离散数学C1C1C3C3数据结构数据结构C1C1，C2C2C4C4汇编语言汇编语言C1C1C5C5算法分析与设计算法分析与设计C3C3，C4C4C6C6计算机组成原理计算机组成原理C11C11C7C7编译原理编译原理C5C5，C3C3C8C8操作系统操作系统C3C3，C6C6C9C9高等数学高等数学无无C C 1010线性代数线性代数C9C9C11C11普通物理普通物理C9C9C12C12数值分析数值分析C9C9，C10C10，C1C1课程课程先后关系先后关系如图：如图：c1c9c4c2c12c10c11c5c3c6c7c8c1c

19、9c4c2c12c10c5c3c6c7c8c2n 在在AOVAOV网络中，如果顶点网络中，如果顶点V Vi i的活动必须在顶点的活动必须在顶点V Vj j的活动以的活动以前进行，则称前进行，则称V Vi i为为V Vj j的前趋顶点，而称的前趋顶点，而称V Vj j为为V Vi i的后继顶点。的后继顶点。这种前趋后继关系有这种前趋后继关系有传递性传递性。此外，任何活动。此外，任何活动i i不能以它自不能以它自己作为自己的前驱或后继，这叫做己作为自己的前驱或后继，这叫做反自反性反自反性。n 从前驱和后继的传递性和反自反性来看，从前驱和后继的传递性和反自反性来看，AOVAOV网中不能网中不能出现回

20、路出现回路(有向环有向环)，回路表示顶点之间的先后关系进入了，回路表示顶点之间的先后关系进入了死循环。死循环。n 判断判断AOVAOV网是否有有向环的方法是对该网是否有有向环的方法是对该AOVAOV网进行拓扑排网进行拓扑排序，将序，将AOVAOV网中顶点排列成一个线性有序序列，若该线性序网中顶点排列成一个线性有序序列，若该线性序列中包含列中包含AOVAOV网全部顶点，则网全部顶点，则AOVAOV网无环，否则，网无环，否则，AOVAOV网中存网中存在有向环，该在有向环，该AOVAOV网所代表的工程是不可行的。网所代表的工程是不可行的。何谓何谓“拓扑排序拓扑排序”？n拓扑序列：拓扑序列：在在AOV

21、AOV网中，若不存在回路，则所有活动可排列网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓动都排在该活动的前面，我们把此序列叫做拓扑序列。扑序列。n拓扑排序拓扑排序 由由AOVAOV网构造拓扑序列的过程叫拓扑排序。网构造拓扑序列的过程叫拓扑排序。AOVAOV网的拓扑序列不是唯一的网的拓扑序列不是唯一的，满足上述定义的任，满足上述定义的任一线性序列都称为它的拓扑序列。一线性序列都称为它的拓扑序列。拓扑有序序列：拓扑有序序列：（C1C1，C2C2，C3C3，C4C4，C5C5，C8C8，C9

22、C9，C7C7，C6C6）（C2C2，C5C5，C1C1，C8C8，C3C3，C9C9，C4C4，C7C7，C6C6）如何进行拓扑排序？如何进行拓扑排序？解决方法：解决方法：1 1）从有向图中选取一个没有前驱的顶点，并）从有向图中选取一个没有前驱的顶点，并输出之；输出之；2 2）从有向图中删去此顶点以及所有以它为尾）从有向图中删去此顶点以及所有以它为尾的弧；的弧；3 3）重复上述两步，直至图空，或者图不空但）重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。后一种情况说明有向找不到无前驱的顶点为止。后一种情况说明有向图中存在环。图中存在环。如何在计算机中实现如何在计算机中实现 拓扑排

23、序呢？拓扑排序呢？拓扑排序算法的实现拓扑排序算法的实现n为了实现拓扑排序的算法，对给定的有向图可采用邻为了实现拓扑排序的算法，对给定的有向图可采用邻接表作为它的存储结构。接表作为它的存储结构。n将每个链表的表头结点构成一个顺序表，各表头结点将每个链表的表头结点构成一个顺序表，各表头结点的的DataData域存放相应顶点的入度值。每个顶点入度初值域存放相应顶点的入度值。每个顶点入度初值可随邻接表动态生成过程中累计得到。可随邻接表动态生成过程中累计得到。n在拓扑排序过程中，凡入度为零的顶点即是没有前趋在拓扑排序过程中，凡入度为零的顶点即是没有前趋的顶点，可将其取出列入有序序列中，同时将该顶点的顶点

24、，可将其取出列入有序序列中，同时将该顶点从图中删除掉不再考虑。从图中删除掉不再考虑。n删去一个顶点时，所有它的直接后继顶点入度均减删去一个顶点时，所有它的直接后继顶点入度均减1 1，表示相应的有向边也被删除掉。，表示相应的有向边也被删除掉。n设置一个堆栈，将已检验到的入度为零的顶点标号进设置一个堆栈，将已检验到的入度为零的顶点标号进栈，当再出现新的无前趋顶点时，也陆续将其进栈。栈，当再出现新的无前趋顶点时，也陆续将其进栈。每次选入度为零的顶点时，只要取栈顶顶点即可。每次选入度为零的顶点时，只要取栈顶顶点即可。4004 2100314 AOVAOV网络的邻接表网络的邻接表01234顶点的入度顶点

25、的入度数组下标数组下标用邻接表存储用邻接表存储AOVAOV网络，拓扑排序算法描述：网络，拓扑排序算法描述：(1)(1)把邻接表中所有入度为零的顶点进栈；把邻接表中所有入度为零的顶点进栈；(2)(2)在栈不空时：在栈不空时：退栈并输出栈顶的顶点退栈并输出栈顶的顶点 j j；在邻接表的第在邻接表的第 j j 个单链表中，查找顶点个单链表中，查找顶点为为 j j 的所有直接后继顶点的所有直接后继顶点 k k，并将并将 k k 的入度减的入度减1 1。若顶点若顶点 k k 的入度为零，则顶点的入度为零，则顶点 k k 进栈；进栈；若栈空时输出的顶点个数不是若栈空时输出的顶点个数不是 n n，则有向，则

26、有向图中有环路，否则拓扑排序完毕。图中有环路，否则拓扑排序完毕。拓扑排序算法拓扑排序算法Status Topological Status Topological Sort(ALGraphSort(ALGraph G)G)/有向图有向图G G采用邻接表存储结构。若采用邻接表存储结构。若G G无回路，无回路，/则输出则输出G G的顶点的的顶点的1 1个拓扑序列并返回个拓扑序列并返回OKOK，否则，否则ERRORERROR FindInDegree(GFindInDegree(G，indegreeindegree)；/对各顶点求入度对各顶点求入度indegree0.vernum-1indegree

27、0.vernum-1 InitStack(SInitStack(S)；for(ifor(i=0=0；ii;p;p=p-nextarcnextarc)k=p-k=p-adjvexadjvex；/对对i i号顶点的每个邻接点入度减号顶点的每个邻接点入度减1 1if(if(！(-(-indegreek)Push(Sindegreek)Push(S，k);k);/若入度减为若入度减为0 0，则入栈，则入栈 /for/for/while/whileif(countif(count G.vexnumG.vexnum)return ERROR;)return ERROR;/该有向图有回路该有向图有回路els

28、e return OKelse return OK；/TopologicalSortTopologicalSort 分析：分析：对有对有 n n 个顶点和个顶点和 e e 条弧的有向图而言，建条弧的有向图而言，建立求各顶点的入度的时间复杂度为立求各顶点的入度的时间复杂度为O(eO(e)；建零入；建零入度顶点栈的时间复杂度为度顶点栈的时间复杂度为O(nO(n)；在拓扑排序过程；在拓扑排序过程中，若有向图无环，则每个顶点进一次栈，出一中，若有向图无环，则每个顶点进一次栈，出一次栈，入度减次栈，入度减1 1的操作在的操作在 WHILEWHILE语句中总共执行语句中总共执行e e次，所以，总的时间复杂度为次，所以，总的时间复杂度为O(n+eO(n+e)。拓扑排序的算法是下一讲讨论的求关键路径的拓扑排序的算法是下一讲讨论的求关键路径的基础。基础。