并查集--Union Find
并查集的概念
一种可以用来判断相互关联（同属一个集合）的元素属于几个集合，也可以用来判断图结构中的两点是否是联通的算法（动态连接,时候属于同一个集合）。
假设存在数组
0 1 2 3 4 5 6 7 8 9
他们分别属于集合
0 1 0 1 0 1 0 1 0 1
那么元素0,2,4,6,8及时关联的，同样的1,3,5,7,9也是
上述的0~9并不代表实际的元素，相当于元素的索引
对于一组数据，主要支持两个操作
- union(p,q)
- isConnected(p,q) -> find(p) == find(q)
并查集的应用
- 用来合并集合元素，并确定集合数量，查询元素属于哪一个集合。
Quick Union
- 这里将每一个元素都看做成是一个节点
拿一个数组做比喻
初始化
上面一排的数字是数字的索引,下面一排是所指向的集合
在初始化时,所有的节点都指向自己,此时便是一棵森林
初始化
-
合并4,3
union 4,3
union 4,3
-
合并3,8
Union 3,8
Union 3,8
-
合并9,4
Union 9,4
注意:这里是
9是直接指向的8(需要进行一步遍历操作),是为了防止出现线性结构[但是在某些操作中还是会出现线性结构]
例如 0,1,2,3,4,5,6进行
unioin(0,1),unioin(0,2),unioin(0,3),unioin(0,4),unioin(0,5),unioin(0,6)这样就会形成一个链表
解决方案:让节点少的那棵树指向节点多的那棵树的根节点(基于size的优化 )
假设当前的节点结构如下
当前节点情况
-
执行union(6,2)操作
union(6,2)
直接使用
6的根节点指向2的根节点
基于rank(深度)的优化
上面提到了可能会出现链表的问题,并提出了基于size的解决方法.源码传送门
其实,基于size的优化是不够合理的,在进行元素合并的时候,决定方法复杂度的是树的深度而不是树的元素个数.
例如这个Unoin(4,2)操作,应当通过比较深度来判断谁作为根节点
路径压缩
面所示森林的任意两个元素之间都是鼠疫同一个元素的(根据根节点是否一致进行判定)
相同的效果,明显最左边的树形结构效率最低,中间效率最高,那么如何才能使得树形结构效率靠近中间的树呢?
这里就要涉及到路径压缩.
- 方案一
在find()方法中执行parent[p] = parent[parent[p]]操作
也就是节点上移
遍历结束后的结果
再次遍历4
最终也会成为中间的那棵树
源码传送门
但是上述的核心代码并不能使得二叉树完全成为上述三棵二叉树的中间那棵
- 方案二 通过递归实现
核心代码
if(p != parent[p]) {
parent[p] = find(parent[p]);
}
这里我们计算并查集的时间复杂度是和深度相关O(h)
严格上并查集的时间复杂度:
log*n
几乎是O(1)级别的.
