实现并查集-04

Posted by franki on January 3, 2021

并查集 04

现实生活中,社交网络,计算机网络,如何知道两两之间是否存在联系,就是要通过并查集的方式去寻找出他们是否有根节点来确定。如果有则认为他们是有联系的,否则无。

第四版并查集

高度低的树指向高度高的树

代码

class UnionFindFour {
    constructor(size) {
        // parent[i]表示第i个元素所指向的父节点
        this.parent = new Array(size);
        // rank[i]表示以i为根的集合所表示的树的层数
        this.rank = new Array(size);
        // 数组个数
        this.count = size;

        // 初始化,每一个parent[i]指向自己,表示每一个元素自己自成一个集合
        for (let i = 0; i < size; i++) {
            this.parent[i] = i;
            this.rank[i] = 1;
        }
    }

    // 合并元素p和元素q所属的集合
    // O(h) 复杂度,h为树的高度
    unionElements(p, q) {
        const pRoot = this.find(p);
        const qRoot = this.find(q);

        if (pRoot === qRoot) {
            return;
        }

        // 根据两个元素所在树的元素个数不同判断合并方向
        // 将元素个数少的集合合并到元素个数多的集合上
        if (this.rank[pRoot] < this.rank[qRoot]) {
            this.parent[pRoot] = qRoot;
        } else if (this.rank[qRoot] < this.rank[pRoot]) {
            this.parent[qRoot] = pRoot;
        } else {
            this.parent[pRoot] = qRoot;
            // 维护rank的值
            this.rank[qRoot] += 1;
        }
    }

    // 查看过程,查找元素p所对应的集合编号
    // O(h) 复杂度,h为树的高度
    find(p) {
        if (p < 0 || p >= this.count) {
            throw new Error("index out of bound.");
        }
        // 不断去查询自己的父节点,知道达到根节点
        // 根节点的特点:parent[p] = p
        while (p !== this.parent[p]) {
            p = this.parent[p];
        }

        return p;
    }

    // 查看元素p和元素q是否所属一个集合
    // O(h) 复杂度,h为树的高度
    isConnected(p, q) {
        return this.find(p) === this.find(q);
    }
}