Cómo funciona
DFS (depth-first search, búsqueda en profundidad) siempre sigue adelante: mira la celda de
la cima de la pila y da un paso a su primer vecino sin marcar (norte, este, sur,
oeste), que apila. Cuando la cima no tiene salida, es un callejón: se desapila y se
vuelve atrás para probar otra salida.
La pila es siempre el camino desde el inicio hasta la celda actual: por eso aquí es una torre al lado
del mapa y un tubo naranja sobre él. Cuando el destino llega a la cima, la pila entera es el camino
encontrado. Es un camino, no necesariamente el más corto.
Paso a paso: de A3 a E3
Un mapa abierto de 7 × 5 con un muro en B1–B2. El destino está a solo 4 pasos al este.
- 01Rama 1: el norte va primero, así que A3 → A2 → A1. A1 y A2 no tienen más salidas: son callejones y se desapilan. Se vuelve a A3.
- 02Rama 2: A3 → B3 → C3, y en C3 otra vez el norte va primero: sube a C1 y recorre la fila de arriba hasta G1, aunque el destino estaba a dos casillas al este.
- 03Baja por la columna G hasta G5, vuelve por F5 y F4 y llega a F3, justo al lado del destino. Pero el norte va antes que el oeste: F2, E2 y, por fin, E3.
- ΣCamino de 18 pasos, con 21 celdas marcadas y 2 callejones. BFS, en el mismo mapa, encuentra el de 4 pasos, A3 → B3 → C3 → D3 → E3, expandiendo 15 celdas.
Cuándo sirve
DFS no busca el camino más corto, pero necesita poca memoria en mapas estrechos (solo la rama actual)
y es la forma natural de recorrer algo entero: generar o resolver laberintos, detectar ciclos, ordenar
tareas con dependencias. El generador de laberintos de esta página es, de hecho, un DFS con los
vecinos en orden aleatorio.
Complejidad
- Tiempo
- O(V + E)
- Memoria
- O(V), la pila
- Estructura
- Pila LIFO
- Óptimo
- No
- Completo
- Sí, en mapas finitos
- En una rejilla
- V celdas, E ≤ 4V