课程内容#
- 并查集：合并集合 [建立连通关系]、查找集合中的连通关系 [判断某两个点是否连通]
连通性问题#
-
-
规则：已经具有连通关系的点不能重复连接
-
将所有点分成了 2 个集合：①、②
-
[PS] 点与点的关系 (合并、判断连通)→也可以是→集合与集合的关系
Quick-Find 算法#
- 核心思想：染色
- 一个颜色，对应一个类别
- 初始化：个体独立，都写成自己的索引，属于一个独立的集合里
- ⭐把和自己连通的所有点的颜色改成要染的颜色
- 时间复杂度
- 连通判断：O (1)—— 查找快，所以叫 Quick-Find
- 合并操作：O (N)—— 需要遍历所有的点才能确定是否要合并
- 🆒引发思考：为什么又叫森林呢？
- 关键在于合并操作，几个点与几个点的合并，集合与集合的合并
- 类似于子树与子树之间的合并，或是将一棵树作为另一棵树的子树
- 所有的集合放在一起，类似于所有的树放在一起，就是森林
- 那么，除了染色还有其他方式吗？
- 思考：染成了什么颜色并不重要，只需要知道和哪些点的颜色相同，即连通
Quick-Union 算法#
- 生活启发：找大哥，找领导
- 核心思想：找代表元素 [根结点]
- 存的值就是其代表元素
- 初始化：个体独立，都写成自己的索引，属于一个独立的集合里
- ⭐找到两点的代表元素，修改其中一个代表元素里的值为另一个代表元素里的值
- 代表元素：里面的值就是它自己
- 联想：大哥或他的小弟叛变了，都从大哥开始叛变，叛变到另一个小弟的大哥那
- 与 Quick-Find 的结果一样，都是把一棵子树整体合并到另一棵子树，不过是通过代表元素来实现的
- 只能是根结点指向根结点
- 时间复杂度
- 都得找根结点，与树高相关
- 连通操作：O (树高)
- 合并操作：O (树高)
- ❗ 2 种情况
- 正常状态→均为 O (logN)
- 退化为一个链表→均为 O (N)
- 对于退化情况，如何解决呢？👇
weighted Quick-Union 算法#
【按秩合并】
- 如何避免退化？→保证枝繁叶茂
- 合并依据 1：树高，矮树挂在高树下 [两两结合]
- 高度为 h 的树，至少需要的结点个数 N 为 2 ^ (h - 1)
- 即树高 h = log [2] N + 1 ≈ log [2] N
- [PS] 只有两棵一样树高的树合并，才会使高度增加
- 合并依据 2：结点数量，结点少的树挂在结点多的树下
- 两种优化方式都能得到 O (logN)，但是合并依据 2【结点数量】更优秀一些
- 合并依据 1：树高，矮树挂在高树下 [两两结合]
- ⭐为什么合并依据 2 更优秀
- 【示例】什么是平均查找次数
- 如下图所示，计算了 A、B 树的平均查找次数
-
- 结点深度即为结点的查找次数，平均查找次数 = 总查找次数 / 总结点数
- 此示例，B 树的查找操作更快
- 【推导】合并依据 2 直接决定平均查找次数
- 对于有 SA、SB 个结点的 A、B 树，它们的总查找次数 LA、LB 分别为：
-
- 其中，li 代表第 i 个结点的深度
-
- 此时进行合并操作，分别计算①A→B 和②B→A 的平均查找次数
- ①当 A 树作为子树合并到 B 树时，为
-
- A 树中的所有结点需要多查找一次
-
- ②当 B 树作为子树合并到 A 树时，为
-
- B 树中的所有结点需要多查找一次
-
- ①当 A 树作为子树合并到 B 树时，为
- ❗【比较两种方式的平均查找次数】
- 和树高 [LA、LB] 没有直接关系，而分子的结点数量 [SA、SB]【直接】决定查找次数，次数越小越好
- 👉谁的结点数少，就作为子树被合并
- ❓思考：上面的推导是否证明高度无法作为合并依据呢？
- ❌否，高度间接影响着结点数量，一般情况高度越低，结点数量越少
- 但是，对于特殊情况，A 树比 B 树高，而 A 树结点数量却比 B 树少时，还是按照【结点数量】作为合并依据，将 A 树作为子树合并到 B 树里
- 对于有 SA、SB 个结点的 A、B 树，它们的总查找次数 LA、LB 分别为：
- 所以以结点数作为合并依据更优秀！👇合并思路如下
- 【示例】什么是平均查找次数
- 在合并两棵子树时
- 如果结点数一样，就按照普通 Quick-Union 的思路换
- 如果不一样，结点数少的子树的根结点接在👉结点数多的子树的根结点下面
- [PS] 换句话说
- 在换大哥时
- 如果小弟数量一样，就按照普通 Quick-Union 的思路换
- 如果不一样，小弟少的大哥得跟👉小弟多的大哥混
+ 路径压缩#
- 参考随堂练习 2 中 weighted Quick-Union 的可视化结果
-
- 0 的位置有些尴尬
- ❗ 不管 0 的代表元素为 1 还是 3，并没区别，将 0 直接挂载 3 的下面，还能减小树高
- 【方法】让每一个非根结点直接指向根结点，让结构扁平化
-
上述算法的效率比较
随堂练习#
Quick-Find vs. Quick-Union#
-
-
【关键】理解 Quick-Union
- 0->1->2->4->5、3->4->5；8->9->7->6
- 查找、合并边界：自己的代表元素就是本身时，停止
Quick-Union vs. weighted Quick-Union#
-
-
【关键】理解 weighted 的含义
- 当两个集合的元素个数不一样时
- 元素少的集合的代表元素的值👉元素多的集合的代表元素的值
- 小弟少的大哥得跟着小弟多的大哥混
-
结果可视化
-
- 很明显，weighted 方法得到的树更矮，合并、查找效率更高
-
代码演示#
HZOJ-71：朋友圈#
样例输入
6 5
1 1 2
2 1 3
1 2 4
1 4 3
2 1 3
样例输出
No
Yes
- 思路
- 使用数据结构 —— 并查集
- 1 即合并操作，2 即查找操作
- 分别测试 Quick-Find、Quick-Union [+weighted、+ 路径压缩、-weighted] 的算法效率
- 代码
Quick-Find#
-
-
-
查找、合并策略：基于染色
Quick-Union#
-
-
基于 Quick-find
- 修改结构定义的 color 为代表元素 father
- 修改查找操作：需要找到底
- 修改合并操作：也要找到两个元素的底，才合并
-
易出现退化为链表的问题，下面进行优化
+ weighted#
-
-
基于 Quick-Union
-
添加 size 属性，记录结点所在集合的结点个数，以此作为合并策略
+ 路径压缩#
-
-
每次查找就会做一次路径压缩，将【查找元素】到【根代表元素】区间的所有元素都指向根代表元素 [根结点]
－weighted#
-
- 抹掉所有与 size 相关的操作
- 有了路径压缩后，不按秩合并 [去除 size 属性] 也能达到很好的效果
HZOJ 平台上题目测试用时
| 方法 | Quick-Find | Quick-Union | +weighted | + 路径压缩 | weighted |
|---|---|---|---|---|---|
| 用时 (ms) | 744 | 2020 | 164 | 172 | 188 |
- Quick-Union 出现了退化问题
- 加了路径压缩后，不按秩合并也能达到很好的效果
- 🆒后三个方法都有不错的效果！
思考点#
- 在 weighted Quick-Union 算法部分，结点数更优秀的推导是否证明高度无法作为合并依据呢？
- ❌否，高度间接影响着结点数量，一般情况高度越低，结点数量越少
- 但是，对于特殊情况，A 树比 B 树高，而 A 树结点数量却比 B 树少时
- 需按照【结点数量】作为合并依据❗ 将 A 树作为子树合并到 B 树里
Tips#
- 《C++ Primer》建议当工具书使用
-
