资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,最小生成树,生成树和生成森林,最小生成树,小结和作业,最小生成树生成树和生成森林最小生成树小结和作业,生成树,一、定义,图,G,的生成树是,G,的极小连通子图，即包含,G,中的所有顶点（,n,）和,n-1,条边的连通子图,生成树一、定义,生成树,V,1,V,2,V,3,V,4,V,5,V,8,V,6,V,7,V,1,V,2,V,4,V,8,V,5,V,3,V,6,V,7,V,1,V,2,V,3,V,4,V,5,V,8,V,6,V,7,深度优先：,广度优先：,生成树V1V2V3V4V5V8V6V7V1V2V4V8V5V,生成树,二、算法,图的遍历算法访问了图中的每个顶点一次且仅一次。,访问某个顶点的邻接点时，要经过与这两个顶点相关联的边。,因此，图的遍历算法可以产生一颗生成树：所有的顶点和经过的边。,生成树二、算法因此，图的遍历算法可以产生一颗生成树：所有的顶,生成树算法,void DFSTree(Graph G,int v,CSNode T)v.visit=true;first=true;for(w=FirstAdjVex(G,v);w=0;,w=NextAdjVex(G,v,w)if(!w.visit)p=new CSNode(v);,if(first)T.lchild=p;first=false;else q.nextsibling=p;q=p;DFSTree(G,w.q);,SG,1,SG,2,SG,3,V,w,1,w,3,w,2,算法,以孩子兄弟链表作为生成森林的存储结构,生成树算法void DFSTree(Graph G,int,生成森林,一、定义,非连通图,G,的每个连通分量的生成树，构成了图,G,的生成森林,生成森林一、定义,生成森林,a,b,c,h,d,e,k,f,g,8,1,2,3,4,5,6,7,0,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,生成森林abchdekfg81234567081234567,生成森林算法,算法,以孩子兄弟链表作为生成森林的存储结构,void DFSForest(Graph G,CSNode T)T=null;for(v=0;v=G.vexnum;+v)v.visit=false;for(v=0;v=G.vexnum;+v)if(!v.visit)p=new CSNode(v),if(!T)T=p;else q.nextsibling=p;q=p;DFSTree(G,v,p);,生成森林算法算法以孩子兄弟链表作为生成森林的存储结构void,最小生成树,假设要在,n,个城市之间建立通讯联络网，则连通,n,个城市只需要修建,n-1,条线路，,如何在最节省,经费,的前提下建立这个通讯网,？,问题：,最小生成树 假设要在 n 个城市之间建立通讯联络网，则,最小生成树,连通网：,n,个城市和城市间可能的通信线路,网的顶点：,表示城市,网的边：,表示两个城市之间的线路,网的边上的权值：,通信代价,2,4,5,2,7,10,6,1,4,v,4,v,5,v,1,v,3,v,2,v,6,v,7,1,3,8,最小生成树连通网：n个城市和城市间可能的通信线路网的顶点：表,最小生成树,2,2,6,1,4,v,4,v,5,v,1,v,3,v,2,v,6,v,7,1,2,4,5,2,7,10,6,1,4,v,4,v,5,v,1,v,3,v,2,v,6,v,7,1,3,8,最小生成树22614v4v5v1v3v2v6v7124527,最小生成树,构造网的一棵最小生成树，即：,在,e,条带权的边中选取,n-1,条边（不构成回路），使,“,权值之和,”,为最小,。,该问题等价于：,特点：,1.,最小生成树中边的条数为,|V|-1,。,2.,最小生成树无圈。,3.,最小生成树是包含所有顶点的的最小的树。,最小生成树 构造网的一棵最小生成树，即：在e条带权的边,最小生成树,算法三：克鲁斯卡尔算法,Kruskal,算法二：普里姆算法,Prim,算法一：破圈法,最小生成树算法三：克鲁斯卡尔算法Kruskal算法二：普里姆,破圈法,一、,基本思想,1,、将所有的边按权重从大到小排列。,2,、对每条边,e,尝试下面的操作，直到,G,中的边数,=n-1:,如果删除,e,图,G,仍然是连通图，则从,G,中删除,e,否则，保留,e,。,破圈法一、基本思想,破圈法,v,4,v,5,v,1,v,3,2,5,v,2,v,6,v,7,1,10,6,4,7,2,4,1,3,8,破圈法v4v5v1v325v2v6v711064724138,破圈法,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,12,7,课堂练习：,破圈法abcdegf195141827168213127课堂,Prim,算法,算法思想：,使最小生成树连续的一步步成长。在每一步，都要把一个节点当作根并往上加边，这样相关联的顶点就加到增长中的树上。,Prim算法算法思想：,Prim,算法,在生成树的构造过程中，图中,n,个顶点分属两个集合：,已落在生成树上的顶点集,U,和尚未落在生成树上的顶点集,V-U,，则应在所有连通,U,中顶点和,V-U,中顶点的边中选取权值最小的边。,U,V-U,Prim算法 在生成树的构造过程中，图中n个顶点分属两,Prim,算法,v,4,v,5,v,1,v,3,2,5,v,2,v,6,v,7,1,10,6,4,7,2,4,1,3,8,v,4,v,5,v,1,v,3,v,2,v,6,v,7,1,2,2,4,1,6,Prim算法v4v5v1v325v2v6v711064724,Prim,算法,v,4,v,5,v,1,v,3,2,5,v,2,v,6,v,7,1,10,6,4,7,2,4,1,3,8,v,4,v,5,v,1,v,3,v,2,v,6,v,7,1,2,2,4,1,6,v,known,d,v,p,v,v,1,v,2,v,3,v,4,v,5,v,6,v,7,F,F,F,F,F,F,F,0,0,0,0,0,0,0,0,T,v,1,2,4,1,T,v,4,v,1,v,1,v,1,2,v,4,7,v,4,8,v,4,4,v,4,T,v,2,T,v,3,T,v,7,6,v,7,T,v,6,T,v,5,5,v,3,1,v,7,Prim算法v4v5v1v325v2v6v711064724,算法的核心：,选择向集合,U,中加入顶点时，要选择到,U,具有最短边的顶点。,1,、对任何一个顶点,v,，如果它有多个邻接,U,的边，则需要找出最短的边作为邻接到,U,的边,2,、从所有的,V,U,顶点中，找出具有最短边的顶点，将它加入,U,Prim,算法,算法的核心：1、对任何一个顶点v，如果它有多个邻接U的边，则,a,b,c,d,e,g,f,19,5,14,18,27,16,8,21,3,12,7,a,b,e,g,f,14,d,8,c,3,5,16,21,Prim,算法,abcdegf195141827168213127abegf,Kruskal,算法,具体做法,:,先构造一个只含,n,个顶点的子图,SG,，然后从权值最小的边开始，若它的添加不使,SG,中产生回路，则在,SG,上加上这条边，如此重复，直至加上,n-1,条边为止。,考虑问题的出发点,:,为使生成树上,边的权值之和达到最小,，,则应使生成树中每一条边的权值尽可能地小。,Kruskal算法具体做法:先构造一个只含n个顶点的子图S,a,b,c,d,e,g,f,3,a,b,c,e,g,f,d,21,5,8,14,16,Kruskal,算法,abcdegf3abcegfd f,Kruskal,算法,v,4,v,5,v,1,v,3,2,5,v,2,v,6,v,7,1,10,6,4,7,2,4,1,3,8,v,4,v,5,v,1,v,3,v,2,v,6,v,7,1,1,2,2,4,6,Kruskal算法v4v5v1v325v2v6v711064,算法描述,:,构造非连通图,ST=(V,);,k=i=0;/k,选中的边数,while(kn-1),+i;,检查边集,E,中第,i,条权值最小的边,(u,v);,if,若,(u,v),加入,ST,后不使,ST,中产生回路,，,则输出边,(u,v);,且,k+;,Kruskal,算法,算法描述:构造非连通图 ST=(V,);Kruskal,两种算法的比较,普里姆算法,克鲁斯卡尔算法,时间复杂度,O(n,2,),O(eloge),稠密图,稀疏图,算法名称,适应范围,两种算法的比较普里姆算法克鲁斯卡尔算法时间复杂度O(n2)O,课堂练习,求出图中最小生成树,a,b,e,d,8,c,9,2,4,4,7,5,6,课堂练习求出图中最小生成树abed8c9244756,小结和作业,1.,普里姆算法,2.,克鲁斯卡尔算法,3.,两种算法的比较,2.,最小生成树算法,1.,图的生成树和生成森林,作业：,P275,9.15,9.18,小结和作业1.普里姆算法2.克鲁斯卡尔算法 3.两种算法的,
展开阅读全文