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

数据结构第讲最小生成树与拓扑排序第一页，共三十六页，2022年，8月28日7.4图的连通性问题1）无向图的连通分量和生成树2）最小生成树3）普里姆算法4）克鲁斯卡尔算法第二页，共三十六页，2022年，8月28日例：图及其生成树⑤④①②③65665513420第三页，共三十六页，2022年，8月28日对于带权的连通图(连通网)G，其生成树也是带权的，将权最小的生成树称为最小生成树。

连通网最小生成树的意义？如何构造最小生成树？第四页，共三十六页，2022年，8月28日对于带权的连通图(连通网)G，其生成树也是带权的，将权最小的生成树称为最小生成树。

连通网最小生成树的意义？如何构造最小生成树？第五页，共三十六页，2022年，8月28日最小生成树的MST性质：假设N=（V,{E}）是一个连通网，U是顶点集V的一个非空子集。若（u,v）是一条具有最小权值（代价）的边，其中u∈U，v∈V-U，则必存在一棵包含边（u,v）的最小生成树。⑤④①②③65665513420第六页，共三十六页，2022年，8月28日7.4图的连通性问题1）无向图的连通分量和生成树2）最小生成树3）普里姆算法4）克鲁斯卡尔算法第七页，共三十六页，2022年，8月28日3.普里姆（Prim）算法基本思想：(1)假设G=(V,{E})是一个具有n个顶点的连通网络，T=(U，{TE})是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空；(2)从V中任取一个顶点（假定为V1），将此顶点并入U中，此时最小生成树顶点集U={V1}；第八页，共三十六页，2022年，8月28日(3)从那些其中一个端点已在U中，另一端点仍在U外的所有边中，找一条最短（即权值最小）的边，设该边为(Vi,Vj)，其中Vi∈U，Vj∈V-U，并把该边和顶点Vj分别并入T的边集TE和顶点集U；(4)如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后，把所有n个顶点都并入生成树T的顶点集U中，此时U=V，TE中包含有（n-1）条边；这样，T就是最后得到的最小生成树。第九页，共三十六页，2022年，8月28日第十页，共三十六页，2022年，8月28日例：求下图最小生成树。假设开始顶点就选为顶点1，故有U={1}，V-U={2，3，4，5，6}

(a)无向网64V1V2V4V36213V55V6556(b)U={1}V-U={2,3,4,5,6}12345665153124561456(c)U={1,3}V-U={2,4,5,6}31

2456

4215

6(d)U={1,3,6}V-U={2,4,5}第十一页，共三十六页，2022年，8月28日31245642156(e)U={1,3,6,4}V-U={2,5}(f)U={1,3,6,4,2}V-U={5}12435642153(g)U={1,3,6,4,2,5}V-U={}54213124356

(a)无向网64V1V2V4V36213V55V6556第十二页，共三十六页，2022年，8月28日基于邻接矩阵的普里姆算法struct{VertaxTypeadjvex;//顶点编号VRTypelowcost;//=Min{cost(u,vi|u∈U)}}closedge[MAX_VERTEX_NUM];VoidMiniSpanTree_PRIM(MGraphG,VertexTypeu){k=LocateVex(G,u);

//顶点u为构造生成树的起始点,返回顶点u在图中的位置for(j=0;j<G.vexnum;++j)//辅助数组初始化if(j!=k)closedge[j]={u,G.arcs[k][j].adj};

closedge[k].lowcost=0;

//初始，U＝{u}边k，j的权值第十三页，共三十六页，2022年，8月28日for(i=1;i<G.vexnum;++i){//在其余顶点中选择

k=minimum(closedge);//求出T的下一结点(k)printf(closedge[k].adjvex,G.vexs[k]);

//输出生成树的边closedge[k].lowcost=0;//第k顶点并入U集for(j=0;j<G.vexnum;++j)if(G.arcs[k][j].adj<closedge[j].lowcost)

//新顶点并入U后重新选择最小边closedge[j]={G.vexs[k],G.arcs[k][j].adj};}//for}//MiniSpanTree_PRIMT(n)=O(n2)第十四页，共三十六页，2022年，8月28日4.克鲁斯卡尔（Kruskal）算法基本思想为使生成树上总的权值最小，应使每条边上的权值尽可能小，自然应从权值最小的边选起，直至选出n-1条权值最小的边为止，同时这n-1条边必须不构成回路。因此，并非每一条当前权值最小的边都可选。第十五页，共三十六页，2022年，8月28日4.克鲁斯卡尔（Kruskal）算法具体做法先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中去，并使森林中不产生回路，直至森林变成一棵树为止。第十六页，共三十六页，2022年，8月28日例：对下图中无向网，用克鲁斯卡尔算法求最小生成树的过程。22156134

无向网6462135556465312345第十七页，共三十六页，2022年，8月28日一般来讲：普里姆算法的时间复杂度为O(n2)，适于稠密图；克鲁斯卡尔算法需对e条边按权值进行排序，其时间复杂度为O(eloge)，适于稀疏图。第十八页，共三十六页，2022年，8月28日第7章图7.1图的定义和术语7.2图的存储结构7.3图的遍历7.4图的连通性问题7.5有向无环图及其应用7.6最短路径第十九页，共三十六页，2022年，8月28日7.5有向无环图及其应用

有向无环图(directedacyclinegraph)简称DAG图，是描述一项工程或系统的进行过程的有效工具。第二十页，共三十六页，2022年，8月28日对整个工程和系统，人们关心的是两个方面的问题：一是工程能否顺利进行；二是估算整个工程完成所必须的最短时间。有向无环图的应用：拓扑排序关键路径第二十一页，共三十六页，2022年，8月28日在工程实践中，一个工程项目往往由若干个子项目组成，这些子项目间往往有多种关系：①先后关系，即必须在一子项目完成后，才能开始实施另一个子项目；②子项目之间无次序要求，即两个子项目可以同时进行，互不影响。第二十二页，共三十六页，2022年，8月28日我们用一种有向图来表示上述问题。在这种有向图中，顶点表示活动，有向边表示活动的优先关系，这种有向图叫做顶点表示活动的网络(ActivityOnVertexNetwork)简称为AOV网。7.5.1拓扑排序第二十三页，共三十六页，2022年，8月28日课程编号课程名称先导课程编号C1程序设计基础无C2离散数学C1C3数据结构C1，C2C4汇编语言C1C5算法分析与设计C3，C4C6计算机组成原理C11C7编译原理C5，C3C8操作系统C3，C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C9，C10，C1第二十四页，共三十六页，2022年，8月28日课程先后关系如图：c1c9c4c2c12c10c11c5c3c6c7c8c1c9c4c2c12c10c5c3c6c7c8c2第二十五页，共三十六页，2022年，8月28日在AOV网络中，如果顶点Vi的活动必须在顶点Vj的活动以前进行，则称Vi为Vj的前趋顶点，而称Vj为Vi的后继顶点。这种前趋后继关系有传递性。此外，任何活动i不能以它自己作为自己的前驱或后继，这叫做反自反性。从前驱和后继的传递性和反自反性来看，AOV网中不能出现回路(有向环)，回路表示顶点之间的先后关系进入了死循环。判断AOV网是否有有向环的方法是对该AOV网进行拓扑排序，将AOV网中顶点排列成一个线性有序序列，若该线性序列中包含AOV网全部顶点，则AOV网无环，否则，AOV网中存在有向环，该AOV网所代表的工程是不可行的。第二十六页，共三十六页，2022年，8月28日何谓“拓扑排序”？拓扑序列：在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列。拓扑排序由AOV网构造拓扑序列的过程叫拓扑排序。AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称为它的拓扑序列。第二十七页，共三十六页，2022年，8月28日拓扑有序序列：（C1，C2，C3，C4，C5，C8，C9，C7，C6）（C2，C5，C1，C8，C3，C9，C4，C7，C6）第二十八页，共三十六页，2022年，8月28日如何进行拓扑排序？解决方法：1）从有向图中选取一个没有前驱的顶点，并输出之；2）从有向图中删去此顶点以及所有以它为尾的弧；3）重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。后一种情况说明有向图中存在环。第二十九页，共三十六页，2022年，8月28日如何在计算机中实现拓扑排序呢？第三十页，共三十六页，2022年，8月28日拓扑排序算法的实现为了实现拓扑排序的算法，对给定的有向图可采用邻接表作为它的存储结构。将每个链表的表头结点构成一个顺序表，各表头结点的Data域存放相应顶点的入度值。每个顶点入度初值可随邻接表动态生成过程中累计得到。在拓扑排序过程中，凡入度为零的顶点即是没有前趋的顶点，可将其取出列入有序序列中，同时将该顶点从图中删除掉不再考虑。删去一个顶点时，所有它的直接后继顶点入度均减1，表示相应的有向边也被删除掉。设置一个堆栈，将已检验到的入度为零的顶点标号进栈，当再出现新的无前趋顶点时，也陆续将其进栈。每次选入度为零的顶点时，只要取栈顶顶点即可。第三十一页，共三十六页，2022年，8月28日4∧0∧04∧21003∧14∧AOV网络的邻接表01234顶点的入度数组下标第三十二页，共三十六页，2022年，8月28日用邻接表存储AOV网络，拓扑排序算法描述：(1)把邻接表中所有入度为零的顶点进栈；(2)在栈不空时：①退栈并输出栈顶的顶点j；②在邻接表的第j个单链表中，查找顶点为j的所有直接后继顶点k，并将k的入度减1。若顶点k的入度为零，则顶点k进栈；③若栈空时输出的顶点个数不是n，则有向图中有环路，否则拓扑排序完毕。第三十三页，共三十六页，2022年，8月28日拓扑排序算法StatusTopologicalSort(ALGraphG){//有向图G采用邻接表存储结构。若G无回路，//则输出G的顶点的1个拓扑序列并返回OK，否则ERROR

FindInDegree(G，indegree)；

//对各顶点求入度indegree[0..vernum-1]

InitStack(S)；for(i=0；i<G.vexnum；++i)//建零入度顶点栈if(!indegree[i])Push(S，i)//入度为0者进栈count=0；//对输出顶点计数第三十四页，共三十六页，2022年，8月28日

while(!StackEmpty(S)){