并查集

我们之前遇到的树结构都是由父亲指向孩子，但是并查集不一样，它是由孩子指向父亲的一种结构，并查集结构可以非常高效的回答连接问题(Connectivity Problem)，它可以很快的判断网络中节点的连接状态。并查集主要支持两个动作

  • union(p, q)
    • 将元素p, q连接起来
  • isConnected(p, q)
    • 判断元素p, q是否是连接的，即是否所属一个集合

这里先给出并查集的接口，后面我们将实现多个版本的并查集

  1. public interface UF {
  2.     public int getSize();
  3.     public boolean isConnected(int p, int q);
  4.     public void unionElements(int p, int q);
  5. }

Quick Find

并查集 - 图1

  1. //第一版的并查集
  2. public class UnionFind1 implements UF{
  3.     private int[] id;
  5.     public UnionFind1(int size) {
  6.         id = new int[size];
  8.         //这时id全部为0，相当于在一个集合中 一开始应该全部不在一个集合中
  9.         for (int i = 0; i < id.length; i++) {
  10.             id[i] = i;
  11.         }
  12.     }
  14.     @Override
  15.     public int getSize() {
  16.         return id.length;
  17.     }
  19.     //找到元素p所属的集合
  20.     private int find(int p) {
  21.         if (p < 0 || p >= id.length) {
  22.             throw new IllegalArgumentException("参数错误");
  23.         }
  25.         return id[p];
  26.     }
  28.     @Override
  29.     public boolean isConnected(int p, int q) {
  30.         return find(p) == find(q);
  31.     }
  33.     @Override
  34.     public void unionElements(int p, int q) {
  35.         if (find(p) == find(q)) {
  36.             return;
  37.         }
  39.         for (int i = 0; i < id.length; i++) {
  40.             if (id[i] == find(p)) {
  41.                 id[i] = find(q);
  42.             }
  43.         }
  44.     }
  45. }

Quick Union

并查集 - 图2

  1. //第二版的并查集
  2. public class UnionFind2 implements UF{
  3.     private int[] parent;
  5.     public UnionFind2(int size) {
  6.         parent = new int[size];
  8.         for (int i = 0; i < parent.length; i++) {
  9.             parent[i] = i;
  10.         }
  11.     }
  13.     @Override
  14.     public int getSize() {
  15.         return parent.length;
  16.     }
  18.     private int find(int index) {
  19.         if (index < 0 || index >= parent.length) {
  20.             throw new IllegalArgumentException("参数错误");
  21.         }
  23.         while (index != parent[index]) {
  24.             index = parent[index];
  25.         }
  26.         return index;
  27.     }
  29.     @Override
  30.     public boolean isConnected(int p, int q) {
  31.         return find(p) == find(q);
  32.     }
  34.     @Override
  35.     public void unionElements(int p, int q) {
  36.         int pRoot = find(p);
  37.         int qRoot = find(q);
  38.         if (pRoot == qRoot) {
  39.             return;
  40.         } else {
  41.             parent[pRoot] = parent[qRoot];
  42.         }
  43.     }
  44. }

基于rank的优化

并查集 - 图3

  1. //第三版的并查集
  2. public class UnionFind3 implements UF{
  3.     private int[] parent;
  4.     //记录根节点的高度
  5.     private int[] rank;
  7.     public UnionFind3(int size) {
  8.         parent = new int[size];
  9.         rank = new int[size];
  11.         for (int i = 0; i < parent.length; i++) {
  12.             parent[i] = i;
  13.             rank[i] = 1;
  14.         }
  15.     }
  17.     @Override
  18.     public int getSize() {
  19.         return parent.length;
  20.     }
  22.     private int find(int index) {
  23.         if (index < 0 || index >= parent.length) {
  24.             throw new IllegalArgumentException("参数错误");
  25.         }
  27.         while (index != parent[index]) {
  28.             index = parent[index];
  29.         }
  30.         return index;
  31.     }
  33.     @Override
  34.     public boolean isConnected(int p, int q) {
  35.         return find(p) == find(q);
  36.     }
  38.     @Override
  39.     public void unionElements(int p, int q) {
  40.         int pRoot = find(p);
  41.         int qRoot = find(q);
  42.         if (pRoot == qRoot) {
  43.             return;
  44.         }
  46.         if (rank[pRoot] <= rank[qRoot]){
  47.             parent[pRoot] = parent[qRoot];
  48.             //只要在两个数的高度相等的时候 树的高度才会增加
  49.             if (rank[pRoot] == rank[qRoot]) {
  50.                 rank[qRoot]++;
  51.             }
  52.         } else {
  53.             parent[qRoot] = parent[pRoot];
  54.         }
  55.     }
  56. }

路径压缩

并查集 - 图4

  1. //第四版的并查集
  2. public class UnionFind4 implements UF{
  3.     private int[] parent;
  4.     private int[] rank;
  6.     public UnionFind4(int size) {
  7.         parent = new int[size];
  8.         rank = new int[size];
  10.         for (int i = 0; i < parent.length; i++) {
  11.             parent[i] = i;
  12.             rank[i] = 1;
  13.         }
  14.     }
  16.     @Override
  17.     public int getSize() {
  18.         return parent.length;
  19.     }
  21.     private int find(int index) {
  22.         if (index < 0 || index >= parent.length) {
  23.             throw new IllegalArgumentException("参数错误");
  24.         }
  26.         while (index != parent[index]) {
  27.             //只添加了这一行代码
  28.             parent[index] = parent[parent[index]];
  29.             index = parent[index];
  30.         }
  31.         return index;
  32.     }
  34.     @Override
  35.     public boolean isConnected(int p, int q) {
  36.         return find(p) == find(q);
  37.     }
  39.     @Override
  40.     public void unionElements(int p, int q) {
  41.         int pRoot = find(p);
  42.         int qRoot = find(q);
  43.         if (pRoot == qRoot) {
  44.             return;
  45.         }
  47.         //这时rank不代表高度 因为在路径压缩时没有维护rank
  48.         //但是整体上rank还是能够表示大小关系的
  49.         if (rank[pRoot] <= rank[qRoot]){
  50.             parent[pRoot] = parent[qRoot];
  52.             if (rank[pRoot] == rank[qRoot]) {
  53.                 rank[qRoot]++;
  54.             }
  55.         } else {
  56.             parent[qRoot] = parent[pRoot];
  57.         }
  58.     }
  59. }

并查集 - 图5

  1. //第五版的并查集
  2. public class UnionFind5 implements UF{
  3.     private int[] parent;
  4.     private int[] rank;
  6.     public UnionFind5(int size) {
  7.         parent = new int[size];
  8.         rank = new int[size];
  10.         for (int i = 0; i < parent.length; i++) {
  11.             parent[i] = i;
  12.             rank[i] = 1;
  13.         }
  14.     }
  16.     @Override
  17.     public int getSize() {
  18.         return parent.length;
  19.     }
  21.     private int find(int index) {
  22.         if (index < 0 || index >= parent.length) {
  23.             throw new IllegalArgumentException("参数错误");
  24.         }
  26.         //修改了这里
  27.         if (index != parent[index]) {
  28.             parent[index] = find(parent[index]);
  29.         }
  30.         return parent[index];
  31.     }
  33.     @Override
  34.     public boolean isConnected(int p, int q) {
  35.         return find(p) == find(q);
  36.     }
  38.     @Override
  39.     public void unionElements(int p, int q) {
  40.         int pRoot = find(p);
  41.         int qRoot = find(q);
  42.         if (pRoot == qRoot) {
  43.             return;
  44.         }
  46.         if (rank[pRoot] <= rank[qRoot]){
  47.             parent[pRoot] = parent[qRoot];
  49.             if (rank[pRoot] == rank[qRoot]) {
  50.                 rank[qRoot]++;
  51.             }
  52.         } else {
  53.             parent[qRoot] = parent[pRoot];
  54.         }
  55.     }
  56. }

第五版的效率不一定比第四版的好，因为第四版最后也可能做到”扁平化”，并且第五版的递归操作比较耗时。