Búsqueda en profundidad (DFS)

Sigue una rama hasta el fondo, luego retrocede. BFS con un stack en lugar de una queue.

El stack es lo que lo hace ir profundo

• Recursa hacia el primer vecino no visto, luego hacia el primer vecino no visto de ESE…
• Una llamada recursiva es un push; un return es un pop
• El stack solo guarda el camino actual de la raíz hasta aquí → memoria O(profundidad)
• Cambia stack → queue y se convierte en BFS

Míralo taladrar hacia dentro

Naranja = visitando · azul = stack de recursión (camino activo) · verde = ya retrocedido. Un solo zarcillo largo, no una ola.

DFS gana en memoria

Árbol ancho, 8191 nodos: DFS sostuvo 13, BFS sostuvo 4096 → 315× menos.

Para qué sirve DFS

• Detección de ciclos (tres colores: blanco / gris / negro)
• Orden topológico (orden de finalización, próximo capítulo)
• Componentes conexas y fuertemente conexas
• Búsqueda con backtracking (prueba → recursa → deshaz)

Dos trampas

• NO da caminos más cortos — su ruta puede irse por las ramas (eso es BFS)
• La forma recursiva desborda el call stack en grafos profundos → usa el stack iterativo

Para llevar

BFS y DFS son un par emparejado: los separa una sola decisión de estructura de datos. Queue = anchura + caminos más cortos. Stack = profundidad + estructura. Lee cada algoritmo de grafos como "¿BFS o DFS, más qué?" Sigue: orden topológico.