生成树学习笔记

生成树学习笔记

代码合集

很好，这还是一篇复习笔记。

考虑这么一个问题，给出一张无向图，有 \(n\) 个点，\(m\) 条边，边有边权，要你找 \(n-1\) 条边，使得这 \(n\) 个点联通且边权和最小。

Kruskal

首先，我们先把边权进行排序，然后贪心的加边，把选的边所带的点加到一个集合里面。

如果 \(x,y\) 已经连通了，这时候来了一条链接 \(x,y\) 的边，那肯定选择不加（边权和最小），那就要涉及到两个点是否在一个集合里面，显然要用并查集。

考虑用数学归纳法证明正确性。

当然，如果有图本身不连通，跑完 kuskral 以后对这些图本身的连通性不变。

因为每个点都至少有一条连边，所以每个点至少会被遍历到一次。一开始每个点所属的集合都不一样，所以一定会出现集合的合并，所以合并完以后，每个节点也都会保留至少一条连边，就保持原来图的连通了。

update in 2024.2.22

关于这样做为什么是最小的，其实考虑一条被我们舍弃的边，如果我们连他的话，最优就是在原图中再舍弃一条边，而这样的舍弃必然不优（从小到大加的）。

时间复杂度是 \(O(m \log m)\) 的。

Prim

和Dij过程很类似，采用贪心的方式。

我们把在生成树中的点的集合称之为点集，用 \(dis\) 数组维护其他点到点集的最小距离。

考虑一开始把任意一个点加入点集中。

然后我们去找到离这个集合最近的点，把这个点加入集合之中。

然后去更新周围点的 \(dis\) 值。

重复第二，第三步即可。

并且如果在集合内的话，\(dis\) 值为 \(0\)，故在第二层循环选出来的点一定是不在集合内的。

如果有多个图的话，考虑采用 \(vis\)，对已经进入生成树的点进行标记，然后没有标记过的点不断跑 Prim 即可，就保证每个点在所属的生成树内了。

做题情况基本已经更新，不在笔记上赘述。

Kuskral 重构树

没想到吧，一年后还会重新来搞这篇学习笔记。

在做 Kuskral 的过程中，你每次不是要合并两个集合嘛，你考虑新建一个节点，然后把两个儿子设为需要合并的两个集合，然后点权设为该边的边权。

于是你就得到了一个有 \(2\times n-1\) 个点的树，这就是Kuskral 重构树。

他的作用在于对于两个点 \(u,v\)，他的 LCA 就是生成树上两个点路径中的最大值。

原因显然，你是从小到大加边的，如果 \(u\) 的联通快和 \(v\) 的联通块被一个新的点联通以后，这个点就是 \(u,v\) 的 LCA，且容易发现最大。

更重要的结论是，这个值还是原图中所有从 \(u\) 到 \(v\) 路径中的最大值的最小值。

如果你从大到小加边，那出来的就是最小值的最大值。

这两个性质是他最经常能的应用。