Búsqueda en profundidad (DFS)

Lo que cubre este capítulo

La búsqueda en profundidad es el otro recorrido fundamental de grafos, y es la imagen espejo de BFS en el sentido más literal: toma el código en anchura del capítulo pasado, cambia la queue por un stack, y el "primero lo más cercano" se convierte en "primero lo más profundo". En lugar de expandirse hacia afuera en anillos, DFS se compromete con una rama y la sigue hasta donde llegue, regresando solo cuando choca con un callejón sin salida. Ese cambio le cuesta la garantía del camino más corto — pero le compra un conjunto distinto de poderes que BFS no puede igualar sin pagar caro. Como la recursión de DFS refleja la estructura del grafo, el orden en que los nodos terminan te da ordenamientos topológicos, una arista de regreso hacia un ancestro que sigue en el stack detecta un ciclo, y un DFS por componente los enumera. Este capítulo lo construye de las dos formas — recursivamente y con un stack explícito —, lo mira lanzarse por una rama, y lo pone a competir contra BFS en el único eje donde DFS gana de forma contundente: la memoria.

Un poco de historia

La búsqueda en profundidad es tan vieja que es anterior a las computadoras. En la década de 1880 el matemático francés Charles Pierre Trémaux describió un procedimiento para recorrer un laberinto: sigue un pasillo, márcalo, hasta que llegues a un callejón sin salida o a un cruce que ya viste, luego regresa a la última bifurcación que no habías probado. Eso es exactamente DFS, con las marcas haciendo el papel del conjunto de visitados. Se quedó como una curiosidad para resolver laberintos hasta los años setenta, cuando John Hopcroft y Robert Tarjan lo convirtieron en el motor de la teoría de grafos moderna. Su hallazgo fue que DFS no solo visita un grafo; el árbol que construye, y las marcas de tiempo de cuándo se entra y se termina cada nodo, exponen estructura profunda. En una ráfaga de artículos entre 1972 y 1973 usaron DFS para probar planaridad, encontrar componentes biconexas y fuertemente conexas, y más — todo en tiempo lineal, cuando los algoritmos previos eran cuadráticos o peores. El algoritmo de componentes fuertemente conexas de Tarjan, que sigue siendo el estándar hoy y que veremos más adelante en este nivel, es puro trabajo contable sobre DFS. Ese es el hilo conductor: BFS es el recorrido del camino más corto, pero DFS es el que revela estructura.

La intuición

Empieza en un nodo, márcalo como visto, y recursa hacia su primer vecino no visto. Luego recursa hacia el primer vecino no visto de ese nodo, y sigue bajando — no tocas el segundo vecino del inicio hasta que todo el subgrafo alcanzable a través del primero quedó completamente explorado y ya retrocediste hasta afuera. Cuando a un nodo no le quedan vecinos sin ver, regresas de él (lo sacas del stack) y continúas donde ibas. El recorrido traza un solo zarcillo largo hacia dentro del grafo, se retrae, enhebra otro zarcillo distinto, y así hasta cubrir todo lo alcanzable.

El mecanismo es un stack, y normalmente es el call stack — DFS es el recorrido que la recursión escribe gratis, porque una llamada recursiva es un push y un return es un pop. Esa es toda la diferencia con BFS: la queue de BFS atiende primero al nodo descubierto hace más tiempo (anchura), el stack de DFS atiende primero al descubierto más recientemente (profundidad). Mismo conjunto de visitados, mismo costo O(V+E), la misma idea de "tocar cada vértice y cada arista una vez" — un solo cambio de estructura de datos voltea todo el carácter de la búsqueda. Y por eso la memoria de DFS es tan distinta: en cualquier instante el stack solo guarda los nodos del camino actual desde la raíz, así que su working set es la profundidad de la búsqueda, no el ancho.

Complejidad: cómo escala

DFS es $O(V + E)$ en tiempo, exactamente igual que BFS: cada vértice se visita una vez y cada arista se examina una vez. La recurrencia de la forma recursiva es $T(V,E) = \Theta(V + E)$ — no hay explosión por ramificación porque el conjunto de visitados corta la re-exploración. Donde los dos recorridos sí divergen de verdad es en la memoria pico. La queue de BFS se infla hasta el tamaño del nivel más ancho del grafo; el stack de DFS solo guarda el camino actual, así que su pico es la profundidad del grafo. En un grafo ancho y poco profundo esa brecha es enorme, y eso es lo que mide el enfrentamiento — memoria de trabajo pico sobre árboles binarios completos conforme crecen:

En un árbol binario completo de altura 12 — 8191 nodos — la recursión de DFS nunca sostuvo más de 13 nodos a la vez (la profundidad de la raíz a la hoja), mientras que la queue de BFS llegó a un pico de 4096 (todo el nivel de abajo). Eso es 315 veces menos memoria para DFS, sobre el mismo grafo, y la brecha se abre con cada nivel que agregas porque el nivel de abajo se duplica mientras la profundidad crece de uno en uno. Este es el espejo honesto del resultado del capítulo pasado: BFS ganó en calidad de camino por un factor de diez, y aquí DFS gana en memoria por un factor de cientos. Ninguno de los dos recorridos domina; intercambian la anchura de la queue por la profundidad del stack.

En qué es bueno y en qué no

DFS es la herramienta correcta cuando la pregunta es la estructura del grafo y no la distancia. Su orden de finalización (la secuencia en que los nodos quedan completamente explorados), invertido, es un orden topológico de un DAG — el próximo capítulo. Una arista de regreso hacia un nodo que sigue en el stack de recursión es un ciclo, y así es como detectas deadlocks, dependencias circulares y loops infinitos en grafos de build. Correr un DFS por cada nodo no visitado parte el grafo en componentes conexas; una versión más cuidadosa (la de Tarjan) encuentra componentes fuertemente conexas en un grafo dirigido. DFS también está debajo de la búsqueda con backtracking — N reinas, Sudoku, resolución de restricciones — porque "prueba una opción, recursa, deshaz si falla" es DFS sobre el árbol de soluciones parciales. Y en grafos anchos su frugalidad de memoria es decisiva.

Donde DFS es la herramienta equivocada es en cualquier cosa que tenga que ver con caminos más cortos o con orden de cercanía. El camino que DFS encuentra entre dos nodos es un camino, a menudo uno absurdamente indirecto — en el enfrentamiento del capítulo pasado salió diez veces más largo que el camino más corto de BFS. Si quieres menos pasos, usa BFS; si quieres menos costo con pesos, usa Dijkstra. DFS también trae el riesgo de profundidad de recursión en grafos profundos que describimos en la sección a fondo, y a diferencia de BFS no te regala ninguna información de distancia.

Los datos, o las entradas

El enfrentamiento corre sobre árboles binarios completos de altura creciente, la forma de grafo más limpia para exponer la división de memoria entre profundidad y ancho: su profundidad crece de uno en uno por nivel mientras su nivel más ancho se duplica. La verificación de correctitud corre DFS (en sus dos formas) y BFS sobre grafos aleatorios para confirmar que alcanzan el mismo conjunto de nodos, y contrasta el detector de ciclos de tres colores contra un pelado independiente estilo Kahn sobre DAGs aleatorios con y sin un ciclo plantado. La animación corre el DFS recursivo sobre el mismo grafo de rejilla de 2×4 que BFS exploró el capítulo pasado, para que puedas poner los dos recorridos lado a lado.

Constrúyelo, una función a la vez

El recorrido recursivo — el call stack es el stack:

def dfs_recursive(adj, start, order=None, seen=None):
    """Explore depth-first from `start` using the CALL STACK as the stack. Visit a node,
    then recurse into its first unseen neighbor, going as deep as possible before
    backtracking. O(V + E): each vertex is visited once, each edge examined once. The
    recursion depth is the length of the current root-to-here path — DFS's whole memory
    footprint. Returns the visit order."""
    if order is None:
        order, seen = [], set()
    seen.add(start)
    order.append(start)
    for v in adj[start]:
        if v not in seen:
            dfs_recursive(adj, v, order, seen)   # go deep before going wide
    return order

El mismo recorrido hecho explícito, para que no desborde en grafos profundos:

def dfs_iterative(adj, start):
    """The same traversal with an EXPLICIT stack instead of recursion — the honest
    picture of what the call stack was doing, and the version that won't overflow on a
    graph deeper than Python's recursion limit. Push the start; repeatedly pop a node,
    and if it's unseen, visit it and push its neighbors. We mark on POP (not on push), so
    a node can sit on the stack more than once — that's the price of the explicit form."""
    seen = set()
    order = []
    stack = [start]
    while stack:
        u = stack.pop()
        if u in seen:
            continue
        seen.add(u)
        order.append(u)
        for v in reversed(adj[u]):      # reversed → visit neighbors in the same order as the recursive version
            if v not in seen:
                stack.append(v)
    return order

Y la capacidad distintiva de DFS — detectar un ciclo con tres colores:

def has_cycle_directed(adj):
    """DFS's signature trick: detect a cycle in a directed graph in O(V+E) using three
    colors. WHITE = untouched, GRAY = on the current recursion stack (being explored),
    BLACK = fully finished. An edge to a GRAY node is a BACK EDGE — it points to an
    ancestor still open on the stack, which means we've found a cycle. This is exactly
    what BFS cannot see cheaply, and it's the basis of topological sort next chapter."""
    n = len(adj)
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n

    def visit(u):
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:            # back edge to an ancestor on the stack → cycle
                return True
            if color[v] == WHITE and visit(v):
                return True
        color[u] = BLACK
        return False

    return any(color[u] == WHITE and visit(u) for u in range(n))

Míralo trabajar

Aquí está el DFS recursivo sobre la misma rejilla de 2×4 del capítulo de BFS, empezando en el nodo 0. El naranja es el nodo que se está visitando en este momento; los nodos azules son el stack de recursión — el camino activo desde la raíz hasta el nodo actual; los verdes ya terminaron (visitados y con el retroceso hecho); los oscuros aún no se descubren. Míralo lanzarse: de 0 va a 1, luego a 2, luego a 3, después cae al 7 y se enhebra de regreso por la fila de abajo — un solo zarcillo largo, no una ola. Compáralo directamente con el BFS del capítulo pasado, que encendía el anillo completo en cada distancia. Mismo grafo, mismo inicio; la queue se abrió en abanico, el stack se mete taladrando:

El código completo

Las dos versiones en un solo lugar — cambia entre ellas. La pestaña desde cero trae DFS de tres maneras (recursivo, iterativo y el detector de ciclos de tres colores) más las sondas de memoria pico. La pestaña de librería trae el DFS/BFS de referencia contra el que se verifican las trazas, con las llamadas de networkx que realmente usarías en producción anotadas al principio.

"""Depth-first search — the other foundational graph traversal, and BFS's mirror
image. Swap BFS's queue for a stack and "nearest first" becomes "deepest first":
DFS plunges down one branch as far as it can go, and only when it dead-ends does it
back up and try the next branch.

That single change — stack instead of queue — costs DFS the shortest-path guarantee
(the path it finds can wander), but buys a different set of powers. DFS's recursion
naturally exposes structure BFS can't see as cheaply: the order nodes FINISH (all
descendants done) gives topological orderings, a back edge to an ancestor still on
the stack detects a cycle, and one DFS per unvisited node enumerates connected
components. And on a graph that is wider than it is deep, DFS's memory is a single
root-to-leaf path where BFS must hold an entire level.
"""
from collections import deque


# region: dfs_recursive
def dfs_recursive(adj, start, order=None, seen=None):
    """Explore depth-first from `start` using the CALL STACK as the stack. Visit a node,
    then recurse into its first unseen neighbor, going as deep as possible before
    backtracking. O(V + E): each vertex is visited once, each edge examined once. The
    recursion depth is the length of the current root-to-here path — DFS's whole memory
    footprint. Returns the visit order."""
    if order is None:
        order, seen = [], set()
    seen.add(start)
    order.append(start)
    for v in adj[start]:
        if v not in seen:
            dfs_recursive(adj, v, order, seen)   # go deep before going wide
    return order
# endregion


# region: dfs_iterative
def dfs_iterative(adj, start):
    """The same traversal with an EXPLICIT stack instead of recursion — the honest
    picture of what the call stack was doing, and the version that won't overflow on a
    graph deeper than Python's recursion limit. Push the start; repeatedly pop a node,
    and if it's unseen, visit it and push its neighbors. We mark on POP (not on push), so
    a node can sit on the stack more than once — that's the price of the explicit form."""
    seen = set()
    order = []
    stack = [start]
    while stack:
        u = stack.pop()
        if u in seen:
            continue
        seen.add(u)
        order.append(u)
        for v in reversed(adj[u]):      # reversed → visit neighbors in the same order as the recursive version
            if v not in seen:
                stack.append(v)
    return order
# endregion


# region: has_cycle
def has_cycle_directed(adj):
    """DFS's signature trick: detect a cycle in a directed graph in O(V+E) using three
    colors. WHITE = untouched, GRAY = on the current recursion stack (being explored),
    BLACK = fully finished. An edge to a GRAY node is a BACK EDGE — it points to an
    ancestor still open on the stack, which means we've found a cycle. This is exactly
    what BFS cannot see cheaply, and it's the basis of topological sort next chapter."""
    n = len(adj)
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n

    def visit(u):
        color[u] = GRAY
        for v in adj[u]:
            if color[v] == GRAY:            # back edge to an ancestor on the stack → cycle
                return True
            if color[v] == WHITE and visit(v):
                return True
        color[u] = BLACK
        return False

    return any(color[u] == WHITE and visit(u) for u in range(n))
# endregion


# region: peak_memory
def peak_dfs_depth(adj, start):
    """Peak DFS memory = the deepest the recursion ever got = the longest root-to-here
    path DFS walked. On a graph wider than it is deep, this is tiny."""
    seen = set()
    peak = 0
    stack = [(start, 1)]
    while stack:
        u, depth = stack.pop()
        if u in seen:
            continue
        seen.add(u)
        peak = max(peak, depth)
        for v in adj[u]:
            if v not in seen:
                stack.append((v, depth + 1))
    return peak


def peak_bfs_frontier(adj, start):
    """Peak BFS memory = the widest the queue ever got = the largest level (ring of one
    distance). On a wide, shallow graph this is the whole bottom level — huge."""
    seen = {start}
    peak = 0
    q = deque([start])
    while q:
        peak = max(peak, len(q))
        u = q.popleft()
        for v in adj[u]:
            if v not in seen:
                seen.add(v)
                q.append(v)
    return peak
# endregion

"""The library counterpart. In real work you don't hand-roll graph traversal — you
reach for networkx, which gives you dfs_preorder_nodes, dfs_tree, find_cycle,
topological_sort, and connected_components, all built on the DFS in impl.py.

    import networkx as nx
    G = nx.DiGraph(); G.add_edges_from(edges)
    list(nx.dfs_preorder_nodes(G, source))   # the visit order
    nx.find_cycle(G)                          # raises if acyclic, else returns the cycle
    list(nx.topological_sort(G))              # DFS finish-order, reversed

networkx is the real, batteries-included graph library, but its traversals are the
exact algorithm in impl.py — a stack, a visited set, O(V+E). To keep this chapter's
data reproducible with the standard library alone, the trace generator checks our DFS
against the plain references below (and the BFS it's raced against for memory).
"""
from collections import deque


# region: reference
def dfs_reference(adj, start):
    """A minimal recursive DFS, the ground truth for the visit order."""
    seen, order = set(), []

    def go(u):
        seen.add(u)
        order.append(u)
        for v in adj[u]:
            if v not in seen:
                go(v)

    go(start)
    return order


def bfs_order(adj, start):
    """Plain BFS — the queue-based sibling DFS is compared against."""
    seen = {start}
    order = []
    q = deque([start])
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            if v not in seen:
                seen.add(v)
                q.append(v)
    return order


def has_cycle_reference(adj):
    """Kahn-style acyclicity check (peel off in-degree-0 nodes) — an independent way to
    confirm the DFS three-color cycle detector, using no recursion at all."""
    n = len(adj)
    indeg = [0] * n
    for u in range(n):
        for v in adj[u]:
            indeg[v] += 1
    q = deque(u for u in range(n) if indeg[u] == 0)
    removed = 0
    while q:
        u = q.popleft()
        removed += 1
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return removed != n     # couldn't remove everyone → a cycle held some nodes back
# endregion

Desde cero vs librería

DFS y BFS tienen complejidad idéntica, así que la comparación — igual que el capítulo pasado — no es de velocidad, es de cuál propiedad necesitas. BFS te dio caminos más cortos; DFS te da estructura y poca memoria. El enfrentamiento hizo concreta la diferencia de memoria: 315× menos en un árbol ancho. Pero la lección de fondo es que estos dos recorridos son un par emparejado, separados por una sola decisión de estructura de datos, y casi todos los algoritmos de grafos de este nivel son uno de ellos con trabajo contable extra atornillado encima. El orden topológico es DFS más tiempos de finalización. Dijkstra es BFS más una cola de prioridad. Las componentes de Tarjan son DFS más números low-link. Aprender a ver un algoritmo de grafos nuevo como "¿BFS o DFS, más qué?" es casi todo lo que necesitas para leer este nivel con soltura. Cuando eches mano de una librería de grafos como networkx, sus dfs_preorder_nodes, find_cycle y topological_sort son todos este mismo recorrido basado en stack — la librería te ahorra el trabajo contable, no el entendimiento.

Dónde te lo vas a encontrar

DFS está en todos lados donde importa la estructura. Los sistemas de build (make, bazel, npm, cargo) lo corren sobre el grafo de dependencias para ordenar la compilación y para rechazar dependencias circulares. Los motores de hojas de cálculo lo usan para recalcular celdas en orden de dependencia y para marcar referencias circulares. Los garbage collectors marcan con él los objetos alcanzables. Los compiladores lo usan para análisis de flujo de control y de flujo de datos. Todo solver con backtracking — Sudoku, N reinas, motores de regex, solvers de restricciones, generadores de laberintos — es DFS sobre un árbol de decisiones. Los recorredores de sistemas de archivos (os.walk, find) son DFS sobre directorios. Y los algoritmos pesados de grafos — componentes fuertemente conexas, biconectividad, puntos de articulación, orden topológico — son todos el DFS con marcas de tiempo de Hopcroft y Tarjan. Donde sea que la pregunta sea "qué depende de qué", "hay un ciclo" o "explora este espacio barato", DFS es la herramienta.

Puntos clave

La búsqueda en profundidad explora un grafo comprometiéndose con una rama y siguiéndola hasta el final antes de retroceder, movida por un stack — normalmente el call stack, que es la razón por la que la recursión lo escribe gratis. Es BFS con la queue cambiada por un stack, y ese solo cambio intercambia anchura y caminos más cortos por profundidad, estructura y memoria O(profundidad): en un árbol ancho usó 315× menos memoria que BFS. No encuentra caminos más cortos, y su forma recursiva puede desbordar el stack en grafos profundos — ahí échale mano a la versión con stack explícito.

El verdadero valor de DFS aparece en el próximo capítulo, donde el orden en que termina los nodos resulta ser un ordenamiento topológico de un grafo dirigido acíclico — la secuencia correcta para ejecutar tareas cuyas dependencias forman un grafo. El orden topológico es el primero de varios algoritmos clásicos que, en el fondo, son una búsqueda en profundidad llevando una pieza extra de contabilidad.