牛小飞《数据结构》9.5最小生成树.ppt
最小生成树,生成树和生成森林,最小生成树,小结和作业,生成树,一、定义图G的生成树是G的极小连通子图，即包含G中的所有顶点（n）和n-1条边的连通子图,生成树,V1,V2,V4,V8,V5,V3,V6,V7,V1,V2,V3,V4,V5,V8,V6,V7,深度优先：,广度优先：,生成树,二、算法图的遍历算法访问了图中的每个顶点一次且仅一次。访问某个顶点的邻接点时，要经过与这两个顶点相关联的边。,因此，图的遍历算法可以产生一颗生成树：所有的顶点和经过的边。,生成树算法,void DFSTree(AdjGraph G,int v,CSNode T)G.vertexsv.visited=true;first=true;for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if(!G.vertexsw.visited)p=new CSNode(G.vertexsw.data);if(first)T.lchild=p;first=false;else q.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,生成森林算法,算法以孩子兄弟链表作为生成森林的存储结构,CSTree DFSForest(AdjGraph G)CSTree T=NULL;for(int v=0;v=G.vexnum;+v)G.vertexsv.visited=FALSE;for(v=0;v=G.vexnum;+v)if(!G.vertexsv.visited)p=new CSNode(G.vertexsw.data);if(!T)T=p;else q.nextsibling=p;q=p;DFSTree(G,v,p);return T;,最小生成树,假设要在 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、从所有的V U顶点中，找出具有最短边的顶点，将它加入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),O(eloge),稠密图,稀疏图,算法名称,适应范围,课堂练习,求出图中最小生成树,小结和作业,1.普里姆算法,2.克鲁斯卡尔算法,3.两种算法的比较,2.最小生成树算法,1.图的生成树和生成森林,作业：P275,9.15,
