Union Find

实现并查集-02

Posted by franki on January 3, 2021

并查集 02

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

第二版并查集

快速合并 (quick union)

代码

class UnionFindTwo {
    constructor(size) {
        // 使用一个数组构建一颗指向父节点的树
        this.parent = new Array(size);
        // 数组个数
        this.count = size;

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

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

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

        this.parent[pRoot] = qRoot;
    }

    // 查看过程，查找元素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);
    }
}
CATALOG
    FEATURED TAGS
    前端开发 H5 JavaScript 设计模式 browser jQuery 源码分析 生活 leetcode Array Stack Queue Linked List 剑指offer Binary Search Tree Binary Tree Breadth-First Search Depth-First Search String Set Binary Search Sliding Window Backtracking Dynamic Programming Two Pointers Union Find Sort Bit Operation Recursion Map Graph Search Hash LinkedList QuickSort Trie Design MinHeap Traverse Min Heap Node.js BackEnd SQL MySQL Design Patterns Network 计算机网络 Python
    FRIENDS