解决岛屿数量问题：并查集、DFS

岛屿数量

leetcode：200
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

示例：

输入:
11110
11010
11000
00000
输出: 1

---

解法一：DFS

染色法是一种简单高效的回溯法。

使用染色法可以重置访问过的数据，本次染色可以上下左右判断。
每次进入 DFS 都要记录次数，DFS 完成的唯一功能就是染色。

染色的缺点是数据已经不再是原有的数据了，如果需要原始数据，记得备份。

def numIslands(self, grid: List[List[str]]) -> int:
    if not grid or not grid[0]:
        return 0
    count = 0
    m, n = len(grid), len(grid[0])
  
    def DFS(i, j):
        grid[i][j] = '0'
        for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
            x, y = i+dx, j+dy
            if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':
                DFS(x, y)
  
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                count += 1
                DFS(i, j)
  
    return count

---

并查集

并查集是另外一种解法，其难点在于构建并查集本身。

并查集介绍

并查集(union & find)：是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。
有两个必须要实现的方法：

• Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
• Union：将两个子集合并成同一个集合。

并查集实现起来并不困难，伪代码如下：

function MakeSet(x)
    x. parent:=x
 
function Find(x)
    if x. parent==x 
        return x 
    else 
        return Find(x. parent)
 
function Union(x,y)
    xRoot:=Find(x)
    yRoot:=Find(y)
    xRoot. parent:=yRoot

其中：
集合的根结点（就是俗称的顶头上司），是自己指向自己的。
普通结点指向自己的上级。指向问题很重要。

下图就是用并查集表示的两个集合。

并查集的优化

并查集有两种优化方法：

1. 按 rank（等级、级别）优化：在合并时优化。
   rank 就相当于二叉树的深度，我们都希望深度尽可能少，以便查询时能尽快找到自己的根进行判定。
   合并时，rank 小的往 rank 大的上面合并。

2. 路径压缩：在查找时进行的优化。
   同样可以减少 rank 的值，减少层级关系，以提高效率。

---

解法二、并查集

使用优化后的并查集进行岛屿判定。

实现并查集的代码：

# 并查集
class UnionFind:
    def __init__(self, grid):
        m, n = len(grid), len(grid[0])
        self.count = 0
        self.parent = [-1] * (m * n)
        self.rank = [0] * (m * n)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    self.parent[i * n + j] = i * n + j  # 降维：二维数组映射到一维数组上
                    self.count += 1
 
    # 查找时路径压缩
    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])  # 以保证所有结点都指向根节点。
        return self.parent[i]
 
    # 按 rank 合并
    def union(self, x, y):
        rootx = self.find(x)
        rooty = self.find(y)
        if rootx != rooty:
            if self.rank[rootx] < self.rank[rooty]:
                self.parent[rootx] = rooty
            elif self.rank[rootx] > self.rank[rooty]:
                self.parent[rooty] = rootx
            else:
                self.parent[rooty] = rootx
                self.rank[rootx] += 1
            self.count -= 1

解释：

• parent 表示自己的父节点（上级），在初始化的时候就要确定。Python 可以使用 list 表示。
• rank 一般的初始值都是为 0 的 list，表示尚未合并过结点。
• count 用于统计集合的数量，随着合并加多，数值随之减小。
• find() 和 union() 是进行优化后代码，所有的并查集问题都可以直接用。
  find() 方法中自己调用了自己。合并集合时都是合并在根结点上的，根据情况，选择是否要更新 rank，而 count 是肯定要减少的。另外要注意 if 的判定条件。

主体代码：

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid or not grid[0]:
            return 0
        uf = UnionFind(grid)
        m, n = len(grid), len(grid[0])
 
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':  # 不染色也可以解决该问题。
                    grid[i][j] = '0'  # 染色能够减少以后的大量 union 判断。以保证合并的都是没有出现的数据。
                    for x, y in [[i+1, j], [i-1, j], [i, j+1], [i, j-1]]:
                        if 0 <= x < m and 0 <= y < n and grid[x][y] == '1':
                            uf.union(i*n+j, x*n+y)
  
        return uf.count

注意：

• 在解决并查集问题时，有时并不需要 count 统计集合数量。
• 平时在做题的时候，并查集的两种优化方法：查找时路径压缩、按 rank 合并，只需保留一种方法即可。
  我个人建议保留路径压缩这种方法，这样连 rank 都不需要定义了。这里代码没有给出，大家可以自己尝试一下。

希望对你能有帮助。

若看懂了，不妨尝试一下下面两道题：
990. 等式方程的可满足性
547. 朋友圈

本文地址：https://blog.csdn.net/weixin_43932942/article/details/107643320