并查集实现 | ZackYJ’s Blog

type

Post

status

Published

date

Nov 14, 2021

slug

summary

并查集也叫不相交集合，是一种树状结构，适合解决集合连接等相关问题

介绍

并查集解决的问题：

有若干个样本a、b、c、...类型假设是V
并查集中一开始认为每个样本都在单独的集合里

并查集的核心操作：单次调用时时间复杂度 O（1）

Find(V)/findRepresent(V) 查找元素所在的集合（或代表节点）
boolean isSameSet（Vx，Vy） 查询样本x和样本y是否属于一个集合
void union(Vx，Vy) 把x和y各自所在集合的所有样本合并成一个集合

实现

数组实现

如果并查集中只存储整型元素，就可以使用数组实现

数组 i 下标存储i 的父节点

Quick Find

Union — 合并：将v1所在集合的所有元素都嫁接到v2的父节点上

即：将下标v1的元素的值（父节点）改为下标v2元素的值（父节点）
原来父节点是v1的节点，父节点也改为 v2


public void union(int v1,int v2){
    int p1 = find(v1);
    int p2 = find(v2);
    if(p1 == p2) { return; }

    for(int i = 0;i<parents.length;i++){
        if(parents[i] == p1){
            parents[i] = p2;
        }
    }
}

扫描了一遍数组，时间复杂度O(n)

Find — 查找元素所在集合（父节点）


public int find(int v){
  rangeCheck(v);
  return parents[v];
}

union最终形成的结构一个集合的高度只有2层，只需找一层即可找到父节点
数组的任意访问，时间复杂度O(1)

isSameSet -是否是同一个集合


public boolean isSameSet(int v1,int v2){
  return  find(v1) == find(v2);
}

Quick Union

Union和 Find 时间复杂度都是 O(logn)

Union合并：让v1的根节点嫁接到v2的根节点上


public void union(int v1, int v2) {
    int p1 = find(v1);
    int p2 = find(v2);
    if(p1 == p2) {
        return;
    }

    parents[p1] = p2;
}

Find -查找元素所在集合（父节点）

数组中不断向上找，直到父节点是自己（没有父节点就是根节点）


public int find(int v) {
    rangeCheck(v);
    while(v != parents[v]){
        v = parents[v];
    }
    return v;
}

isSameSet -是否是同一个集合


public boolean isSameSet(int v1,int v2){
  return  find(v1) == find(v2);
}

哈希表实现

使用哈希表存储包装好的节点对象可以实现存储自定义类型

并基于Rank的优化和路径优化


public class GenericUnionFind<V> {
    //样本和包装的Node对象对应表（仅用于初始化）
    private Map<V,Node<V>> nodes = new HashMap<V,Node<V>>();

    private static class Node<V>{
        //高度，Union时进行优化
        int rank = 1;
        //节点存储的值
        V value;
        //父节点
        Node<V> parent = this;
    }

    public void initSet(V v){
        if(nodes.containsKey(v)) {return;}
        nodes.put(v,new Node<>());
    }

    public V find(V v){
        Node<V> node = findNode(v);
        return node == null ? null : node.value;
    }

    private Node<V> findNode(V v){
        Node<V> node = nodes.get(v);
        if( node == null) {return null;}
        while(!Objects.equals(node.value,node.parent.value)){
            node.parent = node.parent.parent;
            node = node.parent;
        }
        return node;
    }

    public void union(V v1,V v2){
        Node<V> p1 = findNode(v1);
        Node<V> p2 = findNode(v2);
        if((p1 == null || p2 == null )||Objects.equals(p1.value,p2.value)) {return;}
        if(p1.rank < p2.rank){
            p1.parent = p2;
        }else if(p2.rank < p1.rank){
            p2.rank = p1.rank;
        }else{
            p1.parent = p2;
            p2.rank++;
        }
    }

    public boolean isSame(V v1,V v2){
        return Objects.equals(find(v1),find(v2));
    }
}

链表+哈希表


public class GenericUnionFind<V> {
    //样本和包装的Node对象对应表（仅用于初始化）
    private Map<V,Node<V>> nodes = new HashMap<V,Node<V>>();

    private static class Node<V>{
        //高度，Union时进行优化
        int rank = 1;
        //节点存储的值
        V value;
        //父节点
        Node<V> parent = this;
    }

    public void initSet(V v){
        if(nodes.containsKey(v)) {return;}
        nodes.put(v,new Node<>());
    }

    public V find(V v){
        Node<V> node = findNode(v);
        return node == null ? null : node.value;
    }

    private Node<V> findNode(V v){
        Node<V> node = nodes.get(v);
        if( node == null) {return null;}
        while(!Objects.equals(node.value,node.parent.value)){
            node.parent = node.parent.parent;
            node = node.parent;
        }
        return node;
    }

    public void union(V v1,V v2){
        Node<V> p1 = findNode(v1);
        Node<V> p2 = findNode(v2);
        if((p1 == null || p2 == null )||Objects.equals(p1.value,p2.value)) {return;}
        if(p1.rank < p2.rank){
            p1.parent = p2;
        }else if(p2.rank < p1.rank){
            p2.rank = p1.rank;
        }else{
            p1.parent = p2;
            p2.rank++;
        }
    }

    public boolean isSame(V v1,V v2){
        return Objects.equals(find(v1),find(v2));
    }
}

优化

Union 的过程中可能出现树不平衡的情况，退化成链表，导致复杂度降低到O(n)

最佳实践：QuickUnion+基于Rank优化+路径减半Path Halving

Quick Union

基于Size

元素少的数，嫁接到元素多的树


//记录以i为根节点的树有多少个元素
int[] sizes;
public UnionFind_QU_Size(int capacity) {
    super(capacity);
    sizes = new int[capacity];
    for(int i = 0;i<sizes.length;i++){
        sizes[i] = 1;
    }
}

public void union(int v1, int v2) {
    int p1 = find(v1);
    int p2 = find(v2);
    if(p1 == p2) {
        return;
    }
    if(sizes[p1] < sizes[p2]){
        //p1嫁接到p2上
        parents[p1] = p2;
        //更新p2的size
        sizes[p2] += sizes[p1];
    }else{
       //p2嫁接到p1上
        parents[p2] = p1;
        //更新p1的高度
        sizes[p1] += sizes[p2];
    }
}

缺点：基于Size也可能导致树不平衡（元素少不一定高度低）

基于Rank优化

矮的树 嫁接到 高的树


int[] ranks;
public UnionFind_QU_Rank(int capacity) {
    super(capacity);
    ranks = new int[capacity];
    for(int i = 0;i<ranks.length;i++){
        ranks[i] = 1;
    }
}
public void union(int v1, int v2) {
    int p1 = find(v1);
    int p2 = find(v2);
    if(p1 == p2) { return;}
    if(ranks[p1] < ranks[p2]){
        parents[p1] = p2;
    }else if(ranks[p1] > ranks[p2]){
        parents[p2] = p1;
    }else{  //高度相等时注意高度长高了
        parents[p1] = p2;
        ranks[p2]++;
    }
}

路径优化

随着Union次数变多，树的高度将越来越高，导致find操作变慢。

路径压缩

在find操作时让路径上所有节点都指向根节点（让树变扁平）


  public int findPC(int v){
      rangeCheck(v);
      if(parents[v] != v){  //所有的非根节点
          parents[v] = find(parents[v]);
      }
      return parents[v];
  }

所有节点都指向根节点，实现成本稍高。还有两种更优的做法：

路径分裂

使路径上每个节点都指向其祖父节点（parent的parent)，直到根节点


public int findPS(int v){
  rangeCheck(v);
  while(v != parents[v]){
      int parent = parents[v];
      parents[v] = parents[parent];
      v = parent;
  }
  return v;
}

路径减半

使路径上每隔一个节点就指向其祖父节点


public int findPH(int v){
    rangeCheck(v);
    while(v != parents[v]){
        parents[v] = parents[parents[v]];
        v = parents[v];
    }
    return v;
}