DFS, recursión y pilas iterativas
Explore en profundidad y evite los límites de recursión
DFS, recursión y pilas iterativas es una lección gratuita de Coding Interview Prep en CoddyKit. Esta es la lección 3 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de Coding Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de Coding Interview Prep incluye 4 lecciones en total.
Qué hace DFS
DFS se adentra todo lo posible por un camino y después retrocede para probar el siguiente. Piense en explorar un laberinto pasillo por pasillo. 🧭
DFS frente a BFS
BFS se extiende por capas; DFS se adentra primero. Ambos visitan todos los nodos alcanzables, pero en un orden muy diferente.
La estructura recursiva
El DFS recursivo marca un nodo como visited y después se llama a sí mismo para cada vecino no visitado. La pila de llamadas recuerda dónde debe continuar.
def dfs(u):
visited[u] = True
for v in adj[u]:
if not visited[v]:
dfs(v)Marcar antes de llamar recursivamente
Establezca visited al entrar en un nodo, antes de explorar sus vecinos. De lo contrario, los ciclos harán que DFS entre en una recursión infinita.
La trampa del límite de recursión
Python limita la recursión a cerca de 1000 llamadas. Un grafo profundo provoca un RecursionError, que aparece como un veredicto de error en tiempo de ejecución.
Aumentar el límite
Una solución rápida consiste en elevar el límite con setrecursionlimit. Establézcalo por encima de la profundidad máxima prevista antes de ejecutar DFS.
import sys
sys.setrecursionlimit(300000)Usar una versión iterativa
La solución más segura es un DFS iterativo que utilice su propia pila. Al no depender de la profundidad de llamadas, no se producirá un fallo de recursión.
stack = [start]Extraer de la pila
En cada paso, extraiga el elemento superior de la pila. El orden último en entrar, primero en salir hace que DFS se adentre primero por el camino más reciente.
u = stack.pop()Introducir los vecinos en la pila
Después de extraer u, introduzca cada vecino no visitado en la pila. Márquelos para no volver a introducirlos.
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)El bucle iterativo completo
Repita las operaciones de extraer e introducir mientras la pila contenga nodos. Cuando se vacíe, habrá visitado todos los nodos alcanzables.
while stack:
u = stack.pop()
for v in adj[u]:
if not visited[v]:
visited[v] = True
stack.append(v)El mismo coste que BFS
Al igual que BFS, DFS visita cada nodo y cada arista una vez, por lo que se ejecuta en O(n + m). Elija el algoritmo cuyo orden se adapte mejor a la tarea.
Comprobación rápida
Su DFS recursivo falla en un grafo profundo. ¿Por qué?
Resumen
Puede ejecutar DFS de forma recursiva o con su propia pila, marcar visited al entrar y cambiar a la versión iterativa cuando el grafo sea profundo. 🎉
Preguntas frecuentes
¿La lección «DFS, recursión y pilas iterativas» es gratis?
Sí — el texto completo de «DFS, recursión y pilas iterativas» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de Coding Interview Prep, actualiza a CoddyKit PRO. El curso de Coding Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «DFS, recursión y pilas iterativas»?
Explore en profundidad y evite los límites de recursión Practicas Coding Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar Coding Interview Prep?
No se requiere experiencia previa. Coding Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 3 de 4.
¿Cuánto tiempo toma la lección «DFS, recursión y pilas iterativas»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de Coding Interview Prep?
Sí. Cada lección de Coding Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Listas de adyacencia a partir de la entrada
- BFS para caminos mínimos no ponderados
- DFS, recursión y pilas iterativas
- Componentes conexas y flood fill