并查集

什么是并查集

并查集的核心是parent指针，一个结点可以找到自己所属的结点。从而把结点归类。有两个核心操作：

  • Union（用来合并两个并查集）
  • Find（用于查找一个结点的parent）

所以并查集可以叫做：union-find data structure。

什么是路径压缩

我们看两个结点是否属于同一个并查集，实际上只看最顶层的那个parent，如果这两个结点属于同一个最顶层parent，那么它们就在同一个并查集中。

所以我们实际上只需要两层的树结构，让所有其他结点的parent指针指向最顶层parent，这样就能达到扁平化并查集的目的，从而使Find操作从O(logN)的时间复杂度变成O(1)。这就叫：路径压缩

代码如下：

  1. public void findParent(UnionFindSetNode node){
  2.     if(node.parent!=node){
  3.         node.parent = findParent(node.parent);
  4.     }
  5.     return node.parent;
  6. }

这段代码很巧妙，可以在查找本结点父亲的时候，将路径上的所有祖先扁平化。

合并操作

核心目标是：尽可能减少深度。所以需要注意的点是：把深度小的并查集归并到深度大的并查集。我们给并查集多添加一个深度属性：rank，比如两层的并查集，parent的rank就是1，叶子节点们的rank就是0。

代码如下：

  1. public void union(UnionFindSetNode node1, UnionFindSetNode node2){
  2.     UnionFindSetNode parent1 = findParent(node1);
  3.     UnionFindSetNode parent2 = findParent(node2);
  4.     if(parent1!=parent2){
  5.         if(parent1.rank>parent2.rank){
  6.             parent2.parent = parent1;
  7.         }else if(parent1.rank<parent2.rank){
  8.             parent1.parent = parent2;
  9.         }else{
  10.             parent1.parent = parent2;
  11.             parent2.rank++;
  12.         }
  13.     }
  14. }