DFS/BFS: búsqueda en profundidad frente a búsqueda en amplitud

Al finalizar este tema

Comprenderás la diferencia entre cómo DFS y BFS exploran un grafo y podrás decidir cuál utilizar según el tipo de problema.

Dos estrategias para escapar de un laberinto

Has entrado en un laberinto. Aparece una bifurcación. Hay dos estrategias disponibles.

Estrategia A: Elige una dirección y avanza hasta el final. Si llegas a un callejón sin salida, regresa a la última bifurcación e intenta otro camino. Es un enfoque de "profundizar en un solo camino".

Estrategia B: Desde la bifurcación, avanzas un paso en todas las direcciones posibles. Luego, desde cada nueva posición, vuelves a avanzar un paso en todas las direcciones. Es un enfoque que se expande como ondas concéntricas.

La Estrategia A es DFS (búsqueda en profundidad) y la Estrategia B es BFS (búsqueda en amplitud).

DFS: seguir un camino hasta el final

A
   / \
  B   C
 / \   \
D   E   F

Si se inicia desde A y se explora mediante DFS: A → B → D → (bloqueo, retroceso) → E → (retroceso) → C → F

Al elegir una rama, se sigue hasta el final. Si no hay más opciones, se regresa (backtracking) para explorar otra rama.

La implementación se realiza utilizando una pila (Stack) o recursión:

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    print(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

La recursión funciona como una pila. La función se llama a sí misma, lo que permite profundizar en la estructura, y luego regresa al retornar.

BFS: Exploración por cercanía

Al explorar el mismo árbol con BFS, el orden es: A → B → C → D → E → F

Primero se visitan B y C, que están a una distancia de un paso de A. Luego se visitan D, E y F, que están a una distancia de dos pasos. La exploración sigue el orden de cercanía.

La implementación utiliza una cola (Queue):

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

Al procesarlos en el orden en que se añaden a la cola, los nodos más cercanos se procesan primero.

Diferencia clave: pila vs. cola

El código de DFS y BFS es casi idéntico. La única diferencia radica en qué estructura de datos se utiliza para gestionar los nodos siguientes.

DFS: pila (o recursión) → se extrae lo último insertado primero → dirección profunda
BFS: cola              → se extrae lo primero insertado primero     → dirección amplia

Cambiar una sola estructura de datos altera completamente el orden de recorrido.

Cuándo usar qué

Cuándo es adecuado usar DFS:

• Verificar si existe una ruta (sí/no)
• Cuando se deben explorar todas las posibilidades (retroceso)
• En un laberinto, cuando solo es necesario encontrar una salida
• Cuando se desea consumir menos memoria (solo guardar la ruta actual)

Cuándo es adecuado usar BFS:

• Cuando se necesita encontrar la ruta más corta
• Cuando se debe explorar desde lo más cercano hacia lo más lejano
• En redes sociales, para recomendar "amigos de amigos"
• Para encontrar el servidor más cercano en una red

La distinción más importante: usa BFS si necesitas la distancia mínima, y DFS si solo necesitas verificar la existencia.

BFS visita los nodos cercanos primero, por lo que la primera ruta encontrada es la ruta más corta. DFS se adentra en profundidad, por lo que no garantiza encontrar la ruta más corta.

Complejidad temporal

Ambas son O(V + E). V es el número de nodos y E el número de aristas. Se revisa cada nodo una vez y cada arista una vez. Solo difiere el orden de recorrido; la carga total de trabajo es la misma.

La complejidad espacial sí difiere. DFS utiliza una pila proporcional a la profundidad de la ruta actual de recorrido. BFS coloca todos los nodos del mismo nivel en una cola, por lo que consume más memoria en grafos con un ancho amplio.

Puntos clave

DFS recorre una dirección hasta el final y retrocede si se bloquea. Utiliza una pila o recursión. BFS recorre todo desde lo más cercano. Utiliza una cola. Si necesitas la ruta más corta, usa BFS; si solo necesitas verificar la existencia, es adecuado usar DFS.