并查集基础

  • 并查集是一类抽象化程度很高的数据结构

连通性问题

  • 维护连通关系以及查询连通关系的这一类问题
  • 举个例子，现在有两个操作
    • 一个是连通两个元素，即合并两个元素所在的集合
    • 一个是判断两个元素之间是否有关系，即是否属于同一个集合

Quick-Find 算法

  • 思路：用染色法来标记，同颜色的元素为一个集合
    • 维护连通关系：合并两个集合，代表需要将两个集合的所有元素，染成统一的颜色
    • 查询联通关系：判断元素是否属于某个集合，代表需要对比，元素的颜色与集合的颜色是否相同

  • 实现：

    1. /**
    2. *
    3. * 染色法表示集合关系，两个元素的颜色相同时，表示这两个元素属于同一个集合
    4. *
    5. * 查找操作复杂度为 O(1)
    6. * 合并操作复杂度为 O(n)
    7. */
    8. class QuickFind {
    9. constructor(n) {
    10.   // 初始化元素对应的颜色集合
    11.   this.color = new Array(n);
    13.   // 初始化每个元素的颜色，每个元素的颜色都不一样
    14.   for (let i = 0; i < n; i++) {
    15.     this.color[i] = i;
    16.   }
    17. }
    19. /**
    20.  * 查询 元素 所在的集合
    21.  * 即，查找元素的颜色
    22.  */
    23. find = (x) => {
    24.   return this.color[x];
    25. };
    27. /**
    28.  * 连通 a 与 b
    29.  * 意味着，a 与 b 所在的集合，将被合并为一个集合
    30.  * 即，将两个集合染成统一的颜色
    31.  *
    32.  * 同一种颜色的元素，表示是在同一个集合中
    33.  */
    34. merge = (a, b) => {
    35.   if (this.find(a) === this.find(b)) return;
    37.   const color_a = this.find(a);
    38.   const color_b = this.find(b);
    40.   // 遍历所有集合中的元素颜色，将颜色与 b 相同的元素，染成 a 的颜色
    41.   for (let i = 0; i < n; i++) {
    42.     if (this.find(i) === color_b) {
    43.       this.color[i] = color_a;
    44.     }
    45.   }
    46. };
    47. }

  • 小结：

    • quick-find 算法的连通判断非常快，但是合并操作非常慢
      • 连通判断时间复杂度为 O(1)
      • 合并操作时间复杂度为 O(n)
  • 思考：
    • 本质上，上述问题中，只需要知道一个点与其他哪些点的颜色相同
    • 而若干点的颜色可以通过间接指向同一个节点
    • 合并操作时，实际上是将一颗子树作为另一棵树的子树

Quick-Union 算法

  • 思路：树形结构表示集合关系，两个元素的根节点相同时，表示元素为同一个集合
    • 维护连通关系：合并两个集合，代表需要将两个集合的根节点统一即可
    • 查询联通关系：判断元素是否属于某个集合，代表需要对比，元素的根节点与集合的根节点是否相同

  • 实现：

    1. class QuickUnion {
    2. constructor(n) {
    3.   // 初始化一个 元素对应的 root 的集合
    4.   this.root = new Array(n);
    6.   // 初始化每个元素的 root 为自己
    7.   for (let i = 0; i < n; i++) {
    8.     this.root[n] = i;
    9.   }
    10. }
    12. // 查询元素的 root
    13. find = (x) => {
    14.   if (this.root[x] === x) return x;
    16.   return this.find(this.root[x]);
    17. };
    19. // 连通 a 和 b 两个元素
    20. // 意味着将 a 和 b 所在的集合，合并为一个集合
    21. // 直接将 a 集合的根节点，挂在 b 集合根结点上即可
    22. merge = (a, b) => {
    23.   const root_a = this.find(a);
    24.   const root_b = this.find(b);
    26.   if (root_a === root_b) return;
    28.   this.root[a] = root_b;
    29. };
    30. }

  • 小结：

    • 连通判断 与 合并操作 的复杂度与树高有关，树高越深，复杂度越大
  • 思考：
    • 极端情况下，树会变成一条链表
    • 合并操作时，将节点数量多的树，接到节点数量少的树上面，会导致树高变深
    • 合并操作时，将树高较深的树，接到数高较浅的上面，会导致树高变深

Weighted Qiuck-Union 算法

  • 很显然，要优化上面的 Quick-Union 算法，需要优化合并操作，使得合并后的树的每个节点查找跟节点的次数变少
  • 优化策略为：
    • 合并树时，将节点较少的树作为子树，挂到节点数量较多的树的根节点上

  • 这种方法叫：按秩合并

    1. class UnionSet {
    2. // n 为元素个数，这些元素的编号为 0 ～ n-1
    3. constructor(n) {
    4.   // 每个元素对应的 所在集合的 根节点
    5.   this.root = new Array(n);
    7.   // 每个元素对应的 所在集合的 元素数量
    8.   this.size = new Array(n);
    10.   // 初始化时，集合中每个元素的根节点为自己，所以每个元素所在集合的元素数量为 1
    11.   for (let i = 0; i < n; i++) {
    12.     this.root[i] = i;
    13.     this.size[i] = 1;
    14.   }
    15. }
    17. // 查找 x 的根节点
    18. find = (x) => {
    19.   if (this.root[x] === x) return x;
    21.   return this.find(this.root[x]);
    22. };
    24. // 连通 a, b 两点
    25. // 也就是合并 a, b 所在的两个集合
    26. // 也就是 统一 这两个集合的根节点
    27. merge = (a, b) => {
    28.   let root_a = this.find(a);
    29.   let root_b = this.find(b);
    31.   // 根节点相同，表示两个元素已经是属于同一个集合了
    32.   if (root_a === root_b) return;
    34.   // 元素对应的集合的元素个数较大者，其根元素应作为合并后的集合的根节点
    35.   if (this.size[root_a] > this.size[root_b]) {
    36.     this.root[root_b] = root_a;
    37.     this.size[root_a] += this.size[root_b];
    38.   } else {
    39.     this.root[root_a] = root_b;
    40.     this.size[root_b] += this.size[root_a];
    41.   }
    42. };
    43. }

Weighted Qiuck-Union With Path Compression

  • 带路径压缩的 Weighted Qiuck-Union 算法
  • 理想情况下，元素都直接挂在根节点上，那么在查找该元素的根节点时，就会非常快
  • 优化策略为：
    • 每次查找到元素的根结点时，直接将该元素挂在其根节点上
    • 再次查找该元素根节点时就会非常快

  • 这种方法叫：路径压缩

    class UnionSet {
// n 为元素个数，这些元素的编号为 0 ～ n-1
constructor(n) {
  // 每个元素对应的 所在集合的 根节点
  this.root = new Array(n);

  // 每个元素对应的 所在集合的 元素数量
  this.size = new Array(n);

  // 初始化时，集合中每个元素的根节点为自己，所以每个元素所在集合的元素数量为 1
  for (let i = 0; i < n; i++) {
    this.root[i] = i;
    this.size[i] = 1;
  }
}

// // 查找 x 的根节点
// find = (x) => {
//   if (this.root[x] === x) return x;

//   return this.find(this.root[x]);
// };

/**
 *
 * 路径压缩优化
 *
 * 每次查找到元素的 root 之后，直接将元素挂载到 root 上
 * 下次查找该元素的 root 时，只需要查找一次即可
 *
 */
find = (x) => {
  if (this.root[x] === x) return x;

  let root = this.find(this.root[x]);
  this.root[x] = root;

  return root;
};

// 连通 a, b 两点
// 也就是合并 a, b 所在的两个集合
// 也就是 统一 这两个集合的根节点
//
//
merge = (a, b) => {
  let root_a = this.find(a);
  let root_b = this.find(b);

  // 根节点相同，表示两个元素已经是属于同一个集合了
  if (root_a === root_b) return;

  // 元素对应的集合的元素个数较大者，其根元素应作为合并后的集合的根节点
  if (this.size[root_a] > this.size[root_b]) {
    this.root[root_b] = root_a;
    this.size[root_a] += this.size[root_b];
  } else {
    this.root[root_a] = root_b;
    this.size[root_b] += this.size[root_a];
  }
};
}

时间复杂度小结

Algorithm Constructor Union Find
Quick-Find N N 1
Quick-Union N Tree Height Tree Height
Weighted Quick-Union N LogN LogN
Weighted Quick-Union With Path Compression N Very near to 1 (amortized) Very near to 1 (amortized)

带路径优化的并查集算法代码模版

  • 上述代码，最耗时的操作为 find，通过 路径压缩进行优化后，依然能够很好的提升程序运行效率
  • 考虑实现成本和带来的程序运行效率的提升收益，一般情况下，不需要加上 按秩合并 的代码

  • 在数据量较大时，可以再考虑加上 按秩合并 的优化 ```javascript class UnionSet { // n 为元素个数，这些元素的编号为 0 ～ n-1 constructor(n) { // 每个元素对应的 所在集合的 根节点 this.root = new Array(n);

    // 初始化时，集合中每个元素的根节点为自己，所以每个元素所在集合的元素数量为 1 for (let i = 0; i < n; i++) {

    this.root[i] = i;

    } }

    find = (x) => (this.root[x] = this.root[x] === x ? x : this.find[this.root[x]]);

    // 不需要 按秩合并，直接都挂在 b 的根节点上面 merge = (a, b) => (this.root[this.find(a)] = this.find(b)); }

```