2021-11-25 图论

[WanderHuang]

重要问题

1. 环检测
2. 有多少个环
3. 其他

leetcode-1559 二维网格探测环形结构

关键词：并查集 find union，环检测

/**
 * @param {character[][]} grid
 * @return {boolean}
 */
var containsCycle = function(grid) {


    // 并查集-查询 得到任意元素的根结点位置
    function find(x, parent) {
        // 根结点
        if (parent[x] === x) {
            return x;
        } else {
            // 更新根节点
            // 路径压缩算法，可以让平均查找根节点的速度变快
            parent[x] = find(parent[x], parent);
            return parent[x]
        }
    }

    // 并查集-合并 合并任意两个元素为同一个集合，相当于树合并
    function union(x, y, parent) {
        let xRoot = find(x, parent);
        let yRoot = find(y, parent);

        // x y本来就属于同一个集合
        if (xRoot === yRoot) {
            return true;
        } else {
            // 把x的根结点挂载到y的根结点上
            // 挂载后x，y拥有同一个根节点
            parent[xRoot] = yRoot;
            return false;
        }
    }

    let m = grid.length;
    let n = grid[0].length;

    // 并查集，parent为不交集森林，每个元素都是唯一的一棵树，自己为根结点
    // 我们需要搜索二维数组，但是并查集是一维的不交集森林
    let parent = new Array(m * n).fill(0).map((_, len) => len);
    // 从左上角遍历到右下角，任意元素都更新到对应的树里面（任意树的各个元素拥有相同的字符）
    // 角标映射公式
    // k = i * n + j
    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            // 上边
            // 上下字符一样，则执行一次合并
            if (i > 0 && grid[i][j] === grid[i - 1][j]) {
                if (union(i * n + j, (i - 1) * n + j, parent)) {
                    // 合并前两个元素的根就一样，说明就是同一个树上
                    // 由于我们的路径只能查找上边和左边的元素是否相同，碰到两个树的根相等，就说明环路已经形成
                    return true
                }
            }
            // 左边
            if (j > 0 && grid[i][j] === grid[i][j - 1]) {
                if (union(i * n + j, i * n + (j - 1), parent)) {
                    return true;
                }
            }
        }
    }

    return false

// let a = containCycle([
//     ["c","c","c","a"],
//     ["c","d","c","c"],
//     ["c","m","e","c"],
//     ["c","c","c","c"]
//   ]);
// let b = containCycle([
//     ["a","s","a","a"],
//     ["a","s","b","a"],
//     ["a","b","b","a"],
//     ["a","a","a","a"]
//   ])

// console.log(a, b)
};