《算法艺术与信息学竞赛》、黄亮著《算法艺术与信息学竞赛》配套幻灯片本幻灯片可从本书blog上免费下载,,欢迎和作者联系以取得技术支持,也欢迎提供有不同针对性的修改版本,方便更多人使用有任何意见,欢迎在blog上评论Blog地址:http://artofalgo..内容介绍一、最小生成树问题二、Boruvka算法三、Prim算法四、Kruskal算法五、MST唯一性判定六、、最小生成树问题(MST).定义连接每个点的连通图(一定是树):无相等边维护生成森林Fe为无用边,若e的两个端点在F的同一个分量中,但e不在F中对于F的每一个分量从它出去(即恰好有一个端点在此分量内)的最小边为安全边不同的分量可以有相同的安全边结论:MST含有所有安全边,不含无用边..一般最小生成树算法结论:MST含有所有安全边,(黄色),,它经过e’,,w(e)<w’(e),用e替换e’得到更小的T’,,证明原图中删除e后的MST和原来的相同在图中减小一个边的权,求新的MST情况一:e在原MST中情况二:、Borovka算法.
-图论与算法-第七讲 最小生成树 来自淘豆网m.daumloan.com转载请标明出处.
