算法-图/DFS/BFS/并查集-岛屿数量

旧城等待， 2023-03-13 06:14 24阅读 0赞

# 算法-图/DFS/BFS/并查集-岛屿数量 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/number-of-islands

## 1.2 题目描述 ##

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1:

输入:  
11110  
11010  
11000  
00000  
输出: 1  
示例 2:

输入:  
11000  
11000  
00100  
00011  
输出: 3  
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

# 2 图-DFS #

## 2.1 思路 ##

将岛屿分布看做有向图，深度遍历该节点的上下左右四个方向。

遍历到一个为’1’的节点时，标记为’0’代表已经遍历过下次不再遍历。

## 2.2 代码 ##

class Solution { 
        public int numIslands(char[][] grid) { 
            int result = 0;
            if(grid == null || grid.length == 0){ 
                return result;
            }
            
            for(int i = 0; i < grid.length; i++){ 
                char[] columns = grid[i];
                for(int j = 0; j < columns.length; j++){ 
                    char c = columns[j];
                    if(c == '1'){ 
                        dfs(grid, i, j);
                        result++;
                    }
                }
            }
            return result;
        }
        private void dfs(char[][] grid, int row, int column){ 
            char[] columns = grid[row];
            char c = columns[column];
            if(c == '0'){ 
                return;
            }else{ 
            	// 标记为'0'代表已经遍历过下次不再遍历。
                grid[row][column] = '0';
                // 继续遍历上下左右四个相邻位置
                if(column - 1 > -1){ 
                    dfs(grid, row, column - 1);
                }
                if(column + 1 < columns.length){ 
                    dfs(grid, row, column + 1);
                }
                if(row + 1 < grid.length){ 
                    dfs(grid, row + 1, column);
                }
                if(row - 1 > -1){ 
                    dfs(grid, row - 1, column);
                }
            }
        }
    }

## 2.3 时间复杂度 ##

![在这里插入图片描述][20200512113450234.png]  
O(N\*M)

*  其中 N 和 M 分别为行数和列数。

## 2.4 空间复杂度 ##

O(N\*M)

*  因为需要递归

# 3 BFS #

## 3.1 思路 ##

将岛屿分布看做有向图，遍历开始后，从当前节点广度优先遍历。

## 3.2 代码 ##

class Solution { 
        private Set<String> recordSet = new HashSet<>();
        public int numIslands(char[][] grid) { 
            int result = 0;
            if(grid == null || grid.length == 0){ 
                return result;
            }
            
            for(int i = 0; i < grid.length; i++){ 
                char[] columns = grid[i];
                for(int j = 0; j < columns.length; j++){ 
                    char c = columns[j];
                    if(c == '1'){ 
                        bfs(grid, i, j);
                        result++;
                    }
                }
            }
            return result;
        }
        private void bfs(char[][] grid, int row, int column){ 
            char[] columns = grid[row];
            char c = columns[column];
            
            if(c == '0'){ 
                return;
            }
            LinkedList<int[]> coordinateQueue = new LinkedList<>();
            coordinateQueue.add(new int[]{ row, column});
            // bfs
            while(!coordinateQueue.isEmpty()){ 
                int[] coordinate = coordinateQueue.poll();
                int i = coordinate[0];
                int j = coordinate[1];
                if(grid[i][j] == '0'){ 
                    continue;
                }
                grid[i][j] = '0';
                if(j - 1 > -1){ 
                    coordinateQueue.add(new int[]{ i, j - 1});
                }
                if(j + 1 < columns.length){ 
                    coordinateQueue.add(new int[]{ i, j + 1});
                }
                if(i + 1 < grid.length){ 
                    coordinateQueue.add(new int[]{ i + 1, j});
                }
                if(i - 1 > -1){ 
                    coordinateQueue.add(new int[]{  i - 1, j});
                }
            }
        }
    }

## 3.3 时间复杂度 ##

![在这里插入图片描述][20200512120459752.png]  
O(N\*M)

*  其中 N 和 M 分别为行数和列数。

## 3.4 空间复杂度 ##

O(min(M,N))

*  最坏情况全是岛屿

# 4 效率很低的第一版并查集 #

## 4.1 思路 ##

做并查集，遇到相邻的’1’节点就合并成一个并查集。

最后返回不同的并查集数。

## 4.2 代码 ##

## 4.3 时间复杂度 ##

![在这里插入图片描述][20200512155229501.png]

# 5 并查集-优化 #

## 5.1 思路 ##

合并两个不同祖先的节点时，将他们的祖先合并为一个即可。

最后遍历计算出不同的祖先数作为结果返回。

在union的时候还采用了压缩路径优化方法，提升查找效率。

## 5.2 代码 ##

class Solution { 
        public int numIslands(char[][] grid) { 
            int result = 0;
            if(grid == null || grid.length == 0){ 
                return result;
            }
    
            int[] unionFindSet = new int[grid.length * grid[0].length];
    
            // 初始化所有节点的并查集，父节点设为自己
            for(int i = 0; i < grid.length; i++){ 
                char[] columns = grid[i];
                for(int j = 0; j < columns.length; j++){ 
                    unionFindSet[i * columns.length + j] = i * columns.length + j;
                }
            }
            // 下面开始合并岛节点
            for(int i = 0; i < grid.length; i++){ 
                char[] columns = grid[i];
                for(int j = 0; j < columns.length; j++){ 
                    char c = columns[j];
                    if(c == '1'){ 
                        // 初始化岛节点的并查集为index+1
                        // find(unionFindSet, i * columns.length + j);
                        // 连接右侧节点
                        if(j + 1 < columns.length && grid[i][j + 1] == '1'){ 
                            // 这里需要将二维数组转为一位数组的下标
                            // 所以使用 当前行*列总数得到该行在一位数组中的首个下标，
                            // 再加上当前列作为偏移数得到在一维数组的下标
                            union(unionFindSet, i * columns.length + j, i * columns.length + j + 1);
                        }
                        // 连接下侧节点
                        if(i + 1 < grid.length && grid[i+1][j] == '1'){ 
                            union(unionFindSet, i * columns.length + j, (i + 1) * columns.length + j);
                        }
                    }else{ 
                        // 海洋节点，将他们的父节点设为-1，不参与累计
                        unionFindSet[i * columns.length + j] = -1;
                    }
                }
            }
            // 去重根节点
            Set<Integer> filter = new HashSet<>();
            // 将所有父节点不为-1的节点全部取出，并寻找他们的父节点
            // 只要父节点不为-1就放入过滤器统计
            for(int i = 0; i < unionFindSet.length; i++){ 
                if(unionFindSet[i] == -1){ 
                    continue;
                }
                int root = find(unionFindSet, i);
                if(root > -1){ 
                    filter.add(root);
                }
            }
            // 最终返回不重复的根节点数
            return filter.size();
        }
    
        private void union(int[] unionFindSet, int p, int q){ 
            int left = find(unionFindSet, p);
            int right = find(unionFindSet, q);
            // 说明本来就在一个并查集内，不用处理
            if(left == right){ 
                return;
            }
            // 将右边元素的老祖先作为左边元素老祖先的父节点，实现联通
            unionFindSet[left] = right;
        }
    
        private int find(int[] unionFindSet, int p){ 
            int son = p;
            // 寻找祖先根节点
            while(p != unionFindSet[p]){ 
                p = unionFindSet[p];
            }
            // 路径压缩优化，将当前节点及祖先节点的父节点都设为祖先根节点
            // 即将高度压缩为2，方便查找
            while(son != p){ 
                int tmp = unionFindSet[son];
                unionFindSet[son] = p;
                son = tmp;
            }
            return p;
        }    
    }

## 5.3 时间复杂度 ##

![在这里插入图片描述][20200512184631320.png]  
参考[岛屿数量][Link 1]

## 5.4 空间复杂度 ##

O(M\*N)

# 参考文档 #

*  [算法-并查集][-]

[20200512113450234.png]: /images/20230312/a87a6dd35947425eaf268416b401eee8.png
[20200512120459752.png]: /images/20230312/2dd59b11e81042e7822642d2afde0898.png
[20200512155229501.png]: /images/20230312/4e1f4371bcd540e98678119442e804e7.png
[20200512184631320.png]: /images/20230312/22f73d43221e4ec7bfb8ba0b5dd72ec5.png
[Link 1]: https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-shu-liang-by-leetcode/
[-]: https://blog.csdn.net/baichoufei90/article/details/106080837