并查集

发表于 | 更新于: |
字数统计: 420

并查集

什么是并查集

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

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

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

什么是路径压缩

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

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

代码如下：

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

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

合并操作

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

代码如下：

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