本文主要是介绍LeetCode in Python 200. Number of islands (岛屿数量)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
岛屿数量既可以用深度优先搜索也可以用广度优先搜索解决，本文给出两种方法的代码实现。
示例：
图1 岛屿数量输入输出示意图
方法一：广度优先搜索(bfs)
代码：
class Solution:def numIslands(self, grid):if not grid:return 0rows, cols = len(grid), len(grid[0])visit = set()islands = 0def bfs(r, c):que = deque()que.append((r, c))visit.add((r, c))while que:row, col = que.popleft()directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]for dr, dc in directions:r, c = row + dr, col + dcif r in range(rows) and c in range(cols) and grid[r][c] == "1" and (r, c) not in visit:que.append((r, c))visit.add((r, c))for r in range(rows):for c in range(cols):if grid[r][c] == "1" and (r, c) not in visit:bfs(r, c)islands += 1return islands解释：
1）visit记录所有已经遍历的位置集合，如果该位置值为1且还未遍历到，则对该位置进行bfs，并增加一块岛屿数量。bfs中设置了一个队列que用于记录需要遍历的节点，directions为每个节点需要遍历的四个方向，分别对应右、左、上、下。对每个位置进行判断，如果该位置未越界、值为1且未被遍历到，则将该结点加入即将需要遍历的节点队列中，并将其放入已经遍历的节点集合中。
方法二：深度优先搜索(dfs)
代码：
class Solution:def numIslands(self, grid):if not grid:return 0 rows, cols = len(grid), len(grid[0])islands = 0def dfs(r, c):if r not in range(rows) or c not in range(cols) or grid[r][c] == "0":returngrid[r][c] = "0"dfs(r + 1, c)dfs(r - 1, c)dfs(r, c + 1)dfs(r, c - 1)for r in range(rows):for c in range(cols):if grid[r][c] == "1":dfs(r, c)islands += 1return islands解释：
1）深度优先搜索相较于广度优先搜索，选择将遍历过的节点的值置为“0”以免重复遍历，同时dfs采用递归方法来实现对四个位置上节点的判断。
这篇关于LeetCode in Python 200. Number of islands (岛屿数量)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
