DFS: Componentes Conectados e Preenchimento por Inundação
Aplique DFS para contar componentes conectados, resolva number-of-islands em uma grade 2D e implemente flood fill para processamento de imagens.
DFS: Componentes Conectados e Preenchimento por Inundação é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
Definição de Componentes Conectados
Um componente conectado em um grafo não direcionado é um conjunto maximal de vértices tal que existe um caminho entre cada par de vértices do conjunto. Um único grafo pode ter vários componentes desconectados. Encontrar componentes conectados é a base de muitos problemas de grafos: agrupamento, fusão, contagem de ilhas e consolidação de contas podem ser reduzidos a essa operação fundamental.
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}')Contagem de Componentes Conectados com DFS
Percorra todos os nós. Para cada nó não visitado, inicie um DFS para marcar como visitados todos os nós alcançáveis. Cada início de DFS corresponde à descoberta de um novo componente. Conte o número de inícios de DFS para obter o número de componentes. Esse algoritmo O(V + E) funciona corretamente tanto em grafos conectados quanto em grafos desconectados.
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)])) # 2Número de Ilhas
Número de Ilhas (LeetCode #200) é o problema clássico de componentes conectados em uma grade 2D. Cada célula com '1' pertence a uma ilha; células com '1' adjacentes (acima/abaixo/esquerda/direita) formam a mesma ilha. Conte o número de ilhas distintas usando DFS: percorra todas as células e, ao encontrar um '1' não visitado, inicie um DFS que marque todas as células conectadas com '1' (preenchimento por inundação) e depois incremente a contagem.
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)) # 3Algoritmo de Preenchimento por Inundação
Preenchimento por Inundação (LeetCode #733) substitui todas as células conectadas de uma determinada cor inicial por uma nova cor — exatamente como a ferramenta de balde de tinta dos editores de imagens. Use DFS: começando pelo pixel de origem, recolora recursivamente todos os vizinhos que correspondem à cor original. O principal caso-limite é: se a cor da célula inicial já for igual à nova cor, retorne imediatamente para evitar uma recursão infinita.
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]]Área máxima de uma ilha
Área máxima de uma ilha (LeetCode #695) amplia a contagem de ilhas: para cada ilha, retorne o tamanho da maior. Durante o preenchimento por inundação com DFS, conte as células que você marca. A DFS retorna o tamanho da ilha atual, e você acompanha o máximo entre todas as ilhas. Esta é uma extensão simples do padrão de componentes conexas.
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)) # 6Fluxo de água do Pacífico ao Atlântico
Fluxo de água do Pacífico ao Atlântico (LeetCode #417) pergunta quais células podem escoar para os oceanos Pacífico (bordas superior/esquerda) e Atlântico (bordas inferior/direita). Em vez de simular a água escoando para baixo, use DFS reversa: faça a água escoar a partir dos oceanos. Realize duas varreduras de DFS — uma a partir das bordas do Pacífico e outra a partir das bordas do Atlântico — coletando as células alcançáveis. A interseção é a resposta.
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 iterativa para componentes conexas
Use DFS iterativa (com uma pilha explícita) para evitar o limite de recursão do Python em grades grandes. A versão iterativa é equivalente à DFS recursiva, mas usa uma pilha em vez da pilha de chamadas. Coloque o nó inicial na pilha; depois, retire um nó, marque-o como visitado e coloque na pilha os vizinhos não visitados. Isso lida com segurança com grades de até milhões de células, enquanto uma DFS recursiva causaria um estouro de pilha.
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)])) # 3Regiões cercadas
Regiões cercadas (LeetCode #130) identifica todas as regiões de 'O' completamente cercadas por bordas de 'X'. Uma região NÃO é capturada se alguma de suas células 'O' tocar a borda do tabuleiro. A estratégia é: em vez de encontrar diretamente as regiões cercadas, faça uma DFS a partir de todas as células 'O' das bordas e marque tudo o que for alcançável como seguro. Depois, inverta: todas as células 'O' restantes estão cercadas e se tornam 'X', enquanto as células seguras são restauradas para '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, OContar subilhas
Contar subilhas (LeetCode #1905) encontra as ilhas na grade2 que estão inteiramente contidas em uma ilha da grade1. Faça uma DFS a partir de cada célula '1' da grade2: uma ilha é uma subilha se todas as células visitadas também forem '1' na grade1. A estratégia é: visite ALL as células da ilha (para marcá-las como exploradas), mas acompanhe se ALL elas também eram '1' na grade1. Não interrompa na primeira ocorrência de '0' na grade1 — você deixaria de marcar outras células da mesma ilha.
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]])) # 1DFS versus BFS para componentes conexas
DFS e BFS encontram corretamente todas as componentes conexas, com a mesma complexidade de tempo O(V + E) e de espaço O(V). A DFS é mais simples de implementar recursivamente em problemas de componentes conexas, enquanto a BFS é preferível quando você também precisa de informações sobre caminhos mínimos. Em problemas com grades, a DFS favorece o uso da cache porque explora uma direção profundamente antes de retroceder, acessando sequencialmente locais próximos da memória.
# 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')Ilhas com restrições: formas e perímetros
Perímetro da ilha (LeetCode #463) conta o perímetro total da única ilha em uma grade. Para cada célula de terra ('1'), add 4 ao perímetro e depois subtraia 2 para cada célula de terra adjacente (arestas compartilhadas). Esta abordagem baseada em uma fórmula O(mn) não requer DFS — mas compreender que ela equivale a uma DFS que conta as arestas de fronteira reforça a conexão entre problemas com grades e o raciocínio sobre grafos.
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)) # 16Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para entrevistas de programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu: componentes conexas por meio de DFS com acompanhamento de visitados, número de ilhas e preenchimento por inundação como aplicações canônicas de grades bidimensionais e padrões avançados, como DFS reversa a partir das bordas (regiões cercadas) e múltiplas DFS com acompanhamento de restrições (subilhas). A seguir, abordaremos a detecção de ciclos em grafos direcionados e não direcionados.
Perguntas Frequentes
A aula “DFS: Componentes Conectados e Preenchimento por Inundação” é grátis?
Sim — o texto completo de “DFS: Componentes Conectados e Preenchimento por Inundação” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “DFS: Componentes Conectados e Preenchimento por Inundação”?
Aplique DFS para contar componentes conectados, resolva number-of-islands em uma grade 2D e implemente flood fill para processamento de imagens. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “DFS: Componentes Conectados e Preenchimento por Inundação”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Representações de Grafos e Configuração de Percursos
- BFS: Menor Caminho e Percurso por Níveis
- DFS: Componentes Conectados e Preenchimento por Inundação
- Detecção de Ciclos em Grafos Direcionados e Não Direcionados