并查集算法

看到个有意思的题

岛问题
一个矩阵中只有0和1两种值,每个位置都可以和自己的上下左右四个位置相连,如果有一片1连在一起,这个部分叫做一个岛,求一个矩阵中有几个岛?

举例:
0 0 1 0 1 0
1 1 1 0 1 0
1 0 0 1 0 0
0 0 0 0 0 0
这个矩阵中有三个岛

这个问题就用到了并查集算法
指的就是初始时并查集中的元素是不相交的，经过一系列的基本操作(Union)，最终合并成一个大的集合。

比较抽象,先来说是怎么做的吧

第一次遍历如下图

image.png

这条路上,是连通的,就是1个岛,岛数加1,同时也把被"感染"的1改为2.

第二次遍历如下图

image.png

岛数加1,同时把被感染的1改为2

第三次遍历如下图

image.png

岛数加1,同时把被感染的数该为2

最终,就是3个岛.
代码如下

public class Test {
    public static void main(String[] args) {

    }

    public  static  int countIslands(int[][] m){
        if(m == null || m[0] == null){
            return  0;
        }
        int N = m.length;
        int M = m[0].length;
        int res = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(m[i][j]==1){
                    res++;
                    infect(m,i,j,N,M);
                }
            }
        }
        return res;
    }

    private static void infect(int[][] m, int i, int j, int N, int M) {
        if(i<0 || i>=N || j<0 ||j>=M || m[i][j]!=1){
            return;
        }
        m[i][j] = 2;
        infect(m,i+1,j,N,M);
        infect(m,i-1,j,N,M);
        infect(m,i,j+1,N,M);
        infect(m,i,j-1,N,M);
    }
}

看完是不是觉得是what?逗你玩?这有什么？

我们再来推广一下,以上的是在但cpu的情况下,假如让它在多cpu下进行并行计算呢?

即有一个很大的矩阵,我们把它划分为很多和独立的矩阵,每个矩阵算出岛的数量后再合并

那们我们可以发现一个问题,就是切分后就可能不再连通了,所以我们最终的合并不能简单的进行相加,我们现实中也是这样的,就是切分后运行完的结果不是简单的进行合并就可以的,但我们又想要并行计算,那怎么办呢？

其实我们只要处理完后再接着处理边界信息就好了

但我们处理边界信息的时候要注意重复减

解决方案就是,需要记录下感染中心,即第一次感染感染中心是A,第二次感染中心是B

然后分开处理时只需要两个信息,一个是岛的数目,一个是边界信息

边界信息假如左边是A右边是C,那么并集就是(AUC),后面再出现重复的(AUC)就不减

即出现过的就不再减

并行计算的时候,只需要处理最多上下左右四个边界

当然并查集本身还是很复杂的,这也算种下一颗大数据的种子,怎么去并行计算?