傻子都能看懂的并查集算法
一、定义
其实并查集顾名思义就是有“合并集合(Union)”和“查找两个元素是否在同一集合(isSameSet)”两种操作的关于数据结构的一种算法。举个例子。如下图
有a、b、c、d、e五个元素，每个元素处于自己的集合中，比如a元素所在的集合只有a这么一个元素，其他也类似。
然后我们定义每个元素的父亲指针指向自己，如下图所示。
二、并查集的合并操作(Union方法)
例如，我们想要将a所在的集合和b所在的集合合并起来。我们首先通过a的父亲指针一直往上找，找到a的最顶部的根节点，即为a。然后同样通过b的父亲指针一直往上找，找到b的最顶部的根节点，即为b。最后将集合元素较少的根节点挂到集合元素较大的根节点，该例子中是b和a两个集合的元素都为1，谁挂谁都可以，假如是b挂a，结果如下图。
此时，如果再执行Union(b,c)这一操作，即合并b所在的集合和c所在的集合。同样，通过b的父亲指针一直往上找，找到b的最顶部的根节点，即为a，然后同样通过c的父亲指针一直往上找，找到c的最顶部的根节点，即为c。然后把c挂到a上面。如下图。
此时，可以看到，a、b、c三个元素属于同一集合了，而d和e还是属于各自的两个不同的集合。
三、并查集的查找两个元素是否在同一集合操作(isSameSet方法)
现在我们想要执行isSameSet(b,c)方法，即判断b和c是否属于同一集合，同样的，我们可以通过b的父亲指针一直往上找，找到b的最顶部的根节点，为a。然后通过c的父亲指针一直往上找，找到c的最顶部的根节点，也为a。此时我们就可以知道，两者的根节点相等，即b和c属于同一集合。
四、如何加速整个算法？
在上面的两个操作中，我们都涉及了同样的一个操作，即找到某个元素的根节点元素，我们暂且定义该操作为findHead操作，那么一直往上找的这个遍历过程我们可以做如下优化。比如，并查集的某一状态如下图所示。
当我们执行Union或者isSameSet操作时候，都会涉及这个findHead操作，比如，执行isSameSet(e,c)的时候，即判断e和c是否属于同一集合，那么我们首先要找到e的根节点，在往上找的过程中，我们可以记录找寻的路径，即会经过e、c、b、a，然后把这些经过的元素的父亲指针直接指向根节点a。（事实上，只需要改变e、c节点的父亲指针指向即可）。那么下次在找c的根节点的时候，就无需再遍历了。
通过该优化后，可以使得并查集的Union和isSameSet两个操作的时间复杂度均为O(1).
五、参考代码
class Element { //1---->元素1.仅仅是包一层的意思。
public int value;
public Element(int value) {
this.value = value;
}
}
public static class UnionFindSet{
public HashMap<Integer,Element> elementMap;
// key 某个元素 value 该元素的父
public HashMap<Element, Element> fatherMap;
// key 某个集合的代表元素 value 该集合的大小
public HashMap<Element, Integer> sizeMap;
public UnionFindSet(ArrayList<Integer> arrList) {
elementMap = new HashMap<>();
fatherMap = new HashMap<>();
sizeMap = new HashMap<>();
for(Integer item:arrList) {
Element ele = new Element(item);
elementMap.put(item, ele);
fatherMap.put(ele, ele);
sizeMap.put(ele, 1);
}
}
public Element findHead(Element ele) {
Stack<Element> stack = new Stack();
while(ele != fatherMap.get(ele)) {
stack.add(ele);
ele = fatherMap.get(ele);
}
while(!stack.isEmpty()) {
fatherMap.put(stack.pop(), ele);
}
return ele;
}
public boolean isSameSet(Integer a, Integer b) {
if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
}
return false;
}
public void union(Integer a, Integer b) {
if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
Element aF = findHead(elementMap.get(a));
Element bF = findHead(elementMap.get(b));
if (aF != bF) {
Element big = sizeMap.get(aF) >= sizeMap.get(bF) ? aF : bF;
Element small = big == aF ? bF : aF;
fatherMap.put(small, big);
sizeMap.put(big, sizeMap.get(aF) + sizeMap.get(bF));
sizeMap.remove(small);
}
}
}
}腾讯云开发者
