并查集这种结构是为了以常量的时间复杂度解决这样的问题：

  • 判断两个节点是否在同一个集合
  • 如何合并两个集合

并查集结构通常会在图中使用，例如克鲁斯卡尔算法。

结构

  1. public class UnionFindSet<V> {
  2.     //并查集节点
  3.     public static class Node<V> {
  4.         //当前节点的值
  5.         public V value;
  6.         //上一个节点
  7.         public Node<V> pre;
  8.         //这个节点作为集合的代表节点(head)，集合中的节点个数
  9.         public int size;
  10.         public Node(V v) {
  11.             this.value = value;
  12.             this.pre = this;
  13.             this.size = 1;
  14.         }
  15.     }
  16.     //所有元素的Map
  17.     public HashMap<V,Node<V>> elementMap;
  18.     public UnionFindSet(Collection<V> collection) {
  19.         this.elementMap = new HashMap<>();
  20.         for (V v : collection) {
  21.             Node node = new Node(v);
  22.             this.elementMap.put(v,node); 
  23.        }
  24.     }
  25.     //找到节点所在集合的代表节点(头节点)
  26.     public Node<V> findHead(Node<V> element) {
  27.         Node node = element;
  28.         //扁平优化
  29.         Stack<Node<V>> stack = new Stack<>();
  30.         while (node != node.pre) {
  31.             stack.push(node);
  32.             node = node.pre;
  33.         }
  34.         //扁平优化
  35.         while (!stack.isEmpty()) {
  36.             stack.pop().pre = node;
  37.         }
  38.         return node; 
  39.     }
  40.     //查看两个节点是否在同一个集合中
  41.     public boolean isSameSet(V a,V b) {
  42.         if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
  43.             return findHead(elementMap.get(a)) == findHead(elementMap.get(b));
  44.         } else {
  45.             return false; 
  46.         }
  47.     }
  48.     //合并集合
  49.     public void union(V a,V b) {
  50.         if (elementMap.containsKey(a) && elementMap.containsKey(b)) {
  51.             Node<V> headA = findHead(elementMap.get(a));
  52.             Node<V> headB = findHead(elementMap.get(b));
  53.             if (headA != headB) {
  54.                 //找到节点数更多的集合
  55.                 Node<V> big = headA.size >= headB.size ? headA : headB;
  56.                 Node<V> small = big == headA ? headB : headA;
  57.                 //让small集合挂载到big集合上
  58.                 small.pre = big;
  59.                 big.size += small.size;
  60.                 small.size = 0 ;
  61.             }
  62.         }
  63.     } 
  64. }

并查集实现克鲁斯卡尔算法

  1. public static Set<Edge> kruskal(Graph graph) {
  2.         Set<Edge> ans = new HashSet<>();
  3.         UnionFindSet<Node> unionFindSet = new UnionFindSet<Node>(graph.nodes.values());
  4.         PriorityQueue<Edge> queue = new PriorityQueue<>(new Comparator<Edge>() {
  5.             @Override
  6.             public int compare(Edge o1, Edge o2) {
  7.                 return o1.weight - o2.weight;
  8.             }
  9.         });
  10.         for (Edge edge : graph.edges) {
  11.             queue.offer(edge);
  12.         }
  13.         while (!queue.isEmpty()) {
  14.             Edge edge = queue.poll();
  15.             Node from = edge.from;
  16.             Node to = edge.to;
  17.             if (!unionFindSet.isSameSet(from,to)) {
  18.                 ans.add(edge);
  19.                 unionFindSet.union(from,to);
  20.             }
  21.         }
  22.         return ans;
  23.     }