union-find 连通性

作用： 判断两个节点是否 连通

quick-find

思路： 通过类似传染的 方法 把相通的结点都变成同一个值

const arr = [0,1,2,3,4,5,6,7,8,9];
const length = arr.length;
const union = (p, q) => {
    if(arr[p] === arr[q]) {
        return ;
    }
    const tempNum = arr[p];
    for(let i = 0; i < length; i++) {
        if(arr[i] === tempNum) {
            arr[i] = arr[q]
        }
    }
}
const params = [
    [4, 3],
    [3, 8],
    [6, 5],
    [9, 4],
    [2, 1],
    [8, 9],
    [5, 0],
    [7, 2],
    [6, 1],
    [1, 0],
    [6, 7],
]
params.forEach(v => {
    union(...v);
})
console.log(arr);

quick-union

思路： 通过 树形的方法 让新加入的节点的根节点 总是指向 另一个的根节点

与quick-find 的区别： quick-find需要每次都遍历数组所有值 quick-union 只需要在自己树进行查找就可以了 但是quick-union 的速度比较依赖输入的数据

const arr = [0,1,2,3,4,5,6,7,8,9];
const length = arr.length;
const union = (p, q) => {
    // 查出根节点 p
    const pRoot = findRoot(p);
    const qRoot = findRoot(q);
    if(pRoot === qRoot) {
        return
    } else {
        arr[pRoot] = qRoot
    }
}

const findRoot = (k)=> {
    while(arr[k] !== k) {
        k = arr[k]
    }
    return k
}

const params = [
    [4, 3],
    [3, 8],
    [6, 5],
    [9, 4],
    [2, 1],
    [8, 9],
    [5, 0],
    [7, 2],
    [6, 1],
    [1, 0],
    [6, 7],
]
params.forEach(v => {
    union(...v);
})
console.log(arr);

加权quick-union

思路：给每个节点 设置一个值 来告知 这个节点树的深度， 两个树连接时候会 将浅的树加入到深的树中

与不加权的quick-union的区别:quick-nuion总是 将后面的加入的节点拼接到 根节点去 而不给树加权， 让 深度浅的树 加到 深度深的树中 从而让 整体树的深度不会越变越深， 让树的深度均衡 解决了不加权时候算法的稳定性

const arr = [0,1,2,3,4,5,6,7,8,9];
const deepArr = [1,1,1,1,1,1,1,1,1,1]; //记录树深度
const length = arr.length;
const union = (p, q) => {
    // 查出根节点 p
    const pRoot = findRoot(p);
    const qRoot = findRoot(q);
    if(pRoot === qRoot) {
        return
    } else {
        if(deepArr[pRoot] >= deepArr[qRoot] ) {
            // 根深度相加
            arr[qRoot] = pRoot;
            deepArr[pRoot] += deepArr[qRoot];
        } else {
            arr[pRoot] = qRoot;
            deepArr[qRoot] += deepArr[pRoot];
        }

    }
}

const findRoot = (k)=> {
    while(arr[k] !== k) {
        k = arr[k]
    }
    return k
}

const params = [
    [4, 3],
    [3, 8],
    [6, 5],
    [9, 4],
    [2, 1],
    [8, 9],
    [5, 0],
    [7, 2],
    [6, 1],
    [1, 0],
    [6, 7],
]
params.forEach(v => {
    union(...v);
})
console.log(arr);