0Pricing
Coding Interview Prep · Lección

DFS: componentes conexos y flood fill

Aplique DFS para contar componentes conexos, resuelva number-of-islands en una cuadrícula 2D e implemente flood fill para el procesamiento de imágenes.

DFS: componentes conexos y flood fill es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.

Definición de componentes conexos

Un componente conexo de un grafo no dirigido es un conjunto maximal de vértices tal que existe un camino entre cada par de vértices del conjunto. Un mismo grafo puede tener varios componentes desconectados. Encontrar componentes conexos es la base de muchos problemas de grafos: agrupación, combinación, conteo de islas y consolidación de cuentas se reducen a esta operación 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}')

Contar componentes conexos con DFS

Recorra todos los nodos. Para cada nodo no visitado, inicie un DFS que marque como visitados todos los nodos alcanzables. Cada inicio de DFS corresponde al descubrimiento de un componente nuevo. Cuente el número de inicios de DFS para obtener el número de componentes. Este algoritmo O(V + E) funciona correctamente tanto si el grafo es conexo como si no lo es.

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

Number of Islands

Number of Islands (LeetCode #200) es el problema canónico de componentes conexos en una cuadrícula bidimensional. Cada celda «1» pertenece a una isla; las celdas «1» adyacentes (arriba/abajo/izquierda/derecha) forman la misma isla. Cuente el número de islas distintas mediante DFS: recorra todas las celdas y, cuando encuentre una celda «1» no visitada, inicie un DFS que marque todas las celdas «1» conectadas (relleno por inundación) y, después, incremente el contador.

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

Algoritmo de relleno por inundación

Flood Fill (LeetCode #733) reemplaza todas las celdas conectadas de un color inicial por un color nuevo, exactamente como la herramienta de cubo de pintura de los editores de imágenes. Utilice DFS: partiendo del píxel de origen, cambie recursivamente el color de todos los vecinos que coincidan con el color original. El caso límite clave es el siguiente: si el color de la celda inicial ya coincide con el nuevo color, devuelva el resultado inmediatamente para evitar una recursión 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 una isla

Área máxima de una isla (LeetCode #695) amplía el conteo de islas: para cada isla, debe devolver el tamaño de la más grande. Durante el recorrido DFS de inundación, cuente las celdas que marque. El DFS devuelve el tamaño de la isla actual, y usted realiza un seguimiento del máximo entre todas las islas. Esta es una ampliación sencilla del patrón de componentes conexos.

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

Flujo de agua del Pacífico al Atlántico

Flujo de agua del Pacífico al Atlántico (LeetCode #417) pregunta qué celdas pueden conducir agua tanto al océano Pacífico (bordes superior e izquierdo) como al Atlántico (bordes inferior y derecho). En lugar de simular el flujo del agua cuesta abajo, use DFS inverso: haga que el agua fluya hacia arriba desde los océanos. Realice dos recorridos DFS: uno desde los bordes del Pacífico y otro desde los bordes del Atlántico, recopilando las celdas alcanzables. La intersección es la respuesta.

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 iterativo para componentes conexos

Use DFS iterativo (con una pila explícita) para evitar el límite de recursión de Python en cuadrículas grandes. La versión iterativa es equivalente al DFS recursivo, pero utiliza una pila en lugar de la pila de llamadas. Inserte el nodo inicial, después extráigalo, márquelo como visitado e inserte sus vecinos no visitados. Esto permite procesar de forma segura cuadrículas de hasta millones de celdas, en las que el DFS recursivo provocaría un desbordamiento de pila.

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

Regiones rodeadas

Regiones rodeadas (LeetCode #130) captura todas las regiones de 'O' que están completamente rodeadas por bordes de 'X'. Una región NO se captura si alguna de sus celdas 'O' toca el borde del tablero. El truco consiste en que, en lugar de buscar directamente las regiones rodeadas, debe realizar un DFS desde todas las celdas 'O' del borde y marcar como seguras todas las celdas alcanzables. Después, invierta los valores: todas las celdas 'O' restantes están rodeadas y se convierten en 'X', mientras que las celdas seguras se restauran a '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

Contar subislas

Contar subislas (LeetCode #1905) encuentra las islas de grid2 que están completamente contenidas dentro de una isla de grid1. Realice un DFS desde cada celda '1' de grid2: una isla es una subisla si cada celda que visita también es '1' en grid1. El truco consiste en visitar TODAS las celdas de la isla (para marcarlas como exploradas), pero hacer un seguimiento de si TODAS ellas también eran '1' en grid1. No interrumpa el recorrido al encontrar el primer '0' en grid1, ya que no marcaría las demás celdas de la misma isla.

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 frente a BFS para componentes conexos

Tanto DFS como BFS encuentran correctamente todos los componentes conexos, con la misma complejidad temporal O(V + E) y espacial O(V). El DFS es más sencillo de implementar de forma recursiva para problemas de componentes conexos, mientras que se prefiere BFS cuando también necesita información sobre las rutas más cortas. En problemas de cuadrículas, el DFS aprovecha mejor la caché porque explora en profundidad una dirección antes de retroceder, accediendo secuencialmente a ubicaciones de memoria cercanas.

# 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')

Islas con restricciones: formas y perímetros

Perímetro de una isla (LeetCode #463) cuenta el perímetro total de la única isla de una cuadrícula. Para cada celda de tierra ('1'), sume 4 al perímetro y después reste 2 por cada celda de tierra adyacente (por los lados compartidos). Este enfoque basado en una fórmula O(mn) no requiere DFS, pero comprender que equivale a un DFS que cuenta los bordes de la frontera refuerza la conexión entre los problemas de cuadrículas y el razonamiento 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))  # 16

Comprobación rápida

Compruebe su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.

Repaso de la lección

En esta lección ha aprendido: componentes conexos mediante DFS con seguimiento de visitados, número de islas y flood fill como aplicaciones canónicas de cuadrículas 2D, y patrones avanzados como el DFS inverso desde los bordes (regiones rodeadas) y el DFS múltiple con seguimiento de restricciones (subislas). A continuación abordaremos la detección de ciclos en grafos dirigidos y no dirigidos.

Preguntas frecuentes

¿La lección «DFS: componentes conexos y flood fill» es gratis?

Sí — el texto completo de «DFS: componentes conexos y flood fill» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.

¿Qué aprenderé en «DFS: componentes conexos y flood fill»?

Aplique DFS para contar componentes conexos, resuelva number-of-islands en una cuadrícula 2D e implemente flood fill para el procesamiento de imágenes. Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.

¿Necesito experiencia previa para empezar Coding Interview Prep?

No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.

¿Cuánto tiempo toma la lección «DFS: componentes conexos y flood fill»?

La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.

¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?

Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.

Todas las lecciones de este curso

  1. Representaciones de grafos y preparación de recorridos
  2. BFS: ruta más corta y recorrido por niveles
  3. DFS: componentes conexos y flood fill
  4. Detección de ciclos en grafos dirigidos y no dirigidos
← Volver a Coding Interview Prep