21. Recorrido en anchura (BFS)

21.1 Introducción

El recorrido en anchura, conocido como BFS por Breadth-First Search, es uno de los algoritmos fundamentales para explorar grafos. A diferencia de DFS, que profundiza por una rama, BFS examina primero todos los vecinos inmediatos del origen.

Luego visita los vértices situados a dos aristas de distancia, después los que se encuentran a tres y así sucesivamente. Esta organización permite calcular caminos mínimos en grafos sin pesos.

21.2 Idea fundamental

BFS repite cuatro acciones:

1. Elegir un vértice de origen, marcarlo como visitado y encolarlo.
2. Retirar el primer vértice de la cola.
3. Examinar todos sus vecinos todavía no visitados.
4. Marcar y encolar cada vecino nuevo.

El proceso termina cuando la cola queda vacía. En ese momento se han visitado todos los vértices alcanzables desde el origen.

21.3 La cola FIFO

BFS utiliza una cola, una estructura FIFO: el primer elemento que entra es el primero que sale (First In, First Out).

Si desde A se descubren B, C y D en ese orden, la cola garantiza que B se procese antes que C y C antes que D. Los vértices de un nivel se procesan antes de comenzar el nivel siguiente.

21.4 Exploración por niveles

El nivel de un vértice es la cantidad mínima de aristas necesarias para llegar hasta él desde el origen. El origen pertenece al nivel 0, sus vecinos al nivel 1 y los vecinos nuevos de estos al nivel 2.

Los vértices de un mismo nivel pueden cambiar de orden según cómo estén almacenados los vecinos, pero nunca se procesa un nivel posterior antes de finalizar los anteriores.

21.5 Simulación interactiva: BFS paso a paso

Selecciona un nodo como origen y pulsa Iniciar. Avanza paso a paso para observar la cola, el orden de visita, las distancias y las aristas del árbol BFS.

Verde indica los vértices pendientes en la cola; celeste, los ya procesados; rosa, el vértice actual. El número de cada nodo representa su distancia al origen.

21.6 Cuándo se marca un vértice

Un vértice debe marcarse como visitado en el momento de encolarlo, no cuando se lo retira de la cola. Así se evita que dos vértices distintos encolen al mismo vecino.

Marcar al desencolar puede generar duplicados, desperdiciar memoria y dificultar la construcción correcta del árbol BFS.

21.7 Árbol BFS

Cuando BFS descubre un vértice nuevo, registra la arista por la que llegó a él. Esas aristas forman un árbol con raíz en el origen.

El padre de cada vértice se encuentra en el nivel inmediatamente anterior. Por eso el camino desde la raíz hasta cualquier nodo del árbol utiliza la menor cantidad posible de aristas.

21.8 Caminos mínimos sin pesos

En un grafo no ponderado, o cuando todas las aristas tienen el mismo costo, BFS encuentra caminos mínimos en cantidad de aristas. La primera vez que se descubre un vértice se ha encontrado una ruta de longitud mínima hasta él.

Para reconstruir esa ruta se guarda el padre de cada nodo y se retrocede desde el destino hasta el origen.

Esta propiedad no se aplica directamente cuando las aristas tienen costos diferentes. En ese caso se necesitan algoritmos como Dijkstra o Bellman-Ford.

21.9 Grafos desconectados

Una ejecución de BFS solo alcanza la componente que contiene al origen. Para recorrer todo un grafo desconectado debemos iniciar otra búsqueda desde cada vértice que continúe sin visitar.

Las aristas de descubrimiento forman entonces un bosque BFS, compuesto por un árbol para cada componente conexa.

21.10 Implementación de BFS en JavaScript

function bfs(grafo, origen) {
  const visitados = new Set([origen]);
  const cola = [origen];
  const orden = [];

  while (cola.length > 0) {
    const actual = cola.shift();
    orden.push(actual);

    for (const vecino of grafo[actual]) {
      if (!visitados.has(vecino)) {
        visitados.add(vecino); // marcar al encolar
        cola.push(vecino);
      }
    }
  }
  return orden;
}

const grafo = {
  A: ["B", "C"], B: ["A", "D"],
  C: ["A", "D"], D: ["B", "C"]
};

console.log(bfs(grafo, "A")); // A, B, C, D

shift() facilita la explicación, pero desplaza los elementos del arreglo. Para colas grandes es más eficiente conservar un índice que indique el frente.

21.11 Distancias, padres y reconstrucción del camino

function caminoMinimoBFS(grafo, origen, destino) {
  const cola = [origen];
  const padre = new Map([[origen, null]]);
  let frente = 0;

  while (frente < cola.length) {
    const actual = cola[frente++];
    if (actual === destino) break;

    for (const vecino of grafo[actual]) {
      if (!padre.has(vecino)) {
        padre.set(vecino, actual);
        cola.push(vecino);
      }
    }
  }

  if (!padre.has(destino)) return null;

  const camino = [];
  for (let nodo = destino; nodo !== null; nodo = padre.get(nodo)) {
    camino.push(nodo);
  }
  return camino.reverse();
}

El mapa padre cumple dos funciones: indica qué vértices fueron descubiertos y permite reconstruir el camino. Si el destino no aparece en el mapa, no es alcanzable desde el origen.

21.12 Complejidad y aplicaciones

Con listas de adyacencia, cada vértice se encola una sola vez y cada arista se examina una cantidad constante de veces. Por ello el tiempo es O(V + E) y el espacio adicional es O(V).

21.13 BFS y DFS: diferencias

Ninguno es universalmente mejor. La elección depende de si interesa explorar por cercanía, profundizar rápidamente o aprovechar una propiedad específica del problema.

21.14 Errores comunes

• Utilizar una pila y obtener accidentalmente un recorrido DFS.
• Marcar los vértices al desencolarlos en lugar de al encolarlos.
• Olvidar el conjunto de visitados y repetir vértices indefinidamente.
• Suponer que el orden dentro de un mismo nivel es único.
• Aplicar BFS directamente a aristas con costos diferentes.
• Recorrer solo una componente de un grafo desconectado.
• Usar repetidamente shift() en colas muy grandes sin considerar su costo.

21.15 Qué debes recordar de este tema

• BFS explora el grafo por niveles desde un origen.
• Utiliza una cola FIFO.
• Los vértices deben marcarse al ser encolados.
• Encuentra caminos mínimos en grafos sin pesos.
• Las aristas de descubrimiento forman un árbol BFS.
• Desde un origen solo recorre su componente conexa.
• Con listas de adyacencia su complejidad es O(V + E).

21.16 Conclusión

BFS organiza la exploración según la distancia al origen. La cola preserva el orden de los niveles y convierte al algoritmo en una herramienta natural para conectividad, rutas mínimas sin pesos y procesos que avanzan por rondas.

En el próximo tema estudiaremos el ordenamiento topológico, que organiza los vértices de un grafo dirigido respetando sus dependencias.