Búsqueda en anchura (BFS) explicada: cómo funciona, código y complejidad

Qué problema resuelve BFS

Muchos problemas son grafos disfrazados: páginas web y enlaces, amigos en una red social, casillas de un tablero, estados de un rompecabezas. BFS responde dos preguntas habituales sobre un grafo así: qué nodos puedo alcanzar desde un nodo inicial y cuál es el número mínimo de pasos para llegar a cada uno.

Como BFS explora en anillos de distancia creciente, la primera vez que llega a un nodo siempre lo hace por un camino con el menor número de aristas. Por eso es el algoritmo estándar para caminos más cortos cuando todas las aristas tienen el mismo coste.

La idea en palabras sencillas

1. Pon el nodo inicial en una cola y márcalo como visitado.
2. Toma el nodo que está al frente de la cola.
3. Para cada vecino que aún no esté visitado, márcalo como visitado y añádelo al final de la cola.
4. Repite los pasos 2 y 3 hasta que la cola quede vacía.

Marca un nodo como visitado cuando lo añades a la cola, no cuando lo sacas. De lo contrario, el mismo nodo puede añadirse muchas veces antes de procesarse.

Ejemplo resuelto, paso a paso

Toma este grafo no dirigido: A–B, A–C, B–D, C–D, C–E, D–F. Empieza en A y visita los vecinos en orden alfabético.

El orden de visita es A, B, C, D, E, F. A D se puede llegar desde B y desde C, pero se descubre una sola vez, desde B, porque en ese momento ya queda marcado como visitado.

Implementación en Python

Usa collections.deque para la cola: popleft() es O(1), mientras que list.pop(0) es O(n). El grafo es un diccionario que asigna a cada nodo una lista de vecinos (una lista de adyacencia).

from collections import deque
def bfs(graph, start):
    """Return the distance (number of edges) from start to each reachable node."""
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in dist:          # not visited yet
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist
graph = {
    "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
    "D": ["B", "C", "F"], "E": ["C"], "F": ["D"],
}
print(bfs(graph, "A"))  # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}

Aquí el diccionario dist cumple una doble función: es el conjunto de visitados y guarda la respuesta. Para reconstruir el camino real, guarda también el padre de cada nodo y retrocede desde el destino.

def shortest_path(graph, start, goal):
    parent = {start: None}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            path = []
            while node is not None:
                path.append(node)
                node = parent[node]
            return path[::-1]
        for nxt in graph[node]:
            if nxt not in parent:
                parent[nxt] = node
                queue.append(nxt)
    return None  # goal not reachable
print(shortest_path(graph, "A", "F"))  # ['A', 'B', 'D', 'F']

Complejidad temporal y espacial

V es el número de vértices (nodos) y E el de aristas. Con una matriz de adyacencia en lugar de listas, el tiempo pasa a ser O(V²), porque encontrar los vecinos de un nodo cuesta O(V).

Variantes y errores comunes

• BFS en cuadrículas: trata cada celda como un nodo y las cuatro (u ocho) celdas vecinas como aristas. Comprueba los límites y las paredes antes de añadir una celda.
• BFS multifuente: pon varios nodos iniciales en la cola con distancia 0. Así obtienes la distancia a la fuente más cercana, por ejemplo la salida más próxima de un laberinto.
• BFS 0-1: cuando los pesos de las aristas solo son 0 o 1, usa una deque y coloca al frente los vecinos de peso 0. Da caminos más cortos en O(V + E).
• BFS bidireccional: busca desde el origen y desde el destino a la vez y detente cuando las dos fronteras se encuentren. A menudo explora muchos menos nodos.
• Procesamiento por niveles: guarda len(queue) al inicio de cada ronda y extrae exactamente esa cantidad de nodos para tratar un nivel cada vez.

Cuándo usar BFS y usos en el mundo real

• Problemas de entrevista: camino más corto en un laberinto o cuadrícula, escalera de palabras, naranjas podridas (BFS multifuente), recorrido por niveles de un árbol binario, número mínimo de movimientos de un caballo.
• Redes: encontrar todos los dispositivos a k saltos, difusión en redes entre pares, "personas que quizá conozcas" a distancia 2 en un grafo social.
• Rastreadores web que visitan las páginas por orden de distancia en enlaces desde una página semilla.
• Recolectores de basura (por ejemplo, el recolector de copia de Cheney) y resolutores de rompecabezas que necesitan el menor número de movimientos.