岛屿数量

本文详细解析 LeetCode 200 题“岛屿数量”，提供 DFS、BFS 两种解法，并附有 Python 代码实现，适合算法学习者参考。

图 DFS BFS Leetcode Python

阅读要点

DFS 解法：递归遍历岛屿并标记为水
BFS 解法：使用队列遍历岛屿
时间复杂度与空间复杂度分析
Python 代码实现

题目

200. 岛屿数量 - 力扣（LeetCode）

解法一：DFS（深度优先搜索）

采用 DFS 深度遍历每一个岛屿，并将水淹没这个岛屿。

时间复杂度：O(M×N)，其中 M 和 N 分别为网格的行数和列数。

空间复杂度：O(M×N)，最坏情况下递归栈深度为 M×N。

答案

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        self.ni = len(grid)
        self.nj = len(grid[0])
        def dfs(i, j):
            if grid[i][j] == "0":
                return 
            grid[i][j] = "0"
            if i + 1 < self.ni:
                dfs(i+1, j)
            if j + 1 < self.nj:
                dfs(i, j+1)
            if i - 1 >= 0:
                dfs(i-1, j)
            if j - 1 >= 0:
                dfs(i, j-1)
            
        res = 0
        for i in range(self.ni):
            for j in range(self.nj):
                if grid[i][j] == "1":
                    res += 1
                    dfs(i, j)
        return res

解法二：BFS（广度优先搜索）

同上，换成 BFS。

时间复杂度：O(M×N)

空间复杂度：O(min(M,N))，队列中最多存储一层节点。

答案

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        self.ni = len(grid)
        self.nj = len(grid[0])
 
        def bfs(x, y):
            q = []
            q.append((x, y))
            while q:
                i, j = q.pop()
                grid[i][j] = "0"
                if i + 1 < self.ni and grid[i+1][j] == "1":
                    q.append((i+1, j))
                if j + 1 < self.nj and grid[i][j+1] == "1":
                    q.append((i, j+1))
                if i - 1 >= 0 and grid[i-1][j] == "1":
                    q.append((i-1, j))
                if j - 1 >= 0 and grid[i][j-1] == "1":
                    q.append((i, j-1))
 
        res = 0
        for i in range(self.ni):
            for j in range(self.nj):
                if grid[i][j] == "1":
                    res += 1
                    bfs(i, j)
        return res

解法三：并查集（待补充）

使用并查集，还没做出来。