大家好,今天提供不相交集合的笔记(即union/find). 不相交集合有实现简单,证明困难的特点,若有想证明的可以自行查阅相关文献。我就不做赘述啦!
不相交集类解决动态等价类问题,即:
数据结构需要良好支持union和find操作,union操作相对简单,我们关注find操作。
find操作只要求当且仅当两个元素属于同一个集合时,作用在这两个元素上的find返回相同的集合名称。 由此自然想到树: 因为树的每一个元素都有相同的根,所以等价类可以用树表示,不相交集则以森林表示。树的根存储集合名称。 依照上述假设: find操作实质从指定节点向上找到根,所以只需要保存父链
由于只需保存父链,不相交集类(森林)中的等价类(树)可以被非显示的存储在数组中,数组中元素有如下约定:
下图是隐示的森林示意图,上边是隐示森林数组,下边是依据该数组展现实际的森林。
任意合并会出现过深的树,所以采用按秩求并,它保证树的深度不超过O(logN)
/**
* 采用按秩求并
* @param root1 不相交集合1的根
* @param root2 不相交集合2的根
*/
public void union(int root1, int root2) {
if(s[root2]<s[root1]){
s[root1]=root2;
}else{
if(s[root1]==s[root2]){
s[root1]--;
}
s[root2]=root1;
}
}
不进行路径压缩,M次操作,容易出现最差情况O(MlogN),其中N为节点个数
/**
* 查找方式 :路径压缩
* @param x 要寻找的元素
* @return x属于的集合
*/
public int find(int x) {
if (s[x] < 0) {
return x;
} else {
return s[x] = find(s[x]);
}
}
M次union和find的运行时间为:
O(Mlog*N)
什么你觉得太简单了,建议你试着证明! 什么代码没有难度,可以实现各迷宫试试啊!
完整代码地址:https://github.com/floor07/DataStructuresAndAlgorithm/blob/master/src/main/java/chapter8/DisjSets.java
参考他人实现编写的迷宫:https://github.com/floor07/DataStructuresAndAlgorithm/blob/master/src/main/java/chapter8/Maze.java