《最小生成树ppt课件.ppt》由会员分享，可在线阅读，更多相关《最小生成树ppt课件.ppt（16页珍藏版）》请在三一办公上搜索。
1、7.4.3 最小生成树,一、最小生成树问题二、如何构造最小生成树,一、最小生成树问题,现实案例：要在 n 个城市之间建立通信联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通信网？,？,问题转化 用连通网来表示n个城市以及n个城市之间可能设置的通信线路，其中网中的顶点表示城市，边表示两城市之间的线路，赋于边的权值表示相应的经济代价。建立总花费最少的通信网问题就转换为求连通网的最小生成树的问题。,回忆赫夫曼树（最优二叉树）假设有n个权值w1，w2wn，构造一棵n个子叶结点的二叉树，每个子叶带权为wi，则其中带权路径长度WPL最小的二叉树。相似最小生成树可有如下
2、定义,最小生成树定义 按照生成树的定义，含n个顶点的连通网的生成树有n个顶点、n-1条边（不构成回路）。因此，可以建立许多不同的生成树，如果一棵生成树的代价等于树上各边权值之和，那么肯定有一棵生成树的代价最小，称为最小代价生成树（简称最小生成树）。,二、如何构造最小生成树？,MST性质：假设N=(V,E)是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中uU，v V-U，则最小生成树中必包含边(u,v)。,U,V-U,u,v,普里姆算法 假设N=(V,E)是连通图，TE是N上最小生成树中边的集合。算法从U=u0(u0V)，TE=开始，重复执行下述操作：在
3、所有uU,v V-U的边(u,v)E中找一条代价最小的边(u0,v0)并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=(V,TE)为N的最小生成树。（从一个结点的子图开始构造生成树：选择连接当前子图和子图外结点的最小权边，将相应结点和边加入子图，直至将所有结点加入子图。）,例子：,B,A,D,C,F,E,B,A,D,C,F,E,B,A,D,C,F,E,B,A,D,C,F,E,B,A,D,C,F,E,B,A,D,C,F,E,6,3,6,2,5,5,1,6,5,1,1,4,1,1,1,4,2,2,2,4,4,3,5,5,（a）,（f）,（e）,（d）,（c）,（b）,
4、4,在此处引入辅助数组,A,B,C,D,E,F,1,5,3,4,2,A,C,F,D,B,E,BE3,BE3,E,A,C,F,D,B,CB5,CE6,CB5,B,E,A,C,F,D,FD2,CE6,FD2,CB5,B,D,E,A,C,F,CF4,CF4,CE6,AD5,CB5,B,D,E,F,A,C,AC1,AD5,AC1,AB6,B,C,D,E,F,A,TE,F,E,D,C,B,V-U,U,小试牛刀,（1）,A,G,F,E,D,C,B,5,21,8,3,7,12,14,18,19,27,16,A,C,D,H,G,F,E,B,4,5,2,5,6,3,2,5,9,3,6,4,5,7,（2）,解：,
5、（1）,A,G,F,E,D,C,B,5,21,8,3,14,16,A,C,D,H,G,F,E,B,5,2,3,2,3,4,5,（2）,克鲁斯卡尔算法,具体做法:先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。一句话，“不构成环的情况下，每次选取最小边”,考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。,例子：,B,A,D,C,F,E,B,A,D,C,F,E,B,A,D,C,F,E,B,A,D,C,F,E,B,A,D,C,F,E,B,A,D,C,F,E,6,3,6,2,5,5,1,6,5,1,1,1,1,1,2,2,2,4,4,3,5,（a）,（f）,（e）,（d）,（c）,（b）,2,3,3,4,1,5,3,4,2,BC5,CF4,BE3,DF2,AC1,TE,
