You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
2.2 KiB
2.2 KiB
并查集
在计算机科学中，并查集（英文：Disjoint-set data structure，直译为不交集数据结构）是一种数据结构，用于处理一些不交集（Disjoint sets，一系列没有重复元素的集合）的合并及查询问题。
解决两大块区域的合并问题，常用在图等领域中。
并查集的模型
- 有若干个样本a、b、c、d…类型假设是V
- 在并查集中一开始认为每个样本都在单独的集合里
- 用户可以在任何时候调用如下两个方法： boolean isSameSet(V x, V y) : 查询样本x和样本y是否属于一个集合 void union(V x, V y) : 把x和y各自所在集合的所有样本合并成一个集合
- isSameSet和union方法的代价越低越好
合并
合并操作是将两个并查集指向同一个代表节点，而不是将两个集合放到一个新的集合中。可以使用map或者数组实现合并操作。数组实现的合并操作在常数项时间复杂度更有优势。小集合挂在大集合的下面，可以减少路径压缩操作。
查询
从下往上递归查找代表节点，并处理路径压缩。可以借助Stack或者数组处理路径压缩。
并查集的特点
- 每个节点都有一条往上指的指针
- 节点a往上找到的头节点，叫做a所在集合的代表节点
- 查询x和y是否属于同一个集合，就是看看找到的代表节点是不是一个
- 把x和y各自所在集合的所有点合并成一个集合，只需要小集合的代表点挂在大集合的代表点的下方
- 如果方法调用很频繁，那么单次调用的时间复杂度为O(1)
LeetCode547 Friend Circles 使用并查集合并，最后返回子集的个数 LeetCode200 Number of Islands 给定一个二维数组matrix，里面的值不是1就是0，上、下、左、右相邻的1认为是一片岛，返回matrix中岛的数量。 合并、查询，暴力循环(上下左右递归感染)、使用map实现并查集、使用数组实现并查集 LeetCode305 Number of Islands II
岛问题扩展 如果matrix极大，设计一种可行的并行计算方案