并查集

一、什么是并查集？

并查集是一种简单的集合表示。

它支持以下 3 种操作：

• Initial(S)：将集合 S 中的所有元素初始化为一个个单元素集合
• Union(S, Root1, Root2)：把集合 S 中的子集合 Root2 并入子集合 Root1 中
• Find(S, x)：查找集合 S 中单元素 x 所在的子集合，并返回子集合的名字

通常用树表示每个子集合，子集合的合并就是树的合并。

子集合 Root2 合并到子集合 Root1，只需要把 Root2 的根节点指向 Root1 的根节点即可。

二、为什么要用并查集？

• 并查集主要用于解决一些元素分组的问题
• 并查集可用于管理一系列不相交的集合，执行集合的合并以及搜索元素所在集合

三、如何实现并查集？

3.1 集合初始化 Initial(S)

void initial (int[] s) {
    for (int i = 0; i < s.length; i++) {
        s[i] = i;
    }
}

初始化后单个元素就是一个集合

集合 S 存储：

[0, 1, 2, 3, 4]

------------------------------------------

集合示意图：
 ___      ___      ___      ___      ___
| 0 |    | 1 |    | 2 |    | 3 |    | 4 |

3.2 子集合合并 Union(S, Root1, Root2)

void union(int[] s, int root1, int root2) {
    s[root2] = root1;
}

比如合并 0 和 1 得到子集合 0：

集合 S 存储：

[0, 0, 2, 3, 4]

------------------------------------------

集合示意图：
 ___      ___      ___      ___
| 0 |    | 2 |    | 3 |    | 4 |
  ^
  |
 ___
| 1 |

再合并 3 和 4 得到子集合 3：

集合 S 存储：

[0, 0, 2, 3, 3]

------------------------------------------

集合示意图：
 ___      ___      ___
| 0 |    | 2 |    | 3 |
  ^                 ^
  |                 |
 ___               ___
| 1 |             | 4 |

还可以把子集合 0 和子集合 3 也合并起来：

集合 S 存储：

[0, 0, 2, 0, 3]

------------------------------------------

集合示意图：
       ___           ___
      | 0 |         | 2 |
        ^
       / \
      /   \
    ___   ___
   | 1 | | 3 |
           ^
           |
          ___
         | 4 |

3.3 查找子集合 Find(S, x)

int find(int[] s, int x) {
    while (s[x] != x) {
        x = s[x];
    }
    return x;
}

比如查找 4 所在集合时，过程是这样的：

  ___________________   _____
 |                   | |     |
 v                   | v     |
[0,     0,     2,     0,     3]

一直往上找，直到根节点为止，就能得到 4 所在的集合。

3.4 元素合并 Union(S, X1, X2)

判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。

• 合并两个元素时，找到它们的根节点合并即可

所以上面的子集合合并代码可以改成这样：

void union(int[] s, int x1, int x2) {
    s[find(x2)] = find(x1);
}

四、路径压缩

简单的并查集，在某些场景下的性能是比较差的，例如：

• 链条变得越来越长的时候，查找根节点也变得越来越耗时

比如，下面查找元素 5 所在的子集合时，每次都需要经过好几个节点：

 ___
| 1 |
  ^
  |
 ___
| 3 |
  ^
  |
 ___
| 4 |
  ^
  |
 ___
| 5 |

在并查集链比较长的时候，每次搜索元素的根节点，都比较耗时。

那怎么解决这个问题呢？

• 并查集中只关注根节点，因此可以采用路径压缩，将元素直接指向根节点

而实现的方法也很简单，就是：

• 在查询时，把路径上所有节点的父节点都指向根节点

代码上实现的话，可以采用递归，类似这样：

int find(int[] s, int x) {
    if (s[x] == x) {
        return x;
    } else {
        s[x] = find(s, s[x]);
        return s[x];
    }
}

相当于把上面的一条直链，变成了多叉树：

       ___
      | 1 |
        ^
      / | \  
     /  |  \
    /   |   \
 ___   ___   ___
| 3 | | 4 | | 5 |

经过路径压缩后，就基本解决了链条过长引起的性能问题。

五、按秩合并

路径压缩虽然能解决查询时链条过长的问题，但是路径压缩是在查询时才做的。

• 当没有查询时，路径不会压缩，还是会出现链路很长的情况
• 每次查询时，只压缩一条路径，其他路径的链路还是很长

这种情况要如何避免呢？

在两个子集合进行合并时，只要尽量满足：

• 把简单的树往复杂的树上合并

就能避免并查集的树深度过大，影响查询的效率。

比如说，2 个子集合长这样：

 ___               ___
| 0 |             | 3 |
  ^
  |
 ___
| 1 |
  ^
  |
 ___ 
| 4 |

子集合的合并可分为 2 种情况：

1. 3 合并到 0，树深度是还是 2，深度不变
2. 0 合并到 3，树深度变成了 3，深度加深了

所以肯定是把深度小的 3 合并到深度大的 0 更好一些，因为这样可以避免节点深度变得更大。

那怎么知道哪个集合的深度更高呢？

• 采用一个额外的数组，记录每个根节点的深度，合并子集合时同时更新

比如说，采用数组 rank 记录节点深度：

• 初始化时，把所有元素的 rank（秩）设为默认值 1
• 合并子集合时，比较两个根节点，把 rank 较小合并到较大的上面

代码实现的话就类似这样：

初始化：

void initial (int[] s, int[] rank) {
    for (int i = 0; i < s.length; i++) {
        s[i] = i;
        rank[i] = 1;
    }
}

合并子集合：

void union(int[] s, int[] rank, int x1, int x2) {
    int root1 = find(x1);
    int root2 = find(x2);
    if (rank[root1] >= rank[root2]) {
        s[root2] = root1;
        // 两棵树深度一样的时候，合并起来会加深一层
        if (rank[root1] == rank[root2] && root1 != root2) {
            rank[root1]++;
        }
    } else {
        s[root1] = root2;
    }
}

两棵树深度一样的时候，合并起来会加深一层：

 ___               ___
| 0 |             | 3 |
  ^                 ^
  |                 |
 ___               ___
| 1 |             | 4 |

    ___
   | 0 |
     ^
    / \
   /   \
 ___   ___
| 1 | | 3 |
        ^
        |
       ___
      | 4 |

按秩合并和路径压缩一起用的时候，路径压缩会影响到 rank 值，导致它不准确。

虽然 rank 值不准确，但是不影响 2 者结合一起用。

总结

并查集是一种简单的集合表示，包括 3 种操作：

• Initial(S)：将集合 S 中的所有元素初始化为一个个单元素集合
• Union(S, Root1, Root2)：把集合 S 中的子集合 Root2 并入子集合 Root1 中
• Find(S, x)：查找集合 S 中单元素 x 所在的子集合，并返回子集合的名字

并查集的作用：

• 并查集主要用于解决一些元素分组的问题
• 并查集可用于管理一系列不相交的集合，执行集合的合并以及搜索元素所在集合

并查集有 2 种方法优化方式：

• 路径压缩：查询时压缩节点路径，直接指向根节点
• 按秩合并：合并时，深度小的合并到深度大的树上面

按秩合并和路径压缩一起用：

• 路径压缩会影响到按秩合并的 rank 值，导致它不准确
• 虽然 rank 值不准确了，但是不影响 2 者结合一起用

参考

《数据结构》王道考研系列

https://zhuanlan.zhihu.com/p/93647900

https://blog.csdn.net/weixin_38279101/article/details/112546053

https://blog.csdn.net/qq_40378034/article/details/103224445

https://destiny1020.blog.csdn.net/article/details/7655764

附录

完整代码

/**
 * 并查集-路径压缩 + 按秩合并
 */
public class UnionFind {

    /**
     * 父节点存储
     */
    private int[] parent;
    /**
     * 节点深度
     */
    private int[] rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        init(n);
    }

    /**
     * 初始化并查集
     *
     * @param n 元素个数
     */
    private void init(int n) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    /**
     * 查找元素
     *
     * @param x 指定元素
     * @return 元素根节点
     */
    public int find(int x) {
        if (parent[x] == x) {
            return x;
        } else {
            // 路径压缩，会导致 rank 有误差
            parent[x] = find(parent[x]);
            return parent[x];
        }
    }

    /**
     * 合并元素子集合
     *
     * @param x1 元素
     * @param x2 元素
     */
    public void union(int x1, int x2) {
        int root1 = find(x1);
        int root2 = find(x2);
        if (root1 == root2) {
            return;
        }

        // 按秩合并
        if (rank[root1] > rank[root2]) {
            parent[root2] = root1;
        } else if (rank[root1] < rank[root2]) {
            parent[root1] = root2;
        } else {
            // 深度一样的时候，合并起来会加深一层
            parent[root2] = root1;
            rank[root1]++;
        }
    }

}