【数据结构】并查集

并查集

并查集中有三个哈希表，存储三种信息：

• 元素表：存储用户传入的数据类型 V 到自定义包装类型 Element <V>间的映射（装饰器模式）。该表用于根据用户传入的变量查询自定义的包装类型变量
• 父节点表：存储每个元素的父节点的信息（头节点的父节点是其自身）
• 秩表：存储每个集合中元素节点的个数（只有每个集合的头节点才存储在该表中）

并查集的主要思想：

• 查找某个元素的头节点：从父节点表中不断遍历当前元素的父节点，直到父节点等于自身，即找到了头节点
• 判断两个元素所在的集合是否相同：寻找每个元素所在集合的头节点，判断二者是否相等
• 合并两个集合：将节点数量少的集合的头节点的父节点设置为节点多的集合的父节点（节点数量存储在秩表中）

一种通用的并查集模板：

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

public class UnionFind {
   public static class Element<V> {
      private V value;
      public Element(V v) {
         this.value = v;
      }
   }

   public static class UnionFindSet<V> {
      // 保存每个V对象与其对应的包装类对象Element<V>
      public Map<V, Element<V>> elementMap;
      // 保存每个节点的父元素
      public Map<Element<V>, Element<V>> fatherMap;
      // 保存每个头节点所在并查集的大小（只有头结点才保存该信息，代表该头结点所在的并查集有多少节点）
      public Map<Element<V>, Integer> rankMap;

      // 初始化并查集时需要给每个元素单独创建自己所在的集合
      public UnionFindSet(List<V> list) {
         elementMap = new HashMap<>();
         fatherMap = new HashMap<>();
         rankMap = new HashMap<>();

         for (V v : list) {
            Element<V> element = new Element<V>(v);
            elementMap.put(v, element);
            fatherMap.put(element, element);
            rankMap.put(element, 1);
         }
      }

      public Element<V> findHead(Element<V> element) {
         // 创建一个栈，用于在寻找element头节点的过程中，将途径元素都记录下来，
         // 并在找到头节点后依次弹出，重新设置其父节点为找到的头节点，做到路径压缩（扁平化）
         Stack<Element<V>> path = new Stack<>();
         // 不创建额外的变量，复用element不断指向新的父节点，直到指向头结点
         while (element != fatherMap.get(element)) {
            path.push(element);
            element = fatherMap.get(element);
         }

         // 找到头节点后，将栈中每个节点都重新设置父节点
         while (!path.isEmpty()) {
            fatherMap.put(path.pop(), element);
         }
         return element;
      }

      public boolean isSameSet(V a, V b) {
         if (!elementMap.containsKey(a) || !elementMap.containsKey(b)) {
            // 如果集合中都不存在这两个元素，则直接返回false
            return false;
         }

         // 判断两个节点的头结点是否相等，如果不相等，则不在同一个集合中
         return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
      }

      public void union(V a, V b) {
         if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
            Element<V> aH = findHead(elementMap.get(a));
            Element<V> bH = findHead(elementMap.get(b));
            if (aH != bH) {
               Element<V> big = rankMap.get(aH) >= rankMap.get(bH) ? aH : bH;
               Element<V> small = big == aH ? bH : aH;
               // 更新小的头的父节点为大的头
               fatherMap.put(small, big);
               // 更新新的头
               rankMap.put(big, rankMap.get(big) + rankMap.get(small));
               // 移除旧的头
               rankMap.remove(small);
            }
         }
      }
   }
}