最小生成树总结-笔记7.17

常规
1

最小生成树总结

定义：一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。

求解方法:

·Kruskal

·Prim

·Boruvka

Kruskal

构造过程：

​ 先构造一个只含 n 个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有 n 棵树的一个森林。

​ 之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。

​ 依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。

直接数学证明（调整法）

·设真正的MST是T，如当前最短的边e不在T中

​ 将e强制添加到MST，必然形成一个环 (此时称为基环树）

·删掉环上任意其他边e，得到一个新生成树T’

​ max{ T{e}+{e’}}<=max{T}，则T也是MST

结论: e一定在某个MST中，证毕

image-20230717193546050

Prim

构造过程：

​ 一个加权连通图，其中顶点集合为V，边集合为E；
​ 初始化Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
​ 重复下列操作，直到Vnew = V：
​ a.在集合E中选取权值最小的边<u, v>，其中u为集合Vnew中的元素，而v不在Vnew集合当中，并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
​ b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；
​ 使用集合Vnew和Enew来描述所得到的最小生成树。

**证明：**如e∉任意⽣成树T

​ 将e强加到T形成⼀个环，再删掉环上u的另⼀零边e‘

​ 则T’=T T ∪ {e}\{e’}也是⽣成树

​ 所以

W_{T'}+W_{e'}=W_T+W_e 
⽽
W_e<=W_{e'}

​ 则

W_{T'}<=W_T

即T’包含e且不会变差,证毕

Boruvka

构造过程：

​ 创建一个图表；

​ 从一堆未连接的树开始（树的数量=顶点的数量）；
​ 当存在未连接的树时，对于每个未连接的树：
​ (1)以较小的重量找到它的边缘
​ (2)添加此边以连接另一棵树

image-20230717195235051

正确性证明：
1.最优性：最小边一定包含在生成树中。
2.合法性：一定不会构成环。如果存在环说明一个点的最小连边有两个，显然矛盾。

区别

时间复杂度

Kruskal O(m log m)

Prim 稠密图O(n^2+m)

​ 稀疏图O(m log m)

Boruvka O( (n+m) log m)

代码难度

Kruskal<Prim < Boruvka

结果

Kruskal 边集

Prim 有根树

Boruvka 边集

特点

Kruskal 直接兼容⾮连通图

Prim 只能找⼀个连通分⽀

Boruvka 可以做完全图！！！

总结

Kruskal 可以的情况优先写，代码简单，边多会超时

Prim 边多时优势，但代码相对复杂

Boruvka 边多、点多时有时间的优势，代码复杂

2 个赞