通常在解题过程中会遇到一种问题,这种问题会给出一个List集合,里面包含n个V类型的数,我们在接收到这个list之后,要把它里面的所有数据先包装成一个节点,然后每一个节点都是一个单独的集合,这样在初始阶段一共就有n个集合。我们把n个单独的集合通过一定的方法合并在一起,以实现高效查找元素的过程。而这样一个通过特定方法组合而成的集合就称之为并查集。
首先,创建出一个节点类。这个节点类可以看作是一个包装过程,目的是将传进来的数据包装成一个节点,后面在并查集中,会对这些包装后的节点进行操作。
// Node structure
public static class Node<V>{
V value;
public Node(V value){
this.value=value;
}
}
然后,创建出一个并查集结构。这个并查集提供了以下几种方法:查找某一个数所在集合的根节点(findAncestor)、两个数是否位于同一个集合(isSameSet)、合并两个集合(union)以及查看当前并查集中的集合数量(sets)。
// UnionFind structure
public static class UnionFind{
// 创建一个nodes表,key为当前V类型的数,value为将这个数包装之后形成的节点
HashMap<V, Node<V>> nodes;
// fathers表,key表示当前节点,vlaue表示当前节点的父节点
HashMap<Node<V>, Node<V>> fathers;
// sizeMap表,key为当前节点,value为当前节点所在集合共有多少个节点
// 这里key通常为某一个集合的代表节点也就是头节点
HashMap<Node<V>, Integer> sizeMap;
// 初始化并查集
public UnionFide(List<V> values){
nodes = new HashMap<>();
parents = new HashMap<>();
sizeMap = new HashMap<>();
fro(V cur : values){
// 初始时刻将传进来的所有V类型的数包装成一个节点
Node<V> node = new Node<>(cur);
// 将当前数和包装后的节点放入nodes表中
nodes.put(cur, node);
// 将当前节点和它的父节点放入fathers表中,初始时刻设置其父节点为自己
fathers.put(node, node);
// 将当前节点为头的集合中节点的数量设为1,因为此时每个V类型的数形成的节点单独为一个集合
sizeMap.put(node, 1);
}
}
// findAncestor方法用于找到当前节点所在集合的最头部节点,也就是当前节点在该集合里的老祖宗
public Node<V> findAncestor(Node<V> cur){
// 搞一个栈path,当cur节点往上找根祖先的时候,把它沿途的祖先们都压进栈里,至于压栈的作用后面会进行说明
Stack<Node<V>> path = new Stack();
// 只有当某个节点的父节点是它自己,才意味着它是自己集合中的根节点
// 当然,一开始的时候每个集合中只有一个节点,那么每个节点都是本集合中的根节点
while(cur != parents.get(cur)){
stack.push(cur); // 如果没有找到根,就把当前这个节点压栈
cur = parents.get(cur); // 然后让当前节点来到它的父结点位置,一直循环往上找
}
// 当程序跳出上一个while循环来到这里,就意味着当前节点cur来到了集合的根节点位置
while(!stack.isEmpty()){
// 这里我们就能知道刚刚压栈是做什么用的了
// 如果栈不为空,就依次弹出节点,并把这些节点的父节点设置成刚刚找到的根节点
// 这些依次弹出的节点,就是最初的cur节点往上找根的祖先们
// 本来它们是以父子的形式找了很长的路才找到根,也就是说这棵树的高度比较高
// 现在,把沿途所有节点的父亲全部设为根节点,这样一来,相当于原来是串起来的高树,现在变成并行的两层树了
// 沿途所有具有父子关系的节点现在都有一个共同的父亲,那就是根节点
parents.put(stack.pop(), cur);
}
// 这件事就叫做路径压缩,目的是当后面再去查找沿途这些节点的根节点时,就能以O(1)的时间复杂度找到
// 做完路径压缩,把刚刚找到的根节点返回就行了
return cur;
}
// isSameSet方法用于判断两个V类型的数所形成的节点是否在同一个集合中
public boolean isSameSet(V a, V b){
// 直接返回这两个节点往上找到的根节点是否相同即可,因为一个集合中只有一个根节点
return findAncestor(nodes.get(a)) == findAncestor(nodes.get(b));
}
// union方法用于将两个数所在的集合合并成一个大的集合
// 合并规则为:小集合挂在大集合的下面
public void union(V a, V b){
// 先看两个数是否在同一集合中,如果不是,就找到各自的根节点,并比较哪个集合的size大,size小的集合挂在size大的集合下面
Node<V> aHead = findAncestor(nodes.get(a));
Node<V> bHead = findAncestor(nodes.get(b));
if(aHead != bHead){
int aSetSize = sizeMap.get(aHead);
int bSetSize = sizeMap.get(bHead);
Node<V> big = aSetSize > bSetSize ? aHead : bHead;
Node<V> small = big == aHead ? bHead : aHead;
// 小集合的根节点的根节点设置成大集合的根节点,这就完成了小集合挂大集合下面
parents.put(small, big);
// 调整大集合的size为大小集合的size之和
sizeMap.put(big, aSetSize + bSetSize);
// 删除小集合的size信息
sizeMap.remove(small);
}
}
// sets方法用于返回当前并查集中有多少个集合,直接返回sizeMap表的大小即可
public int sets(){
return sizeMap.size();
}
}