并查集-解决连通性问题

并查集，在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。

考虑平均查找次数，将节点数更少的树合并到节点数更多的树上，平均查找次数更少。

Quick-find算法

思路：将同一组的节点染成相同颜色

/**
 * 基于染色的思想，一开始所有点的颜色不同
 * 连接两个点的操作，可以看成将一种颜色的点染成另一种颜色
 * 如果两个点颜色一样，证明联通，否则不联通
 * 这种方法叫做并查集的：【Quick-Find算法】
 * 
 * 联通操作：O（1）
 * 合并操作：O（n）
 */
class qucik_find(){
  construstor(n){
    this.color = new Array(n).fill(0).map((item, index) => index);
  }

  find(x){
    return this.color[x];
  }

  merge(a, b){
    if (find(a) === find(b)) return;
    let cb = this.find(b);
    for (let i = 0; i < this.color.length; i++) {
      if (color[i] === cb) color[i] = color[a]
    }
    return;
  }
}

Quick-Union算法

思路：将连通关系转换为树形结构，通过递归的方式快速判定。

/**
 * 每个节点记录与他联通的父节点 根据父节点是否一致判断联通性
 * 联通判断：tree-height树高 O(logN～N)
 * 合并操作：tree-height树高 O(logN～N)
 * 有效减少树高能够提升算法效率
 */

class quick_union {
    constructor(n) {
        this.father = new Array(n).fill(0).map((item, index) => index);//数组 记录每个节点的父节点编号
    }
    find(x) {
        return this.father[x] === x ? x : this.find(this.father[x]);
    }
    merge(a, b) {
        let fa = this.find(a);
        let fb = this.find(b);
        if (fa === fb) return;
        this.father[fa] = fb;
        return;
    }
}

Weighted-Quick-Union算法

思路：通过考虑平均查找次数的方式，对合并过程进行优化。

/**
 * 按质优化：节点数少的接到节点数多的上 节点数多的当父亲
 * 按照‘树的高度’还是‘节点数量’作为合并参考？指标：平均查找次数=总查找次数/节点树
 * a树:节点总数sa，深度和la
 * b树:节点总数sb，深度和lb
 * a作为父亲时:平均查找次数=la+lb+sb/sa+sb 要让sb尽量小
 * b作为父亲时:平均查找次数=la+lb+sa/sa+sb 要让sa尽量小
 * 所以应该让节点总数大的做父亲
 * 
 * 联通操作：O（logN）
 * 合并操作：O（logN）
*/
class weighted_quick_union {
    constructor(n) {
        this.father = new Array(n).fill(0).map((value, index) => index);//当前节点的父节点
        this.size = new Array(n).fill(1);//当前节点作为根节点所在子树的节点数量
    }
    find(x) {
        return this.father[x] === x ? x : this.find(this.father[x]);
    }
    merge(a, b) {
        let ra = this.find(a);
        let rb = this.find(b);
        if (ra === rb) return;
        if (this.size[ra] < this.size[rb]) {
            this.father[ra] = rb;
            this.size[rb] += this.size[ra];
        } else {
            this.father[rb] = ra;
            this.size[ra] += this.size[rb];
        }
    }
}

带路径压缩的Weighted-Quick-Union算法

/**
 * 按质优化+路径压缩
 * 查找的时候 将子节点的父节点设置为根节点
 * 联通操作：near to O（1）
 * 合并操作：near to O（1）
 */
class weighted_quick_union_with_path_compression {
    constructor(n) {
        this.father = new Array(n).fill(0).map((value, index) => index); //当前节点的父节点
        this.size = new Array(n).fill(1); //当前节点作为根节点所在子树的节点数量
    }
    find(x) {
        if (this.father[x] === x) return x;
        let root = this.find(this.father[x]);
        this.father[x] = root;
        return root;
    }
    merge(a, b) {
        let ra = this.find(a);
        let rb = this.find(b);
        if (ra === rb) return;
        if (this.size[ra] < this.size[rb]) {
            this.father[ra] = rb;
            this.size[rb] += this.size[ra];
        } else {
            this.father[rb] = ra;
            this.size[ra] += this.size[rb];
        }
    }
}

带路径压缩的并查集模版

思路：每次查询连通性关系时，对节点到其根节点的路径上所有点进行优化，避免连通性关系从树形结构退化成链表型结构

/**
 * 路径压缩
 * 实际编程只使用路径压缩即可 减少代码量
 * 加上按质优化的差距不大
 * 联通操作：near to O（1）
 * 合并操作：near to O（1）
 */
class quick_union_with_path_compression {
    constructor(n) {
        this.father = new Array(n).fill(0).map((value, index) => index);
    }
    find(x) {
        if (this.father[x] === x) return x;
        let root = this.find(this.father[x]);
        this.father[x] = root;
        return root;
    }
    merge(a, b) {
        let fa = this.find(a);
        let fb = this.find(b);
        if (fa === fb) return;
        this.father[fa] = fb;
    }
}

并查集模版代码

/**
 * 并查集模版代码（路径优化）
 * 联通操作：near to O（1）
 * 合并操作：near to O（1）
 */
class UnionSet {
    constructor(n) {
        this.parent = new Array(n + 1).fill(0).map((value, index) => index);
        // this.cnt = new Array(n + 1).fill(1);
    }
    get(x) {
        return (this.parent[x] =
            this.parent[x] === x ? x : this.get(this.parent[x]));
    }
    merge(a, b) {
        let rootA = this.get(a);
        let rootB = this.get(b);
        if (rootA === rootB) return;
        // this.cnt[rootB] += this.cnt[rootA];
        this.parent[rootA] = rootB;
    }
}