广度优先搜索（BFS）实现思路
- 实现思路：
- BFS从一个起始点开始，逐层向外扩展：先访问距离起始点最近的节点，再访问更远的节点。
- 图的遍历中，通常用队列
deque实现广度优先搜索BFS。
- 一般模板：
# 调用deque
from collections import deque
def bfs(start_node, graph):visited = set()queue = deque([start_node])while queue:node = queue.popleft()if node in visited:continuevisited.add(node)# 处理当前节点process_node(node)for neighbor in graph[node]:if neighbor not in visited:queue.append(neighbor)
from collections import dequeclass Solution:def numIslands(self, grid):# 空网格gridif not grid: return 0# 后续需要的参数rows = len(grid)cols = len(grid[0])count = 0# 向右、向左、向下、向上directions = [(1, 0), (-1, 0), (0, -1), (0, 1)]# 双层嵌套遍历所有grid所有元素for row in range(rows):for col in range(cols):if grid[row][col] == '1': # 当前是岛屿count += 1 # 计数queue = deque([(row, col)]) # 标记，添加当前坐标到队列中while queue: # 如果当前队列不为空，进入一个循环r, c = queue.popleft() # 左边元素pop，从队列取出一个位置if grid[r][c] != '1': # 如果当前位置不是陆地continue # 跳过这个位置grid[r][c] = '#' # 当前位置是陆地，标记上'#'# 遍历四个方向，对于每个方向，计算新的位置(new_r, new_c)for dr, dc in directions:new_r = r + drnew_c = c + dc# 如果新位置在网格grid范围内,且是陆地if 0 <= new_r < rows and 0 <= new_c < cols and grid[new_r][new_c] == '1':# 则将该方向的新位置也加入队列，实现广度优先搜索算法queue.append((new_r, new_c))return count以下是对上述代码涉及知识点的详细总结：
一、广度优先搜索（BFS）知识点
-
实现思路：
- BFS 从一个起始点开始，逐层向外扩展，先访问距离起始点最近的节点，再访问更远的节点。这是一种类似于“水波扩散”的方式，以固定的距离层次逐步探索图中的节点。
- 在图的遍历中，通常使用队列来实现 BFS。这是因为队列具有“先进先出”的特性，非常适合模拟 BFS 的逐层扩展过程。
-
队列在 BFS 中的作用：
- 初始化时，将起始节点加入队列，代表从这个节点开始进行搜索。
- 在每次循环中，从队列中取出一个节点进行处理。这个节点是当前层中最早被加入队列的节点，保证了先处理距离起始点近的节点。
- 处理当前节点时，将其未访问过的相邻节点加入队列，这些节点将在后续的循环中被处理，从而实现了逐层向外扩展的搜索过程。
-
队列相关语法知识（以 Python 为例）：
from collections import deque：导入 Python 中的deque模块，它实现了双端队列，可以高效地在两端进行添加和删除操作。queue = deque([start_node])：创建一个双端队列，并将起始节点放入队列中。这里使用列表[start_node]作为参数初始化队列，是因为deque可以接受一个可迭代对象作为初始值。queue.popleft()：从队列的左端取出一个元素。这是队列在 BFS 中的关键操作，保证了先处理先加入队列的节点。queue.append(element)：将一个元素添加到队列的右端。在 BFS 中，当处理一个节点时，将其未访问过的相邻节点加入队列，以便后续进行处理。
-
BFS 的实现过程：
- 首先，初始化一个空的集合
visited用于记录已访问过的节点，避免重复访问。创建一个队列，并将起始节点加入队列。 - 进入一个循环，只要队列不为空，就从队列中取出一个节点进行处理。如果该节点已经被访问过，则跳过；否则，将其标记为已访问，并对其进行具体的处理操作（在本题中是判断是否为陆地，如果是陆地则计数并标记为已访问）。
- 然后，遍历当前节点的相邻节点。如果相邻节点未被访问过且满足特定条件（在本题中是在网格范围内且为陆地），则将其加入队列，以便在后续的循环中进行处理。
- 重复这个过程，直到队列为空，此时所有可达节点都已被访问过。
- 首先，初始化一个空的集合
二、结合本题的分析
-
问题解决思路：
- 本题要求计算由’1’（陆地）和’0’（水）组成的二维网格中的岛屿数量。岛屿是由相邻的陆地组成的区域，水平或垂直方向上相邻的陆地被视为同一岛屿。
- 使用 BFS 的思路是，当遇到一个陆地时，从这个陆地开始进行广度优先搜索，将与其相连的所有陆地都标记为已访问，这样就找到了一个岛屿。然后继续遍历网格，寻找下一个未被访问的陆地，重复这个过程，直到遍历完整个网格。
-
代码分析：
- 首先判断特殊情况，如果输入的网格为空，则岛屿数量为 0。
- 然后获取网格的行数和列数，初始化岛屿数量计数器
count为 0。 - 定义四个方向的偏移量
directions，用于在遍历网格时快速计算相邻位置。 - 使用两层嵌套的循环遍历整个二维网格，当遇到一个值为’1’的位置时，说明找到了一个新的陆地，岛屿数量加 1，并将该位置加入队列。
- 进入一个循环，从队列中取出位置进行处理。如果当前位置不是陆地，则跳过；如果是陆地，将其标记为已访问。然后遍历四个方向，对于每个方向，计算新的位置。如果新位置在网格范围内且是陆地，则将其加入队列，实现广度优先搜索，将整个岛屿的陆地都标记为已访问。
- 循环结束后，继续遍历网格，寻找下一个未被访问的陆地，重复上述过程。最后返回岛屿的数量
count。
