Union-Find并查集

并查集的作用

并查集主要用来解决集合类的问题，集合间的连通性问题

并查集的实现

主要有两个操作

find：查询节点所在的集合

merge：合并两个节点所在的集合

方案A:quick find

用数组存储每个索引对应的集合，数组的值就是集合的名称代表。

时间复杂度

查找：O(1)

合并：O(n)

function Unionfind(n) {
    this.data = new Array(n)
    //初始化每个节点的值为自己，每个不同的值都是一个集合
    for (let i = 0; i < n; i++) {
        this.data[i] = i
    }
}

// 查找所在集合
Unionfind.prototype.find = function (i) {
    return this.data[i]
}

// 合并集合
Unionfind.prototype.merge = function (x, y) {
    let UnionX = this.data[x]
    let UnionY = this.data[y]
    if (UnionX == UnionY) {
        return
    }
    // 数组内：集合为X的节点都变成Y
    for (let i = 0; i < this.data.length; i++) {
        this.data[i] == UnionX && (this.data[i] = UnionY)
    }
}

方案B:quick union

将各个集合抽象成倒着的树，每个儿子节点指向父亲节点，根节点指向自己

即根节点data[i] = i，儿子节点data[i] = fatherIndex

image.png

function Unionfind(n) {
    this.data = new Array(n)
    //倒着的树，儿子指向父亲。根节点指向自己
    //初始时都是独立的树，都是根节点，都指向自己
    for (let i = 0; i < n; i++) {
        this.data[i] = i
    }
}

// 查找所在集合，需要一直查，直到指向自己
Unionfind.prototype.find = function (i) {
    let root = i
    while (this.data[root] !== root) {
        root = this.data[root]
    }
    return root
}

// 合并集合
Unionfind.prototype.merge = function (x, y) {
    let UnionX = this.find(x)
    let UnionY = this.find(y)
    if (UnionX == UnionY) {
        return
    }
    // 集合X的root指向y集合根节点，所有的节点都挂到y节点上了，y节点的根节点称为两个集合的根节点
    this.data[x] = UnionY
}

方案B的优化

一：带权合并

在执行merge时，上个实现是无规则的将两个树合并成一个。

我们可以优化：挂载时将少的节点树挂到多的节点树上，这样合并后较少的节点多个一个父级。（另一种思路是将树高低的合入树高高的）

二：路径压缩

树的合并极端情况下会合并成为一个链表，查找根节点遍历次数很多，
可以在每次find操作时，直接将遇到的节点都指向根节点，减少后面查找根节点的遍历次数。

路径压缩示意图：

image.png

function Unionfind(n) {
    this.data = new Array(n)
    // 增加一个以i为根节点的树的节点数量，初始都为1
    this.treeSize = new Array(n).fill(1)
    for (let i = 0; i < n; i++) {
        this.data[i] = i
    }
}

// 查找所在集合，需要一直查，直到指向自己
Unionfind.prototype.find = function (i) {
    let root = i
    while (this.data[root] !== root) {
        root = this.data[root]
    }
    //路径压缩：将遍历时遇到的各层节点都直接指向根节点
    while (this.data[i] !== root) {
        let t = i
        i = this.data[i]
        this.data[t] = root
    }
    return root
}

// 合并集合
Unionfind.prototype.merge = function (x, y) {
    let UnionX = this.find(x)
    let UnionY = this.find(y)
    if (UnionX == UnionY) {
        return
    }
    // 带权合并：
    // 挂载时将少的节点树挂到多的节点树上，这样较少的节点多一个父级
    if (this.treeSize[UnionX] < this.treeSize[UnionY]) {
        this.data[UnionX] = UnionY
        this.treeSize[y] = this.treeSize[x] + this.treeSize[y]
    } else {
        this.data[UnionY] = UnionX
        this.treeSize[x] = this.treeSize[x] + this.treeSize[y]
    }
}

200. 岛屿数量

547. 省份数量