最小生成树

· · 算法·理论

摘自本人的图论一文

2. 最小生成树

基本问题:给定一个无向图,求该图边权和最小的生成树。

2.0 常用算法

2.0.1 Kruskal

基本思想:贪心

核心:将所有边按边权升序排序,对于边 (u, v, w)u,v 此时没有联通,那么将此边加入最小生成树中,并连接 (u, v)

优势:方便快捷,好些,稳定。

劣势:处理稠密图不够优秀。

时间复杂度: O(m \log m + m \alpha(n) )

2.0.2 Prim

基本思想:贪心

核心:找出没有与根相连的点中,距离已连接点最近的点加入树中。(有点类似 Dijkstra)

优势:稳定,处理稠密图比较快速。

劣势:不够好写。

时间复杂度:

2.1 在最小生成树上维护信息

具体为,题目所求信息可以通过在任意一个最小生成树上维护出来的情况。本质数据结构。

例题:

2.2 最小/大瓶颈树

当要求生成树两点之间路径上边权的最大值/最小值尽肯能小/大,此时,最小/最大生成树就是最优的解。原因:最小生成树上的边一定是原图中边权尽可能小的边。

例题:

2.3 Kruskal 优化建图

根据 Kruskal 的原理,有时候我们发现有一些边是冗余的边(比如一定可以证明不比另一些边优的),可以不考虑这些边来优化时间复杂度。

例题: