Union Find

实现并查集-01

Posted by franki on January 3, 2021

并查集 01

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

第一版并查集

快速查找 (quick find)

代码

class UnionFindOne {
    constructor(size) {
        // 本质是一个数组
        this.ids = new Array(size);
        // 数组个数
        this.count = size;

        // 初始化，每一个 ids[i] 指向自己
        for (let i = 0; i < size; i++) {
            this.ids[i] = i;
        }
    }

    // 合并元素p和元素q所属的集合
    // O(n) 复杂度
    unionElements(p, q) {
        const pId = this.find(p);
        const qId = this.find(q);

        if (pId === qId) {
            return;
        }

        // 合并过程需要遍历一遍所有元素，将两个元素所属结婚编号合并
        for (let i = 0; i < this.count; i++) {
            if (this.ids[i] === pId) {
                this.ids[i] = qId;
            }
        }
    }

    // 查找过程，查找元素p所对应的集合编号
    find(p) {
        if (p < 0 || p >= this.count) {
            throw new Error("index out of bound.");
        }
        return this.ids[p];
    }

    // 查看元素p和元素q是否所属一个集合
    // O(1) 复杂度
    isConnected(p, q) {
        return this.ids[p] === this.ids[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