Búsqueda en profundidad (DFS) explicada: cómo funciona, código y complejidad

Qué problema resuelve DFS

DFS responde a la pregunta "¿qué puedo alcanzar desde aquí?" explorando una rama por completo antes de probar la siguiente. Ese orden es útil cuando importa más la estructura de los caminos que su longitud: encontrar la salida de un laberinto, comprobar si un grafo tiene un ciclo, ordenar tareas que dependen unas de otras o listar todas las soluciones de un rompecabezas.

A diferencia de la búsqueda en anchura, DFS no encuentra caminos más cortos. Su fortaleza es que solo guarda en memoria el camino actual y que registra de forma natural cuándo se entra en un nodo y cuándo se termina con él.

La idea en palabras sencillas

1. Marca el nodo actual como visitado.
2. Para cada vecino que no esté visitado, pasa a él y repite el paso 1 desde ahí.
3. Cuando un nodo ya no tiene vecinos sin visitar, está terminado: vuelve al nodo del que vienes.
4. Cuando regresas al nodo inicial y ya no tiene vecinos sin visitar, la búsqueda ha terminado.

Volver al nodo anterior se llama retroceso (backtracking). Con recursión, la pila de llamadas lo hace por ti.

Ejemplo resuelto, paso a paso

Usa el mismo grafo no dirigido del artículo de BFS: A–B, A–C, B–D, C–D, C–E, D–F. Empieza en A y prueba los vecinos en orden alfabético.

El orden de visita es A, B, D, C, E, F. El orden de finalización es E, C, F, D, B, A. El orden de finalización es el que usan la ordenación topológica y los algoritmos de componentes fuertemente conexas.

Implementación en Python

La versión recursiva es la más corta y la más cercana a la idea:

def dfs(graph, node, visited=None):
    if visited is None:
        visited = []
    visited.append(node)
    for nxt in graph[node]:
        if nxt not in visited:
            dfs(graph, nxt, visited)
    return visited
graph = {
    "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
    "D": ["B", "C", "F"], "E": ["C"], "F": ["D"],
}
print(dfs(graph, "A"))  # ['A', 'B', 'D', 'C', 'E', 'F']

Una lista mantiene el ejemplo legible, pero hace que in sea una comprobación O(n). Para grafos grandes, usa un set aparte para la pertenencia. La versión iterativa usa una pila explícita y evita el límite de recursión de Python. Los vecinos se apilan en orden inverso para que salgan en el orden original:

def dfs_iterative(graph, start):
    visited, order = set(), []
    stack = [start]
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for nxt in reversed(graph[node]):
            if nxt not in visited:
                stack.append(nxt)
    return order
print(dfs_iterative(graph, "A"))  # ['A', 'B', 'D', 'C', 'E', 'F']

Fíjate en la diferencia con BFS: aquí un nodo se marca cuando se extrae de la pila, así que puede estar en ella más de una vez. Eso es correcto para DFS y conserva el verdadero orden en profundidad.

Detectar un ciclo en un grafo dirigido

Una aplicación clásica de DFS colorea cada nodo: blanco (no visto), gris (en el camino actual) y negro (terminado). Llegar a un nodo gris significa que hay una arista de vuelta al camino actual, es decir, un ciclo.

def has_cycle(graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = {node: WHITE for node in graph}
    def visit(node):
        color[node] = GRAY
        for nxt in graph[node]:
            if color[nxt] == GRAY:
                return True              # back edge
            if color[nxt] == WHITE and visit(nxt):
                return True
        color[node] = BLACK
        return False
    return any(color[n] == WHITE and visit(n) for n in graph)
print(has_cycle({"a": ["b"], "b": ["c"], "c": ["a"]}))  # True
print(has_cycle({"a": ["b"], "b": ["c"], "c": []}))     # False

Complejidad temporal y espacial

Variantes y errores comunes

• Preorden y postorden: registra un nodo al entrar en él (preorden) o al terminar con él (postorden). El postorden inverso de un grafo acíclico dirigido es un orden topológico.
• Componentes conexas: inicia un nuevo DFS desde cada nodo que siga sin visitar; cada inicio es una componente.
• DFS con profundización iterativa: ejecuta DFS con un límite de profundidad 0, 1, 2, … Encuentra caminos más cortos como BFS con la poca memoria de DFS.
• El relleno por inundación en una cuadrícula (la herramienta cubo de pintura) es un DFS o BFS sobre celdas vecinas del mismo color.

Otros errores frecuentes: olvidar el conjunto de visitados (bucle infinito ante cualquier ciclo), usar un argumento por defecto mutable como visited=[] (se comparte entre llamadas) y tratar como ciclo una arista no dirigida de vuelta al padre.

Cuándo usar DFS y usos en el mundo real

• Usa DFS para alcanzabilidad, detección de ciclos, ordenación topológica, componentes conexas y fuertemente conexas, puentes y puntos de articulación, y para la búsqueda exhaustiva con backtracking.
• Usa BFS en su lugar cuando necesites el menor número de pasos, y Dijkstra o A* cuando las aristas tengan pesos.
• Problemas de entrevista: número de islas, clonar un grafo, horario de cursos (detección de ciclos), suma de camino en un árbol binario, generación de permutaciones.
• En el mundo real: sistemas de compilación y gestores de paquetes que resuelven el orden de dependencias, compiladores que analizan el flujo de control, generación de laberintos y recorridos de árboles en sistemas de archivos o documentos HTML.