Algoritmos en Python

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.

  • Intermedio
  • 2 min de lectura
  • 1 ejemplo ejecutable

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.

De explorar una cueva al código
visited.add(node)🧵 Marca este túnel como explorado
for neighbor in graph[node]:🔀 Mira cada túnel que sale de aquí
depth_first(neighbor, visited)⬇️ Baja por el primero sin explorar
return order↩️ Callejón sin salida: sigue el hilo de vuelta
Primero ve a fondo, luego retrocede y prueba la siguiente rama.
En una frase

La 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

  1. visited.add(node) marca el nodo, así los ciclos no pueden causar una recursión infinita.
  2. for neighbor in graph[node]: mira cada vecino por turno.
  3. order.extend(depth_first(neighbor, visited)) explora toda la rama que cuelga de un vecino antes de pasar al siguiente.
  4. 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

Ejecutar código →
main.py
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"))
Obtén un botón Run para este ejemplo

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.

  1. Prueba con una lista vacía, una lista de un solo elemento y una lista con repetidos.
  2. Muestra el estado después de cada paso para ver el algoritmo en acción.
  3. Mide el tiempo de ejecución con 100, 1.000 y 10.000 elementos y compáralo con otra solución.
Ejecutar en el compilador de Python →

Errores comunes

Usar un argumento por defecto mutable

visited=set() se compartiría entre llamadas distintas.

Problema
def depth_first(node, visited=set()):
Solución
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.

Todos los retos