DFS — Algoritmo de búsqueda en profundidad explicado

La búsqueda en profundidad, o DFS, es un algoritmo para explorar un árbol o un grafo siguiendo un camino tan lejos como sea posible antes de retroceder. En términos simples: DFS sigue profundizando hasta que se atasca, y luego vuelve al último lugar donde había otra rama disponible.

Si recuerdas una sola idea, recuerda esta: DFS significa "profundiza y luego retrocede".

Qué hace la búsqueda en profundidad

DFS puede usarse en árboles y en grafos generales. Empezando desde un nodo, se mueve repetidamente a un vecino no visitado. Cuando llega a un nodo que ya no tiene vecinos no visitados, retrocede al nodo anterior y continúa desde allí.

Ese retroceso es el comportamiento que la define. En las implementaciones recursivas, la pila de llamadas se encarga de ello automáticamente. En las implementaciones iterativas, una pila explícita cumple el mismo papel.

Por qué el orden de DFS puede cambiar

DFS no produce un único orden de visita universal. El orden exacto depende del orden en que se consideren los vecinos.

Por ejemplo, si un nodo tiene como vecinos a $B$ y $C$, visitar primero $B$ puede dar un orden DFS distinto que visitar primero $C$. La búsqueda sigue siendo DFS en ambos casos porque la regla es la misma: seguir profundizando antes de explorar una rama hermana.

Ejemplo de DFS en un grafo pequeño

Supón que el grafo tiene estas conexiones:

• $A$ se conecta con $B$ y $C$
• $B$ se conecta con $D$ y $E$
• $C$ se conecta con $F$

Supón que siempre inspeccionamos los vecinos de izquierda a derecha y empezamos en $A$.

DFS avanza así:

1. Visita $A$
2. Ve a $B$
3. Ve a $D$
4. $D$ no tiene vecinos no visitados, así que retrocede a $B$
5. Desde $B$, ve a $E$
6. $E$ termina, así que retrocede a $B$ y luego a $A$
7. Desde $A$, ve a $C$
8. Desde $C$, ve a $F$

Así que un orden de visita DFS válido es:

$$A, B, D, E, C, F$$

La idea clave es que DFS termina el lado $A \to B$ antes de empezar el lado $A \to C$. Si cambiaras el orden de los vecinos, el orden de visita también podría cambiar.

Por qué el retroceso usa una pila

DFS siempre necesita una forma de recordar a dónde volver después de llegar a un callejón sin salida. Por eso las pilas aparecen de forma natural en DFS.

En DFS recursivo, cada llamada de función espera mientras la búsqueda profundiza, y el programa regresa en orden inverso cuando retrocede. En DFS iterativo, apilas nodos en una pila y los desapilas cuando llega el momento de continuar desde el punto inacabado más reciente.

Complejidad temporal y espacial de DFS

Si el grafo se almacena como una lista de adyacencia y cada vértice se marca la primera vez que se visita, DFS se ejecuta en

$$O(V + E)$$

tiempo para la parte alcanzable del grafo, donde $V$ es el número de vértices y $E$ es el número de aristas.

El espacio extra suele ser

$$O(V)$$

porque la estructura de visitados y la pila de recursión o la pila explícita pueden crecer cada una con el número de vértices.

Errores comunes en DFS

Olvidar marcar los nodos visitados

En un grafo general, olvidar la comprobación de visitados puede hacer que DFS recorra un ciclo para siempre. Incluso en un árbol almacenado como grafo no dirigido, todavía necesitas evitar volver inmediatamente al padre, a menos que tu código maneje ese caso de forma explícita.

Suponer que DFS encuentra el camino más corto

DFS puede encontrar un camino, pero en general no garantiza el camino más corto en un grafo no ponderado. Si el objetivo es el camino más corto y todas las aristas tienen el mismo peso, BFS suele ser el punto de partida correcto.

Tratar el orden de DFS como si fuera único

El orden depende del orden de los vecinos. Si ese orden cambia, el orden del recorrido también puede cambiar.

Cuándo se usa la búsqueda en profundidad

DFS es útil cuando quieres explorar la estructura en lugar de solo la distancia más cercana primero. Algunos usos comunes incluyen:

• comprobar si un nodo es alcanzable
• encontrar componentes conectados
• detectar ciclos en algunos contextos de grafos
• recorrer árboles
• resolver problemas de tipo backtracking, como laberintos o búsqueda en rompecabezas

La razón principal por la que aparece tan a menudo es que "profundiza y luego retrocede" encaja con muchas estructuras de problemas recursivos.

DFS vs BFS: la diferencia práctica

DFS baja primero por una rama. BFS explora todos los nodos a una distancia antes de pasar a la siguiente distancia.

Si te importa la exploración exhaustiva o la estructura recursiva, DFS suele ser natural. Si te importa el camino más corto en un grafo no ponderado, BFS suele ser la opción inicial más segura.

Prueba un recorrido similar

Dibuja un grafo pequeño con seis nodos y elige un orden fijo para los vecinos. Ejecuta DFS a mano y anota exactamente cuándo avanzas y cuándo retrocedes. Si tu orden cambia después de reordenar los vecinos, eso no es un error. Es parte de cómo funciona DFS.