DFS：连通分量与洪水填充
应用 DFS 统计连通分量，解决二维网格中的岛屿数量问题，并实现用于图像处理的洪水填充。
DFS：连通分量与洪水填充 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
连通分量的定义
无向图中的连通分量是一个极大的顶点集合，使得集合中的每一对顶点之间都存在一条路径。一个图可以包含多个互不连通的分量。查找连通分量是许多图问题的基础：分组、合并、统计岛屿数量和账户合并等问题最终都可以归结为这一基本操作。
from collections import defaultdict
# Graph with 3 components: {0,1,2}, {3,4}, {5}
graph = defaultdict(list)
for u, v in [(0,1),(0,2),(1,2),(3,4)]:
graph[u].append(v)
graph[v].append(u)
# Node 5 is isolated (no edges)
for node in [0,1,2,3,4,5]:
if node not in graph:
graph[node] = []
# We need DFS or BFS from each unvisited node
# to discover all components
print('Graph has nodes 0-5 with components: {0,1,2}, {3,4}, {5}')使用 DFS 统计连通分量
遍历所有节点。对于每个未访问节点，启动一次 DFS，将所有可达节点标记为已访问。每次启动 DFS 都表示发现了一个新的分量。统计启动 DFS 的次数，即可得到分量数量。无论图是否连通，这个 O(V + E) 算法都能正确工作。
from collections import defaultdict
def count_components(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
count = 0
def dfs(node):
visited.add(node)
for nb in graph[node]:
if nb not in visited:
dfs(nb)
for node in range(n):
if node not in visited:
dfs(node)
count += 1
return count
print(count_components(6, [(0,1),(0,2),(1,2),(3,4)])) # 3
print(count_components(5, [(0,1),(1,2),(3,4)])) # 2岛屿数量
岛屿数量（LeetCode #200）是二维网格上连通分量问题的典型代表。每个“1”单元格都属于某个岛屿；上下左右相邻的“1”单元格属于同一个岛屿。请使用 DFS 统计不同岛屿的数量：遍历所有单元格，当发现一个未访问的“1”时，启动 DFS，将所有相连的“1”单元格标记为已访问（泛洪填充），然后将计数加一。
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if grid[r][c] != '1':
return
grid[r][c] = '#' # mark visited in-place
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)
count += 1
return count
grid = [['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']]
print(num_islands(grid)) # 3泛洪填充算法
泛洪填充（LeetCode #733）会将从指定起始位置开始的所有相连单元格从原颜色替换为新颜色——这与图像编辑器中的油漆桶工具完全一样。请使用 DFS：从源像素开始，递归地为所有与原颜色匹配的邻居重新着色。关键的边界情况是：如果起始单元格的颜色已经等于新颜色，应立即返回，以避免无限递归。
def flood_fill(image, sr, sc, new_color):
original = image[sr][sc]
if original == new_color:
return image # edge case: same color, nothing to do
rows, cols = len(image), len(image[0])
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if image[r][c] != original:
return
image[r][c] = new_color
dfs(r+1,c); dfs(r-1,c)
dfs(r,c+1); dfs(r,c-1)
dfs(sr, sc)
return image
image = [[1,1,1],[1,1,0],[1,0,1]]
result = flood_fill(image, 1, 1, 2)
for row in result: print(row)
# [[2,2,2],[2,2,0],[2,0,1]]岛屿的最大面积
岛屿的最大面积（LeetCode #695）扩展了岛屿计数问题：对于每个岛屿，返回其中最大的岛屿面积。在 DFS 泛洪填充过程中，统计标记的单元格数量。DFS 返回当前岛屿的大小，然后在所有岛屿中记录最大值。这是对连通分量模式的一种简单扩展。
def max_area_of_island(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
max_area = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return 0
if grid[r][c] != 1:
return 0
grid[r][c] = 0 # mark visited
return (1 + 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:
max_area = max(max_area, dfs(r, c))
return max_area
grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0]]
print(max_area_of_island(grid)) # 6太平洋和大西洋水流
太平洋和大西洋水流（LeetCode #417）要求找出哪些单元格中的水可以同时流向太平洋（上边缘/左边缘）和大西洋（下边缘/右边缘）。不要模拟水向下流，而应使用反向 DFS：让水从海洋向上流。执行两次 DFS 遍历——一次从太平洋边界开始，另一次从大西洋边界开始——收集所有可到达的单元格。两者的交集就是答案。
def pacific_atlantic(heights):
rows, cols = len(heights), len(heights[0])
pac = set(); atl = set()
def dfs(r, c, visited, prev_h):
if (r,c) in visited or r < 0 or r >= rows or c < 0 or c >= cols:
return
if heights[r][c] < prev_h:
return # water can't flow uphill in reverse
visited.add((r,c))
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
dfs(r+dr, c+dc, visited, heights[r][c])
for r in range(rows):
dfs(r, 0, pac, heights[r][0]) # Pacific left
dfs(r, cols-1, atl, heights[r][cols-1]) # Atlantic right
for c in range(cols):
dfs(0, c, pac, heights[0][c]) # Pacific top
dfs(rows-1, c, atl, heights[rows-1][c]) # Atlantic bottom
return sorted(pac & atl) # intersection
print(pacific_atlantic([[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]))连通分量的迭代式 DFS
使用迭代式 DFS（配合显式栈），避免在大型网格上触及 Python 的递归限制。迭代版本与递归式 DFS 等价，但使用栈而不是调用栈。先将起始节点压入栈中，然后弹出节点、标记为已访问，并将未访问的邻居压入栈中。在递归式 DFS 会导致栈溢出的情况下，这种方法也能安全处理多达数百万个单元格的网格。
def count_components_iterative(n, edges):
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
count = 0
for start in range(n):
if start in visited:
continue
# Iterative DFS
stack = [start]
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
for nb in graph[node]:
if nb not in visited:
stack.append(nb)
count += 1
return count
print(count_components_iterative(6, [(0,1),(0,2),(1,2),(3,4)])) # 3被围绕的区域
被围绕的区域（LeetCode #130）要求找出所有完全被 'X' 边界包围的 'O' 区域。如果某个区域中的任何 'O' 单元格接触到棋盘边缘，则该区域NOT会被捕获。关键思路是：不要直接查找被围绕的区域，而是从所有边界上的 'O' 单元格执行 DFS，并将所有可到达的单元格标记为安全。然后进行翻转：所有剩余的 'O' 单元格都被围绕，应变为 'X'；安全单元格则恢复为 'O'。
def solve(board):
if not board:
return
rows, cols = len(board), len(board[0])
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
if board[r][c] != 'O':
return
board[r][c] = 'S' # safe: connected to border
dfs(r+1,c); dfs(r-1,c)
dfs(r,c+1); dfs(r,c-1)
# Mark border-connected O's as safe
for r in range(rows):
dfs(r, 0); dfs(r, cols-1)
for c in range(cols):
dfs(0, c); dfs(rows-1, c)
# Flip: surrounded O -> X, safe S -> O
for r in range(rows):
for c in range(cols):
if board[r][c] == 'O': board[r][c] = 'X'
elif board[r][c] == 'S': board[r][c] = 'O'
board = [['X','X','X','X'],['X','O','O','X'],
['X','X','O','X'],['X','O','X','X']]
solve(board)
print([board[1][1], board[3][1]]) # X, O统计子岛屿
统计子岛屿（LeetCode #1905）用于找出第二个网格中完全包含在第一个网格某个岛屿内的岛屿。从第二个网格中的每个 '1' 单元格执行 DFS：只有当访问到的每个单元格在第一个网格中也都是 '1' 时，该岛屿才是子岛屿。关键是：要访问该岛屿的所有单元格（将它们标记为已探索），同时记录它们是否全部也是第一个网格中的 '1'。不要在第一个网格中首次遇到 '0' 时就提前结束，否则会漏掉同一岛屿中的其他单元格。
def count_sub_islands(grid1, grid2):
rows, cols = len(grid2), len(grid2[0])
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols:
return True
if grid2[r][c] != 1:
return True
grid2[r][c] = 0 # mark visited
is_sub = grid1[r][c] == 1 # this cell must be in grid1
is_sub = dfs(r+1,c) and is_sub # note: AND not short-circuit OR
is_sub = dfs(r-1,c) and is_sub
is_sub = dfs(r,c+1) and is_sub
is_sub = dfs(r,c-1) and is_sub
return is_sub
count = 0
for r in range(rows):
for c in range(cols):
if grid2[r][c] == 1 and dfs(r, c):
count += 1
return count
print(count_sub_islands([[1,1,1],[1,0,1],[1,1,1]],
[[1,1,1],[1,0,1],[1,1,1]])) # 1连通分量中的 DFS 与 BFS 对比
DFS 和 BFS 都能正确找出所有连通分量，并且时间复杂度都是 O(V + E)，空间复杂度都是 O(V)。对于连通分量问题，DFS 更适合用递归实现；而当您还需要最短路径信息时，通常优先选择 BFS。在网格问题中，DFS 的缓存友好性更好，因为它会先沿一个方向深入，再回溯，从而按顺序访问相邻的内存位置。
# DFS advantages for connected components:
# - Simpler recursive implementation
# - Lower constant factor for small graphs
# - Can restore grid state during backtracking (if needed)
# BFS advantages:
# - Finds shortest path while traversing
# - Better for wide, shallow graphs (avoids deep recursion)
# - Multi-source initialisation is natural
# Same asymptotic complexity: O(V + E) time, O(V) space
# Grid (m rows, n cols): O(mn) time and space
print('DFS and BFS: same O(V+E) complexity for component counting')带约束的岛屿：形状与周长
岛屿周长（LeetCode #463）用于计算网格中唯一岛屿的总周长。对于每个陆地单元格（'1'），先将周长加 4；然后，对于每个相邻的陆地单元格（共享边），减去 2。这种基于公式、复杂度为 O(mn) 的方法不需要 DFS，但理解它等价于通过 DFS 统计边界边，有助于强化网格问题与图推理之间的联系。
def island_perimeter(grid):
rows, cols = len(grid), len(grid[0])
perimeter = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
perimeter += 4 # start with 4 sides
# Subtract shared edges with adjacent land cells
if r > 0 and grid[r-1][c] == 1:
perimeter -= 2 # shared top edge
if c > 0 and grid[r][c-1] == 1:
perimeter -= 2 # shared left edge
return perimeter
grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
print(island_perimeter(grid)) # 16快速检查
测试您对本课中“数据结构与算法 — 编程面试准备”相关概念的理解。
课程回顾
本课中，您学习了：通过记录已访问节点，使用 DFS 查找连通分量；将岛屿数量和泛洪填充作为二维网格的经典应用；以及从边界反向执行 DFS（被围绕的区域）和带约束跟踪的多次 DFS（子岛屿）等高级模式。接下来，我们将学习有向图和无向图中的环检测。
常见问题解答
「DFS：连通分量与洪水填充」课时是免费的吗？
是的 — 「DFS：连通分量与洪水填充」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「DFS：连通分量与洪水填充」这节课中我会学到什么？
应用 DFS 统计连通分量，解决二维网格中的岛屿数量问题，并实现用于图像处理的洪水填充。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「DFS：连通分量与洪水填充」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 图的表示与遍历准备
- BFS：最短路径与层序遍历
- DFS：连通分量与洪水填充
- 有向图与无向图中的环检测