La búsqueda en profundidad (DFS) en Python
En esta lección vas a recorrer un grafo con la búsqueda en profundidad, implementada con una función recursiva.
Introducción
El problema
Encontrar la salida de un laberinto, comprobar si un grafo tiene un ciclo u ordenar tareas que dependen unas de otras exige seguir un camino hasta donde llegue antes de probar otro. Eso es la búsqueda en profundidad.
Imagínalo así
La búsqueda en profundidad es como explorar una cueva con un ovillo de hilo. Sigues un túnel hasta lo más hondo. En un callejón sin salida, sigues el hilo de vuelta hasta la última bifurcación y pruebas el siguiente túnel. Marcas los túneles que ya exploraste para no recorrerlos nunca dos veces.
visited.add(node)🧵 Marca este túnel como exploradofor neighbor in graph[node]:🔀 Mira cada túnel que sale de aquídepth_first(neighbor, visited)⬇️ Baja por el primero sin explorarreturn order↩️ Callejón sin salida: sigue el hilo de vueltaLa búsqueda en profundidad (DFS) explora un grafo siguiendo una rama lo más hondo posible antes de retroceder, normalmente con recursión o una pila.
Puntos clave
visited.add(node)marca el nodo, así los ciclos no pueden causar una recursión infinita.for neighbor in graph[node]:mira cada vecino por turno.order.extend(depth_first(neighbor, visited))explora toda la rama que cuelga de un vecino antes de pasar al siguiente.- El resultado visita D antes que C, porque primero se termina la rama de B.
¿Cuándo se usa?
- Encontrar cualquier camino, resolver laberintos y acertijos con backtracking.
- Detectar ciclos y ordenar tareas con dependencias (ordenación topológica).
- Explorar todas las partes conectadas de un grafo.
Cuándo no hace falta
- Necesitas el camino más corto: la búsqueda en profundidad puede encontrar antes un camino largo; usa búsqueda en anchura.
- Grafos muy profundos: la recursión puede chocar con el límite de Python; usa una pila explícita.
Visualizador de La búsqueda en profundidad (DFS) en Python
O(V + E)Usa Reproducir o Paso para seguir cada comparación y movimiento de datos.
Código de ejemplo
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
def depth_first(node, visited=None):
visited = visited or set()
visited.add(node)
order = [node]
for neighbor in graph[node]:
if neighbor not in visited:
order.extend(depth_first(neighbor, visited))
return order
print(depth_first("A"))
Resultado de la ejecución
['A', 'B', 'D', 'C', 'E']
Explicación del código
El conjunto visited recuerda los nodos visitados para evitar repeticiones y bucles infinitos cuando el grafo tiene ciclos. Cada llamada recursiva baja hacia un vecino aún no visitado, así que el programa visita A, B, D antes de volver para visitar C y E. La pila de llamadas hace el papel de la pila del algoritmo, y la complejidad es O(V + E).
Cambia los valores y ejecuta el programa en el compilador Python online de CodeUtility sin instalar Python.
Ejercicios de práctica
Prueba a modificar el código siguiendo las ideas de abajo. Cambiar el código y ver el resultado te ayudará a entender la lección mucho mejor que solo leerla.
- Prueba con una lista vacía, una lista de un solo elemento y una lista con repetidos.
- Muestra el estado después de cada paso para ver el algoritmo en acción.
- Mide el tiempo de ejecución con 100, 1.000 y 10.000 elementos y compáralo con otra solución.
Errores comunes
Usar un argumento por defecto mutable
visited=set() se compartiría entre llamadas distintas.
def depth_first(node, visited=set()):
def depth_first(node, visited=None):
visited = visited or set()
¿Terminaste esta lección?
Márcala como aprendida para seguir tu progreso.
Practica con un reto
Usa lo que cubre esta lección para resolver un problema real. Cada reto se ejecuta en el navegador, con pruebas al instante y una revisión de IA.
- Count Islands Count groups of connected land cells in a grid. Intermedio
- Componentes Fuertemente Conexas Cuenta los grupos de nodos donde todos pueden alcanzarse mutuamente. Difícil
- Longest Path in a DAG Find the heaviest path in a task dependency graph. Difícil