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

1、第7章 图7.1 图的定义和术语7.2 图的存储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及其应用7.6 最短路径7.4 图的连通性问题1）无向图的连通分量和生成树2）最小生成树2.1）普里姆算法2.2）克鲁斯卡尔算法例：图及其生成树65665513420 对于带权的连通图(连通网)G，其生成树也是带权的，将权最小的生成树称为最小生成树。 连通网最小生成树的意义？ 如何构造最小生成树？ 对于带权的连通图(连通网)G，其生成树也是带权的，将权最小的生成树称为最小生成树。 连通网最小生成树的意义？ 如何构造最小生成树？最小生成树的MST性质： 假设 N =（V,E）是一个连通网，

2、U是顶点集 V 的一个非空子集。若（u,v）是一条具有最小权值（代价）的边，其中 u U，vV-U，则必存在一棵包含边（u,v）的最小生成树。656655134207.4 图的连通性问题1）无向图的连通分量和生成树2）最小生成树3）普里姆算法4）克鲁斯卡尔算法3.普里姆（Prim）算法基本思想：(1)假设 G=(V,E) 是一个具有 n 个顶点的连通网络，T=(U，TE)是 G 的最小生成树，其中 U 是 T 的顶点集，TE 是 T 的边集，U 和 TE 的初值均为空；(2)从 V 中任取一个顶点（假定为 V1），将此顶点并入 U中，此时最小生成树顶点集 U=V1；(3)从那些其中一个端点已在

3、 U 中，另一端点仍在 U 外的所有边中，找一条最短（即权值最小）的边，设该边为(Vi,Vj)，其中 ViU，VjV-U，并把该边和顶点 Vj分别并入 T 的边集 TE 和顶点集 U；(4)如此进行下去，每次往生成树里并入一个顶点和一条边，直到 n-1 次后，把所有 n 个顶点都并入生成树 T 的顶点集 U 中，此时 U=V，TE中包含有（n-1）条边；这样，T 就是最后得到的最小生成树。 实现该算法需附设一个辅助数组closedge，以记录从 U 到 V-U 具有最小代价的边。对每个顶点 viV-U，在辅助数组中存在一个相应分量closedgei-1(下标从0开始)，它包括两个域。其中：lo

4、wcost存储该边上的权。显然， closedgei-1.lowcost =Mincost(u，vi)|uU 即vi到已生成子树的最短距离等于到U中所有顶点中的最小边的权值。 vex域存储该边依附的在U中的顶点。例：求下图最小生成树。假设开始顶点就选为顶点1， 故有U=1，V-U=2，3，4，5，6 (a )无向网64V1V2V4V36213V55V6556(b) U=1 V-U=2,3,4,5,612345665153124561456(c) U=1,3 V-U=2,4,5,631 2456 4215 6 (d) U=1,3,6 V-U=2,4,531245642156(e) U=1,3,6

5、,4 V-U=2,5(f) U=1,3,6,4,2 V-U=512435642153(g) U=1,3,6,4,2,5 V-U= 54213124356 (a )无向网64V1V2V4V36213V55V6556基于邻接矩阵的普里姆算法 struct VertaxType adjvex; /顶点编号 VRType lowcost; / =Mincost(u,vi|uU) closedgeMAX_VERTEX_NUM;Void MiniSpanTree_PRIM(MGraph G, VertexType u) k = LocateVex ( G, u ); / 顶点u为构造生成树的起始点,返回顶

6、点u在图中的位置 for ( j=0; jG.vexnum; +j ) / 辅助数组初始化 if (j!=k) closedgej= u, G.arcskj.adj ; closedgek.lowcost = 0; / 初始，Uu边k，j的权值 for (i=1; iG.vexnum; +i) /在其余顶点中选择 k = minimum(closedge); / 求出T的下一结点(k) printf(closedgek.adjvex, G.vexsk); /输出生成树的边 closedgek.lowcost = 0; / 第k顶点并入U集 for (j=0; jG.vexnum; +j) if

7、 (G.arcskj.adj closedgej.lowcost) / 新顶点并入U后重新选择最小边 closedgej=G.vexsk,G.arcskj.adj; / for / MiniSpanTree_PRIMT(n)=O(n2)20140424 Class34.克鲁斯卡尔（Kruskal）算法基本思想 为使生成树上总的权值最小，应使每条边上的权值尽可能小，自然应从权值最小的边选起，直至选出n-1条权值最小的边为止，同时这n-1条边必须不构成回路。因此，并非每一条当前权值最小的边都可选。4 克鲁斯卡尔 (Kruskal) 算法克鲁斯卡尔算法的基本思想： 设有一个有 n 个顶点的连通网络

8、N = V, E ,最初先构造一个只有 n 个顶点，没有边的非连通图 T = V, , 图中每个顶点自成一个连通分量。当在 E 中选到一条具有最小权值的边时,若该边的两个顶点落在不同的连通分量上，则将此边加入到 T 中；否则将此边舍去，重新选择一条权值最小的边。 如此重复下去，直到所有顶点在同一个连通分量上为止。v1v6v5v4v2v34623561556克鲁斯卡尔（Kruskal）构造最小生成树算法： 设 N=(V，E)是一个连通网，V是顶点集，T=（V， ），把E中权值最小的边加入T中，再选权值最小的边，而且它的顶点落在T中不同的连通分量上则加入T，否则不加入T，直到V都在T连通分量为止。

9、v1v6v5v4v2v342315v1v6v5v4v2v34231v1v6v5v4v2v3231v1v6v4v321v1v31克鲁斯卡尔算法构造最小生成树的过程22连通分量1连通分量2连通分量3连通分量1连通分量1连通分量2连通分量2连通分量1201511264.克鲁斯卡尔（Kruskal）算法具体做法 先构造一个只含 n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中去，并使森林中不产生回路，直至森林变成一棵树为止。例：对下图中无向网，用克鲁斯卡尔算法求最小生成树的过程。 22156134 无向网6462135556465312345/*/* kruskal求解最小生成树算法 *

10、/* 文件名kruskal.c 函数名kruskal() */*/void kruskal(edge adjlist,edge tree,int cnvx,int n) int v=0,j,k; for (j=0;jn;j+) cnvxj=j; /* 设置每一个顶点的连通分量 */ for (k=0;kn-1;k+) /*树中共有n-1条边*/ while (cnvxadjlistv.beg=cnvxadjlistv.en ) v+; /*找到属于两个连通分量权最小的边*/treek=adjlistv; /*将边v加入到生成树中*/ for (j=0;jn;j+) /*两个连通分量合并为一个连

11、通分量*/ if (cnvxj=cnvxadjlistv.en) cnvxj=cnvxadjlistv.beg; v+; printf(最小生成树是：n); for (j=0;jn-1;j+) printf(%3d%3d%6dn,treej.beg,treej.en,treej.length);算法8.6 Kruskal求解最小生成树void kruskal(edge adjlist,edge tree,int cnvx,int n) int v=0,j,k; for (j=0;jn;j+) cnvxj=j; /* 设置每一个顶点的连通分量 */ for (k=0;kn-1;k+) /*树中共

12、有n-1条边*/ while (cnvxadjlistv.beg=cnvxadjlistv.en ) v+; /*找到属于两个连通分量权最小的边*/ treek=adjlistv; /*将边v加入到生成树中*/ for (j=0;jn;j+) /*两个连通分量合并为一个连通分量*/ if (cnvxj=cnvxadjlistv.en) cnvxj=cnvxadjlistv.beg; v+; printf(最小生成树是：n); for (j=0;jn-1;j+) printf(%3d%3d%6dn,treej.beg,treej.en,treej.length);一般来讲,. 在不使用优先队列优

13、化的条件下，普里姆算法的时间复杂度为 O(V2)，使用后的时间复杂度为O(elogV)，适于稠密图； 克鲁斯卡尔算法需对 e 条边按权值进行排序，其时间复杂度为 O(elogV)，适于稀疏图。P.S.如果使用斐波那契堆，PRIM的效率会有进一步提升。第7章 图7.1 图的定义和术语7.2 图的存储结构7.3 图的遍历7.4 图的连通性问题7.5 有向无环图及其应用7.6 最短路径7.5 有向无环图及其应用 有向无环图(directed acycline graph)简称DAG图，是描述一项工程或系统的进行过程的有效工具。有向无环图Directed acycline graph DAG及其应用有

14、向树DAG环一般有向图偏序：集合X中的元素只有部分成员可以比较关系（如先后关系）的。如：v1v2v4v3v2与v3谁先?全序：集合X中的全部成员都可以比较关系（如先后关系）的也称为拓扑有序。如：v1v2v4v3v1v2v4v3v1v2v4v3v1v2v4v32320151202 对整个工程和系统，人们关心的是两个方面的问题：一是工程能否顺利进行；二是估算整个工程完成所必须的最短时间。 有向无环图的应用：拓扑排序关键路径 在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系： 先后关系，即必须在一子项目完成后，才能开始实施另一个子项目； 子项目之间无次序要求，即两个子项目

15、可以同时进行，互不影响。20141114 我们用一种有向图来表示上述问题。在这种有向图中，顶点表示活动，有向边表示活动的优先关系，这种有向图叫做顶点表示活动的网络(Activity On Vertex Network)简称为AOV网。7.5.1 拓扑排序课程编号课程名称先导课程编号C1程序设计基础无C2离散数学C1C3数据结构C1，C2C4汇编语言C1C5算法分析与设计C3，C4C6计算机组成原理C11C7编译原理C5，C3C8操作系统C3，C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C9，C10，C1课程先后关系如图：c1c9c4c2c12c10c11c5c3c6c7

16、c8c1c9c4c2c12c10c5c3c6c7c8c2 在AOV网络中，如果顶点Vi的活动必须在顶点Vj的活动以前进行，则称Vi为Vj的前趋顶点，而称Vj为Vi的后继顶点。这种前趋后继关系有传递性。此外，任何活动i不能以它自己作为自己的前驱或后继，这叫做反自反性。 从前驱和后继的传递性和反自反性来看，AOV网中不能出现回路(有向环)，回路表示顶点之间的先后关系进入了死循环。 判断AOV网是否有有向环的方法是对该AOV网进行拓扑排序，将AOV网中顶点排列成一个线性有序序列，若该线性序列中包含AOV网全部顶点，则AOV网无环，否则，AOV网中存在有向环，该AOV网所代表的工程是不可行的。AOV网

17、，即顶点活动网何谓“拓扑排序” ？拓扑序列： 在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列。拓扑排序 由AOV网构造拓扑序列的过程叫拓扑排序。AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称为它的拓扑序列。AOV网，即顶点活动网拓扑有序序列： （C1，C2，C3，C4，C5，C8，C9，C7，C6） （C2，C5，C1，C8，C3，C9，C4，C7，C6）如何进行拓扑排序？解决方法： 1）从有向图中选取一个没有前驱的顶点，并输出之； 2）从有向图中删去此顶点以及所有以它为尾的弧； 3）重复上述两步

18、，直至图空，或者图不空但找不到无前驱的顶点为止。后一种情况说明有向图中存在环。如何在计算机中实现 拓扑排序呢？拓扑排序算法的实现为了实现拓扑排序的算法，对给定的有向图可采用邻接表作为它的存储结构。将每个链表的表头结点构成一个顺序表，各表头结点的Data域存放相应顶点的入度值。每个顶点入度初值可随邻接表动态生成过程中累计得到。在拓扑排序过程中，凡入度为零的顶点即是没有前趋的顶点，可将其取出列入有序序列中，同时将该顶点从图中删除掉不再考虑。删去一个顶点时，所有它的直接后继顶点入度均减1，表示相应的有向边也被删除掉。设置一个堆栈，将已检验到的入度为零的顶点标号进栈，当再出现新的无前趋顶点时，也陆续将其进栈。每次选入度为零的顶点时，只要取栈顶顶点即可。4004 2100314 AOV网络的邻接表01234顶点的入度数组下标用邻接表存储AOV网络，拓扑排序算法描述：(1) 把邻接表中所有入度为零的顶点进栈；