并查集数据结构以及多机器解决岛屿数量问题

一时失言乱红尘 2023-02-18 01:50 8阅读 0赞

并查集能够解决的问题：

（1）查找两个元素是否处于同一个集合

（2）把两个集合合并。

**并查集要求在建立并查集结构的时候，必须给出所有的并查集数据集，在之后的操作过程中不允许在动态添加数据**。

我们先来看一张小图：

假设数据集如下：1，2，3，4，5，6

![20200615103254468.png][]

如果合并1和2，同时合并3，4，结果如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70][]

我们称1、3为代表节点，\{1，2\}、\{3，4\}、\{5\}、\{6\}是集合。现在合并\{5\}和\{1，2\}，就变成：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 1][]

此时可以解决并查集的第二问题，查询4和1两个元素是否在同一个集合内，怎么做呢？就向上找代表节点，然后发现两个代表节点1和3不一样说明不在同一个集合内，现在合并\{1，2，3\}和\{3，4\}，如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 2][]

代表节点为1了，如果此时查找4和2，是否在同一个集合内，就会发现最终找到的代表节点都是一样的，所以是true。同时查找节点以上都会变成这样：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 3][]

查找结点的path路上每一个节点都会指向代表节点！

这就是并查集数据结构。再看它的应用：

（1）查找两个元素是否处于同一个集合

（2）把两个集合合并。

我们来看一下代码：

因为实际的排序啥的跟node内容是没有关系的，所以节点中可以是任意值：

public static class Node{
            //可以是int、String、char
            //不需要指针
        }

基本数据结构：这里面是两个map集合，我们没有用链表这种方式，因为遍历的复杂度还是比较高的，用map可以保证O（1）,

fatherMap结构是存储了当前节点和它上一级节点，sizeMap是代表节点下面子节点的个数。初始化的时候，node的父节点指向的是自己。大小都是1，相当于每一个元素都是自己的集合代表节点。

public static class UnionFindSet{
            //key => child，value => father
            public HashMap<Node,Node> fatherMap;
            //某个节点所在集合，有多少个
            public HashMap<Node,Integer> sizeMap;
    
            public UnionFindSet(List<Node> nodes){
                makeSets(nodes);
            }
    
            private void makeSets(List<Node> nodes){
                fatherMap = new HashMap<>();
                sizeMap = new HashMap<>();
                for(Node node :nodes){
                    fatherMap.put(node,node);
                    sizeMap.put(node,1);
                }
            }

这个方法是查找这个集合的代表节点，找到代表节点之后，依次返回到路上每一个节点的递归，然后设置每一个节点的父节点都指向代表节点。

private Node findHead(Node node){
                Node  fatherNode = fatherMap.get(node);
                if(fatherNode != node){
                    fatherNode = findHead(fatherNode);
                }
                fatherMap.put(node,fatherNode);
                return fatherNode;
            }

如果不喜欢递归，下面还有一个非递归版本的：

private Node findHea1(Node node){
                Stack<Node> stack = new Stack<>();
                Node cur = node;
                Node parent = fatherMap.get(node);
                while(parent != node){
                    stack.push(cur);
                    cur = parent;
                    parent = fatherMap.get(cur);
                }
                while(!stack.isEmpty()){
                    fatherMap.put(stack.pop(),parent);
                }
                return parent;
            }

判断两个节点是否是同一个集合，就是找到代表节点，然后看代表节点是不是一致，这里面用==表示，只有内存地址或者引用一致的时候，才是相等。

public boolean isSameSet(Node a,Node b){
                return findHead(a) == findHead(b);
            }

合并两个集合，首先拿到两个集合的节点，然后找到代表节点，拿出大小，然后在数量多的代表节点作为整个合并后集合的代表节点，然后更新信息，设置父节点，和大小

public void union(Node a,Node b){
                if(a == null || b == null){
                    return ;
                }
                Node aHead = findHead(a);
                Node bHead = findHead(b);
                if(aHead != bHead){
                    int aSetSize = sizeMap.get(aHead);
                    int bSetSize = sizeMap.get(bHead);
                    if(aSetSize <= bSetSize){
                        fatherMap.put(aHead,bHead);
                        sizeMap.put(bHead,aSetSize + bSetSize);
                    }else{
                        fatherMap.put(bHead,aHead);
                        sizeMap.put(aHead,aSetSize + bSetSize);
                    }
                }
            }

so easy的并查集结构！！！

看一个小题：

岛问题

一个矩阵中只有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

这个矩阵中有三个岛。

相信大家这道题都会了，利用感染的思想。具体解法可以看[https://blog.csdn.net/weixin\_44588495/article/details/106243644][https_blog.csdn.net_weixin_44588495_article_details_106243644]这里面由岛屿数量的解法。

我们现在说的是如果岛屿数据集庞大，一台机器解决很慢，我们需要多台机器如何解决？看下面的图

现在的岛屿：红色1代表陆地，白色的0代表海洋，用多台机器求现在岛屿有多少个，答案实际上上两个对吧。但是我们多台机器如何去算呢？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 4][]

比如两台机器，分别计算左右两边：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 5][]

多台机器难解决的问题在于计算完两边之后，如何合并呢？就是判断边界是否向相连。就像上面显示的，左边两个，右边两个，如果遇到一个边界-1，那么最后你会发现就剩一个岛屿了，实际上是不对的。所以，看如下解决：

（1）第一步：用之前的感染方法，求出每一个机器上面的岛屿数量，左边：2，右边：2。先相加一共是4个。

（2）对于左右两边每一个岛屿都用并查集，集合的代表节点就是起初的感染中心，比如看下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 6][]

下面来看如何做：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 7][]

现在有四个集合和他们分别的代表节点，我们开始比较边界信息，发现是否相连，发现可以连接。再判断是否是同一个集合，发现并不是。所以合并两个集合，总的岛屿数量-1。变成了3，下面的图变成了（这里面没画查询完都指向代表节点）：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 8][]

然后比较相连元素，是不是同一个集合，是同一个集合，不操作。直接结束比较下一个。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 9][]

比较是不是同一个集合内，发现并没有，合并集合，同时总的岛屿数量- 1，变成2，效果如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 10][]

之后再无符合条件，所以最后求出岛屿的数量是2，大家可以试试四台机器或者更多机器的时候，是一样的。

[20200615103254468.png]: https://img-blog.csdnimg.cn/20200615103254468.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200615103409927.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200615103647557.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200615103851258.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200615104014253.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[https_blog.csdn.net_weixin_44588495_article_details_106243644]: https://blog.csdn.net/weixin_44588495/article/details/106243644
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200615105717337.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/2020061510592253.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200615110541727.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200615110718236.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200615110906589.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200615111118111.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/2020061511125436.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDU4ODQ5NQ==,size_16,color_FFFFFF,t_70