最小生成树.ppt

算法艺术与信息学竞赛教学幻灯片,算法图论 第七讲 最小生成树,声明,本系列教学幻灯片属于刘汝佳、黄亮著算法艺术与信息学竞赛配套幻灯片 本幻灯片可从本书blog上免费下载，即使您并未购买本书. 若作为教学使用，欢迎和作者联系以取得技术支持，也欢迎提供有不同针对性的修改版本，方便更多人使用 有任何意见，欢迎在blog上评论 Blog地址：,内容介绍,一、最小生成树问题 二、Boruvka算法 三、Prim算法 四、Kruskal算法 五、MST唯一性判定 六、瓶颈生成树,参考资料,CLRS Chapter 23. Minimal Spanning Trees,一、最小生成树问题(MST),定义,连接每个点的连通图（一定是树） 权和尽量小,一般最小生成树算法,前提: 无相等边 维护生成森林F e为无用边, 若e的两个端点在F的同一个分量中, 但e不在F中 对于F的每一个分量 从它出去(即恰好有一个端点在此分量内)的最小边为安全边 不同的分量可以有相同的安全边 结论: MST含有所有安全边, 不含无用边.,一般最小生成树算法,结论: MST含有所有安全边, 不含无用边. 证明 假设有一个分量(黄色), 它的安全边e不在T内. 则u到v有唯一路径, 它经过e, 它恰好有一个端点在黄色分量中. 由于e是安全边, w(e)<w(e), 用e替换e得到更小的T, 矛盾 加入无用边将形成环,练习,证明最小边属于某棵MST中 对于某环上的最大边e, 证明原图中删除e后的MST和原来的相同 在图中减小一个边的权, 求新的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次 二叉堆: 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的时间复杂度如何? 如果边权在0, 1)上均匀分布, Kruskal和Prim哪个算法更快? 计算出MST后, 如果加一个顶点和它所关联的边, 如何快速更新MST?,五、MST唯一性判定,MST唯一性判定,考虑一般最小生成树算法 每一个分量出发安全边唯一, 不特殊处理, 否则 若同时添加会形成环, 一定不唯一 若同时添加不会形成环, 类似正确性证明, 即: 假设某边e不在T中, 对应的e一定比e大而不可能相等,MST唯一性判定,时间复杂度 Boruvka: 不变(只在和安全边比较时修改) Prim: 不变(只在判断顶点标号时修改) Kruskal: 不变(相等的边时特殊处理) 另一种思路: 最小=第二小,六、瓶颈生成树,基本问题,边的最大值最小的生成树成为G的瓶颈生成树(bottleneck spanning tree), 把其中最大的边称为它的权. 显然, MST是一个瓶颈生成树, 但是瓶颈生成树可以算得更快 判定问题 问题: 给一个实数b, 如何在线性时间内判定是否存在一个瓶颈生成树, 它的权不超过b? 方法: 忽略超过b的边, 判断图是否连通,