El recorrido DFS (Depth First Search) o búsqueda por profundidad es una de las formas más usadas para visitar nodos en un grafo o árbol. Sirve cuando necesitas explorar un camino completo antes de regresar y probar otro, y es una pieza clave si estás aprendiendo estructuras de datos no lineales.

Cómo funciona el recorrido DFS en un árbol binario

Imagina un árbol binario con su raíz en la parte superior. En lugar de pintar primero el nodo de la izquierda y luego el de la derecha al mismo nivel, con DFS bajas hasta el último hijo posible por un camino, y solo cuando ya no puedes avanzar más, regresas para tomar otro camino [01:00].

Una analogía útil es pensar en agua cayendo por una llave. El agua entra por la raíz y empieza a llenar hacia abajo cada círculo del árbol, siguiendo la gravedad. No se distribuye en paralelo entre niveles, sino que profundiza primero por una rama hasta el fondo. Esa idea de profundizar es la esencia del algoritmo.

¿Qué es DFS en estructuras de datos? Es un algoritmo de recorrido que visita un nodo y luego prioriza a sus hijos antes que a sus hermanos del mismo nivel, hasta llegar al final de cada rama.

Por qué DFS también funciona en grafos, no solo en árboles

DFS no se limita a árboles. También aplica en grafos generales, donde no siempre existe una raíz única. Puedes tener varios nodos iniciales, nodos independientes o simplemente un nodo desde el cual decidiste comenzar tu recorrido.

Piensa en un grafo de ciudades conectadas por carreteras. Si partes de una ciudad y la siguiente es otra ciudad, con DFS recorres primero un camino completo hasta la última ciudad alcanzable, y solo después vuelves para iniciar otro camino. Es lo opuesto a avanzar dos caminos a la par.

Qué prioridad sigue DFS al elegir el siguiente nodo

La regla es clara: cuando estás en un nodo, en vez de mirar a sus hermanos del mismo nivel, le das prioridad a sus hijos. Y cada hijo repite la misma lógica con los suyos. Así se construye la profundidad del recorrido de forma natural y recursiva.

Cómo se relaciona DFS con la estructura de datos pila

El comportamiento de DFS es prácticamente idéntico al de una pila, esa estructura de datos donde lo último que entra es lo primero que sale (LIFO) [03:00]. El último nodo que revisaste es el que toma prioridad para seguir explorando, y sus hijos son los que acabas de ingresar a esa pila mental.

Por eso, cuando implementes DFS en código, te vas a apoyar en una pila, ya sea explícita o usando la pila de llamadas de la recursión. Los nodos viejos del mismo nivel quedan esperando hasta que termines de profundizar.

¿Por qué DFS usa una pila y no una cola? Porque DFS necesita atender primero el nodo más reciente para seguir bajando. Una cola haría lo contrario y recorrería por niveles.

Cuál es la complejidad temporal de DFS

La complejidad temporal de DFS se calcula como O(V + E), donde V es el número de nodos (vértices) y E es la cantidad de aristas o relaciones entre esos nodos [02:30]. Tiene sentido: visitas cada nodo una vez y revisas cada conexión también una vez.

Algunos puntos prácticos para tener presentes al usar DFS:

• Funciona en árboles binarios, árboles generales y grafos.
• Profundiza por una rama antes de explorar otras.
• Se apoya en una pila o en recursión.
• Su costo crece con nodos y aristas, no con niveles.

¿Cuándo conviene usar DFS? Cuando quieres explorar caminos completos, detectar ciclos, recorrer laberintos o resolver problemas donde la profundidad importa más que el orden por niveles.

Si ya entendiste la lógica detrás del recorrido, el siguiente paso es verlo en código y notar cómo la pila aparece de forma natural. Cuéntame en los comentarios qué problema te gustaría resolver con DFS.