Búsqueda en anchura (BFS)

Qué cubre este capítulo

La búsqueda en anchura es el recorrido de grafos que explora hacia afuera en anillos: primero todo lo que está a un paso, luego todo lo que está a dos pasos, y así sucesivamente. Su motor es la queue del nivel de estructuras lineales, y esa disciplina FIFO le da a BFS un superpoder: la primera vez que llega a un nodo, llegó por la menor cantidad posible de aristas. Así que BFS no es nada más una forma de visitar todos los nodos alcanzables; en un grafo sin pesos es el algoritmo de camino más corto, el que está detrás de los "grados de separación", los solucionadores de laberintos y los acertijos de "mínimos movimientos". En este capítulo lo construimos, vemos la frontera expandirse en oleadas y lo vemos encontrar caminos un orden de magnitud más cortos que los de una búsqueda en profundidad.

Un poco de historia

La búsqueda en anchura se inventó varias veces para resolver problemas prácticos de ruteo. Konrad Zuse la describió en 1945 en su tesis nunca publicada, pero las versiones que se quedaron vinieron de la ingeniería: Edward Moore la publicó en 1959 como método para encontrar el camino más corto a través de un laberinto, y C. Y. Lee la desarrolló de forma independiente en 1961 para rutear cables en tarjetas de circuitos, el "algoritmo de Lee" que todavía se usa en diseño de chips. Ese origen dice mucho: BFS no fue una curiosidad teórica sino una herramienta para encontrar las conexiones más cortas en redes físicas, laberintos y circuitos, que es justo en lo que sigue siendo mejor. Su matrimonio con la queue, y su garantía de caminos más cortos, la convirtieron en uno de los dos recorridos fundamentales de grafos, y la plantilla —explorar una frontera, marcar lo que ya viste, expandirte hacia afuera— reaparece en Dijkstra, A* y en la mitad de los algoritmos de este nivel.

La intuición

Empieza en un nodo y métele en una queue. Ahora repite: toma el nodo del frente de la queue y, por cada vecino que no hayas visto antes, márcalo como visto y agrégalo al final de la queue. Como la queue es primero en entrar, primero en salir, procesas los nodos exactamente en el orden en que los descubriste, lo que significa que todos los vecinos inmediatos del inicio (distancia

1. salen antes que cualquiera de sus vecinos (distancia 2), que a su vez salen antes que los de distancia 3, y así. BFS barre el grafo en anillos concéntricos de distancia.

De ese orden sale la garantía del camino más corto. La primera vez que BFS llega a un nodo, tuvo que ser por un camino más corto, porque BFS explora todas las distancias menores antes que las mayores: no hay manera de llegar a un nodo en menos pasos que el anillo en el que aparece por primera vez. Guarda quién descubrió a cada nodo (su "padre") y puedes recorrer esos padres hacia atrás desde cualquier destino para recuperar el camino más corto real.

Complejidad: cómo escala

BFS es $O(V + E)$ en tiempo: cada vértice se encola y se desencola exactamente una vez, y cada arista se examina una vez (cuando se procesa su origen). El espacio es $O(V)$ para la queue y los marcadores de visitado/distancia. Ese costo lineal es gracias a que corre sobre una lista de adyacencia: sobre una matriz, encontrar los vecinos de cada nodo costaría O(V), y todo el asunto se volvería O(V²). El duelo no compite en velocidad (los dos recorridos son O(V+E)); lo que compara es la calidad del camino que encuentra cada uno, porque eso es lo que los distingue:

En grafos aleatorios de 400 vértices, BFS encontró caminos de 5.2 aristas en promedio, mientras que DFS encontró caminos de 53 en promedio: más de 10 veces más largos, para el mismo origen y destino. Esa brecha es justo el punto: los dos recorridos llegan al destino, pero solo BFS llega de forma óptima. El camino de DFS es un camino, que se fue por la rama que le tocó; el de BFS es el más corto. Cuando importan los "mínimos pasos", esta es la diferencia entre una respuesta correcta y una nada más válida.

En qué es bueno y en qué no

BFS es la herramienta correcta para caminos más cortos en grafos sin pesos y para cualquier cosa con forma de "mínimos pasos": resolver laberintos, acertijos de escaleras de palabras, grados de separación en una red social, el mínimo número de movimientos en un juego, exploración de lo más cercano primero. También es la opción natural cuando quieres procesar un grafo nivel por nivel, o encontrar el nodo más cercano que cumpla alguna condición, porque llega a lo cercano antes que a lo lejano. Y es simple, lineal y óptimo garantizado para estos problemas.

Donde BFS deja de ser óptimo es en grafos con pesos. En el momento en que las aristas tienen costos distintos —una red de carreteras donde los caminos tienen longitudes, una red donde los enlaces tienen latencias— "menos aristas" ya no es "menor distancia", y la garantía de BFS se evapora: la ruta con menos saltos puede ser mucho más larga que una ruta de muchos saltos hecha de aristas cortas. Ese es el problema que resuelve el algoritmo de Dijkstra, más adelante en este nivel, cambiando la queue simple de BFS por una priority queue. BFS también usa memoria O(V) para su frontera, que en grafos muy anchos puede ser bastante; el stack de DFS suele ser más superficial. Pero para caminos más cortos sin pesos, BFS es exactamente lo que necesitas.

Los datos, o las entradas

El duelo corre BFS y DFS sobre grafos aleatorios y compara la longitud del camino que encuentra cada uno entre pares aleatorios, aislando la optimalidad de camino más corto de BFS. La animación corre BFS sobre un grafo de rejilla pequeño desde la esquina superior izquierda, para que veas la frontera expandirse en anillos limpios de distancia.

Constrúyelo, una función a la vez

El recorrido central: una queue, marcando la distancia al descubrir.

def bfs(adj, start, probe=None):
    """Explore the graph breadth-first from `start` using a QUEUE. Mark a node's distance
    the moment it's discovered and enqueue it; process the queue front to back. Every node
    is enqueued once, and its recorded distance is the shortest (fewest-edge) distance from
    the start. O(V + E): each vertex and edge is touched once. Returns the visit order and
    the distance array."""
    n = len(adj)
    dist = [-1] * n
    dist[start] = 0
    order = []
    q = deque([start])
    while q:
        u = q.popleft()
        order.append(u)
        if probe is not None:
            probe.append({"node": u, "dist": dist[u], "frontier": list(q)})
        for v in adj[u]:
            if dist[v] == -1:              # first time we've seen v → this is its shortest distance
                dist[v] = dist[u] + 1
                q.append(v)
    return order, dist

Y la reconstrucción del camino más corto: el mismo BFS recordando padres, y luego recorriéndolos hacia atrás.

def shortest_path(adj, start, target):
    """Reconstruct a shortest (fewest-edge) path. Same BFS, but remember each node's parent
    (who discovered it); then walk parents back from the target. This is how BFS powers
    maze solving, social 'degrees of separation', and any unweighted shortest path."""
    n = len(adj)
    dist = [-1] * n
    parent = [-1] * n
    dist[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                parent[v] = u
                q.append(v)
    if dist[target] == -1:
        return None                        # target unreachable
    path, x = [], target
    while x != -1:
        path.append(x)
        x = parent[x]
    return path[::-1]

Míralo funcionar

Aquí está BFS explorando una rejilla de 2×4 desde el nodo 0. Naranja es el nodo que se está procesando en este momento; los nodos azules son la frontera (descubiertos, esperando en la queue); los verdes ya están listos; los oscuros aún no se descubren. Avanza paso a paso y observa la ola: desde el 0, descubre a sus vecinos 1 y 4 (distancia 1) y los encola; luego los procesa y descubre los nodos de distancia 2; y así. La frontera azul siempre es exactamente el anillo de la distancia actual, barriendo hacia afuera. Como ese anillo llega a los nodos cercanos antes que a los lejanos, el primer descubrimiento de cada nodo va sobre un camino más corto: la garantía, hecha visible.

El código completo

Las dos versiones en un solo lugar: cambia entre ellas. La pestaña "desde cero" es BFS y su reconstrucción de camino más corto. La pestaña de librería es el DFS contra el que se compara —el recorrido que también visita todo pero no encuentra caminos más cortos— más un BFS de referencia. (La librería de grafos de verdad es networkx; Python no trae recorridos de grafos integrados.)

"""Breadth-first search — the graph traversal that explores in waves of increasing
distance from the start, and the first algorithm most graph problems reduce to.

Its engine is the queue from the linear-structures tier. Because a queue serves nodes in
the order they were discovered (first in, first out), BFS finishes everything one edge
away before it touches anything two edges away, and so on outward. That ordering has a
powerful consequence: the first time BFS reaches a node, it has reached it by a SHORTEST
path — the fewest edges possible. So BFS isn't just a way to visit every node; on an
unweighted graph it's the shortest-path algorithm.
"""
from collections import deque


# region: bfs
def bfs(adj, start, probe=None):
    """Explore the graph breadth-first from `start` using a QUEUE. Mark a node's distance
    the moment it's discovered and enqueue it; process the queue front to back. Every node
    is enqueued once, and its recorded distance is the shortest (fewest-edge) distance from
    the start. O(V + E): each vertex and edge is touched once. Returns the visit order and
    the distance array."""
    n = len(adj)
    dist = [-1] * n
    dist[start] = 0
    order = []
    q = deque([start])
    while q:
        u = q.popleft()
        order.append(u)
        if probe is not None:
            probe.append({"node": u, "dist": dist[u], "frontier": list(q)})
        for v in adj[u]:
            if dist[v] == -1:              # first time we've seen v → this is its shortest distance
                dist[v] = dist[u] + 1
                q.append(v)
    return order, dist
# endregion


# region: shortest_path
def shortest_path(adj, start, target):
    """Reconstruct a shortest (fewest-edge) path. Same BFS, but remember each node's parent
    (who discovered it); then walk parents back from the target. This is how BFS powers
    maze solving, social 'degrees of separation', and any unweighted shortest path."""
    n = len(adj)
    dist = [-1] * n
    parent = [-1] * n
    dist[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                parent[v] = u
                q.append(v)
    if dist[target] == -1:
        return None                        # target unreachable
    path, x = [], target
    while x != -1:
        path.append(x)
        x = parent[x]
    return path[::-1]
# endregion

"""The graph library is the third-party `networkx` (`nx.shortest_path`, `nx.bfs_edges`) —
no graph traversal in the standard library. To show what makes BFS special rather than just
correct, the counterpart here is depth-first search (next chapter's algorithm), which visits
every node too but does NOT find shortest paths: it plunges deep, so the path it discovers to
a node can be far longer than necessary. The face-off compares the path lengths the two
traversals find, and BFS's optimality is the point.
"""
from collections import deque


# region: dfs_path
def dfs_path(adj, start, target):
    """A path from start to target via depth-first search (an explicit stack). It finds *a*
    path if one exists, but not the shortest — DFS follows one branch as far as it goes, so
    it can reach the target by a long detour. Contrast with BFS's shortest path."""
    n = len(adj)
    visited = [False] * n
    parent = [-1] * n
    stack = [start]
    visited[start] = True
    while stack:
        u = stack.pop()
        if u == target:
            break
        for v in adj[u]:
            if not visited[v]:
                visited[v] = True
                parent[v] = u
                stack.append(v)
    if not visited[target]:
        return None
    path, x = [], target
    while x != -1:
        path.append(x)
        x = parent[x]
    return path[::-1]
# endregion


# region: bfs_reference
def bfs_distances_reference(adj, start):
    """A plain BFS distance computation, as an independent reference to check against."""
    n = len(adj)
    dist = [-1] * n
    dist[start] = 0
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist
# endregion

Desde cero vs. librería

Aquí la comparación no es de velocidad —BFS y DFS son los dos O(V+E)— sino de una corrección de otro tipo: la calidad de la respuesta. Los caminos de DFS fueron 10× más largos que los de BFS sobre los mismos grafos, que es la ilustración más nítida posible de que dos algoritmos con la misma complejidad pueden dar respuestas radicalmente distintas a la misma pregunta. Elegir BFS sobre DFS para un problema de camino más corto no es una optimización; es la diferencia entre correcto e incorrecto. Esto replantea lo que significa "qué algoritmo": a veces eliges por velocidad, pero muchas veces, como aquí, eliges porque un algoritmo tiene una propiedad que el otro no tiene —la garantía de camino más corto de BFS— y ninguna cantidad de tuning le da esa propiedad a DFS. Empata el algoritmo con la garantía que necesitas, no nada más con la cota de tiempo.

Dónde te lo vas a encontrar

BFS corre en todos lados donde la pregunta es "mínimos pasos". Las redes sociales calculan grados de separación y distancias para sugerencias de amigos con él. El GPS y los videojuegos lo usan para caminos más cortos en rejillas sin pesos, y es el esqueleto de los buscadores de rutas con pesos (Dijkstra, A*) que mueven la navegación real. Los web crawlers exploran en anchura para llegar primero a las páginas cercanas importantes. El broadcast en redes y el flood-fill (la herramienta de bote de pintura) son BFS. Los recolectores de basura rastrean objetos alcanzables con él. Los ruteadores de diseño de chips usan el algoritmo de laberinto original de Moore y Lee. Y un montón de acertijos —el cubo de Rubik en mínimos movimientos, escaleras de palabras, fichas deslizantes— son BFS sobre un grafo de estados. Cuando necesites la cadena de pasos más corta, BFS es la primera herramienta a la que debes echar mano.

Puntos clave

La búsqueda en anchura explora un grafo en anillos de distancia creciente usando una queue, visita cada nodo alcanzable en $O(V+E)$ y —porque el orden FIFO llega a cada nodo primero por la menor cantidad de aristas— encuentra caminos más cortos en grafos sin pesos. Su garantía de camino más corto, no su velocidad, es lo que la vuelve la opción correcta, y viene por completo de la queue: métele un stack y obtienes búsqueda en profundidad, lo más profundo primero en lugar de lo más cercano primero.

Ese hermano basado en stack es el siguiente capítulo. La búsqueda en profundidad se lanza por cada rama hasta el final antes de retroceder, lo que la hace peor para caminos más cortos pero mejor para otro conjunto de preguntas: detectar ciclos, ordenar dependencias, encontrar componentes conexas y puntos de articulación. Entre la anchura de BFS y la profundidad de DFS tienes los dos lentes con los que cada algoritmo de grafos de este nivel mira un grafo.