并查集,在一些有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;
}
}