《最小生成树》PPT课件.ppt

《《最小生成树》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《最小生成树》PPT课件.ppt（26页珍藏版）》请在三一办公上搜索。

1、算法艺术与信息学竞赛教学幻灯片,算法图论第七讲 最小生成树,声明,本系列教学幻灯片属于刘汝佳、黄亮著算法艺术与信息学竞赛配套幻灯片本幻灯片可从本书blog上免费下载，即使您并未购买本书.若作为教学使用，欢迎和作者联系以取得技术支持，也欢迎提供有不同针对性的修改版本，方便更多人使用有任何意见，欢迎在blog上评论Blog地址：,内容介绍,一、最小生成树问题二、Boruvka算法三、Prim算法四、Kruskal算法五、MST唯一性判定六、瓶颈生成树,参考资料,CLRS Chapter 23.Minimal Spanning Trees,一、最小生成树问题(MST),定义,连接每个点的连通图（一定

2、是树）权和尽量小,一般最小生成树算法,前提:无相等边维护生成森林Fe为无用边,若e的两个端点在F的同一个分量中,但e不在F中对于F的每一个分量从它出去(即恰好有一个端点在此分量内)的最小边为安全边不同的分量可以有相同的安全边结论:MST含有所有安全边,不含无用边.,一般最小生成树算法,结论:MST含有所有安全边,不含无用边.证明假设有一个分量(黄色),它的安全边e不在T内.则u到v有唯一路径,它经过e,它恰好有一个端点在黄色分量中.由于e是安全边,w(e)w(e),用e替换e得到更小的T,矛盾加入无用边将形成环,练习,证明最小边属于某棵MST中对于某环上的最大边e,证明原图中删除e后的MST和

3、原来的相同在图中减小一个边的权,求新的MST情况一:e在原MST中情况二:e不在原MST中,二、Borovka算法,Boruvka算法,由Boruvka于1926年提出(早于图论产生!),Boruvka算法,每个分量设置leader,用DFS在m时间内求出检查每条边一次以修正各分量的安全边权第i次迭代每个分量大小至少为2i最多logV次迭代,总O(ElogV),三、Prim算法,Prim算法,Prim提出,但事实上Jarnik于1930于年更早提出只关心一棵树T,每次加入T的安全边用堆保存到每个顶点(而非边)的安全边Insert/ExtractMin调用V次,DecreaseKey调用E次二叉

4、堆:O(E+V)logV),Fibonacci堆:O(E+VlogV),练习,给定邻接矩阵,设计一个O(V2)算法对于稀疏图中,用k次Boruvka迭代可以加速MST计算.如何选取k,使得k次迭代以后调用Prim算法的时间复杂度变为O(EloglogV),四、Kruskal算法,Kruskal算法,Kruskal,1956年提出把边从小到大排序,每次填加一个安全边如何知道边是否安全?并查集,每次约O(1)总O(ElogE+E(V),练习,Kruskal返回的MST和边排序结果有关.证明对于任何一个MST,都有一个排序方法使得Kruskal返回此MST如果边权为1|V|的整数,Kruskal的时

5、间复杂度如何?如果边权在0,1)上均匀分布,Kruskal和Prim哪个算法更快?计算出MST后,如果加一个顶点和它所关联的边,如何快速更新MST?,五、MST唯一性判定,MST唯一性判定,考虑一般最小生成树算法每一个分量出发安全边唯一,不特殊处理,否则若同时添加会形成环,一定不唯一若同时添加不会形成环,类似正确性证明,即:假设某边e不在T中,对应的e一定比e大而不可能相等,MST唯一性判定,时间复杂度Boruvka:不变(只在和安全边比较时修改)Prim:不变(只在判断顶点标号时修改)Kruskal:不变(相等的边时特殊处理)另一种思路:最小=第二小,六、瓶颈生成树,基本问题,边的最大值最小的生成树成为G的瓶颈生成树(bottleneck spanning tree),把其中最大的边称为它的权.显然,MST是一个瓶颈生成树,但是瓶颈生成树可以算得更快判定问题问题:给一个实数b,如何在线性时间内判定是否存在一个瓶颈生成树,它的权不超过b?方法:忽略超过b的边,判断图是否连通,