岛屿数量（经典 DFS 和 BFS 高频题 商汤、字节面试题）

1. 题目描述

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

输入:

[ ['1','1','1','1','0'], ['1','1','0','1','0'], ['1','1','0','0','0'], ['0','0','0','0','0'] ] 输出: 1 示例 2: 

输入: [ ['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ] 输出: 3 解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。 

2. 解题思路 & 代码

2.1. DFS 深度优先遍历

递归转化为迭代的话可以用栈，后进先出

1. 我们可以将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。
2. 为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。
3. 在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0，这样可以避免两个 for 循环重复搜索。

最终岛屿的数量就是我们进行深度优先搜索的次数。

# 在开头加上 # import sys # python 默认递归深度不超过1000，做dfs会比C吃亏 # sys.setrecursionlimit(10000000)# 手动修改深度 class Solution: def dfs(self, grid, r, c): grid[r][c] = '0' # 每次某个岛屿计数以后，把该岛屿所有 1 都归 0，这样两个 for 循环 就不会重复遍历了 nr = len(grid) nc = len(grid[0]) for new_r, new_c in [[r-1,c],[r+1,c],[r, c-1],[r, c+1]]: if 0 <= new_r < nr and 0 <= new_c <nc and grid[new_r][new_c] == '1': self.dfs(grid, new_r, new_c) def numIslands(self, grid: List[List[str]]) -> int: nr = len(grid) # 行数 if nr == 0: return 0 nc = len(grid[0]) # 列数 num_land = 0 for r in range(nr): for c in range(nc): if grid[r][c] == '1': num_land += 1 self.dfs(grid, r, c) return num_land 

复杂度分析

时间复杂度：$O(MN)$，其中 $M$ 和 $N$ 分别为行数和列数。

空间复杂度：$O(MN)$，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 $MN$。

2.2. BFS 广度优先遍历

广度优先用队列，先进先出

同样地，我们也可以使用广度优先搜索代替深度优先搜索。

1. 为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则将其加入队列，开始进行广度优先搜索。
2. 在广度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。直到队列为空，搜索结束。
3. 最终岛屿的数量就是我们进行广度优先搜索的次数。

class Solution: def numIslands(self, grid: List[List[str]]) -> int: nr = len(grid) if nr == 0: return 0 nc = len(grid[0]) num_land = 0 queue = [] # 队列，可用列表表示 for r in range(nr): for c in range(nc): if grid[r][c] == '1': num_land += 1 queue.append([r, c]) # 入队 # grid[r][c] = '0'    # 这里标记已访问可有可无 while queue: row, col = queue.pop(0) #左边出队（先进先出） for i, j in [[row-1, col],[row+1, col],[row, col-1],[row, col+1]]: if 0 <= i < nr and 0 <= j < nc and grid[i][j] == '1': queue.append([i, j]) # 入队 grid[i][j] = '0' # 放入队列以后马上标记为已访问，即置零 return num_land 

复杂度分析

时间复杂度：$O(MN)$，其中 $M$ 和 $N$ 分别为行数和列数。

空间复杂度：$O(min(M,N))$，在最坏情况下，整个网格均为陆地，队列的大小可以达到 $min(M,N)$。

本文地址：https://blog.csdn.net/weixin_41888257/article/details/107128917