牛小飞《数据结构》9.5最小生成树

最小生成树,生成树和生成森林,最小生成树,小结和作业,生成树,一、定义图G的生成树是G的极小连通子图，即包含G中的所有顶点（n）和n-1条边的连通子图,生成树,V1,V2,V4,V8,V5,V3,V6,V7,V1,V2,V3,V4,V5,V8,V6,V7,深度优先：,广度优先：,生成树,二、算法图的遍历算法访问了图中的每个顶点一次且仅一次。访问某个顶点的邻接点时，要经过与这两个顶点相关联的边。,因此，图的遍历算法可以产生一颗生成树：所有的顶点和经过的边。,生成树算法,voidDFSTree(AdjGraphG,intv,CSNodeT)G.vertexsv.visited=true;first=true;for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if(!G.vertexsw.visited)p=newCSNode(G.vertexsw.data);if(first)T.lchild=p;first=false;elseq.nextsibling=p;q=p;DFSTree(G,w.q);,算法以孩子兄弟链表作为生成森林的存储结构,生成森林,定义非连通图G的每个连通分量的生成树，构成了图G的生成森林,生成森林,8,1,2,3,4,5,6,7,0,a,b,c,h,d,e,k,f,g,非连通图G：,G的深度优先搜索生成森林：,a,c,h,d,f,e,k,b,g,生成森林算法,算法以孩子兄弟链表作为生成森林的存储结构,CSTreeDFSForest(AdjGraphG)CSTreeT=NULL;for(intv=0;v=G.vexnum;+v)G.vertexsv.visited=FALSE;for(v=0;v=G.vexnum;+v)if(!G.vertexsv.visited)p=newCSNode(G.vertexsw.data);if(!T)T=p;elseq.nextsibling=p;q=p;DFSTree(G,v,p);returnT;,最小生成树,假设要在n个城市之间建立通讯联络网，则连通n个城市只需要修建n-1条线路，如何在最节省经费的前提下建立这个通讯网？,问题：,最小生成树,连通网：n个城市和城市间可能的通信线路,网的顶点：表示城市,网的边：表示两个城市之间的线路,网的边上的权值：通信代价,最小生成树,最小生成树,构造网的一棵最小生成树，即：在e条带权的边中选取n-1条边（不构成回路），使“权值之和”为最小。,该问题等价于：,特点：1.最小生成树中边的条数为|V|-1。2.最小生成树无圈。3.最小生成树是包含所有顶点的的最小的树。,最小生成树,算法三：克鲁斯卡尔算法Kruskal,算法二：普里姆算法Prim,算法一：破圈法,破圈法,一、基本思想1、将所有的边按权重从大到小排列。2、对每条边e尝试下面的操作，直到G中的边数=n-1:如果删除e,图G仍然是连通图，则从G中删除e否则，保留e。,破圈法,v4,v5,v1,v3,v2,v6,v7,1,破圈法,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,12,7,课堂练习：,Prim算法,算法思想：使最小生成树连续的一步步成长。在每一步，都要把一个节点当作根并往上加边，这样相关联的顶点就加到增长中的树上。,Prim算法,在生成树的构造过程中，图中n个顶点分属两个集合：已落在生成树上的顶点集U和尚未落在生成树上的顶点集V-U，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。,Prim算法,v4,v5,v1,v3,v2,v6,v7,v4,v5,v1,v3,v2,v6,v7,Prim算法,v4,v5,v1,v3,v2,v6,v7,T,v1,2,4,1,T,v4,v1,v1,v1,2,v4,7,v4,8,v4,4,v4,T,v2,T,v3,T,v7,6,v7,T,v6,T,v5,5,v3,1,v7,算法的核心：选择向集合U中加入顶点时，要选择到U具有最短边的顶点。,1、对任何一个顶点v，如果它有多个邻接U的边，则需要找出最短的边作为邻接到U的边,2、从所有的VU顶点中，找出具有最短边的顶点，将它加入U,Prim算法,a,b,e,g,f,14,d,8,c,3,5,16,21,Prim算法,Kruskal算法,具体做法:先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如此重复，直至加上n-1条边为止。,考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。,a,b,c,d,e,g,f,3,a,b,c,e,g,f,d,21,5,8,14,16,Kruskal算法,Kruskal算法,v4,v5,v1,v3,v2,v6,v7,v4,v5,v1,v3,v2,v6,v7,算法描述:,构造非连通图ST=(V,);k=i=0;/k选中的边数while(kn-1)+i;检查边集E中第i条权值最小的边(u,v);if若(u,v)加入ST后不使ST中产生回路，则输出边(u,v);且k+;,Kruskal算法,两种算法的比较,普里姆算法,克鲁斯卡尔算法,时间复杂度,O(n2