BFS

Tema: Grafos · temarios: Syllabus OCI · Syllabus IOI

📍 Dónde se aprende: módulo 15 de la Ruta de Aprendizaje.

El problema: llegar con la menor cantidad de pasos

Imagina estaciones conectadas por pasillos. Cada pasillo cuesta un paso: queremos saber cuántos pasos separan la estación A de cada una de las demás. Probar todos los caminos repite trabajo y, si hay ciclos, puede continuar indefinidamente.

La idea de BFS es explorar por distancia: primero A, después todas las estaciones a un paso, luego las que están a dos. Una cola conserva ese orden: lo que descubrimos primero se procesa primero. Si necesitas repasar esa operación, mira stack y queue.

Ver cómo crece la búsqueda

Las líneas del dibujo son conexiones en ambos sentidos, todas con costo 1. F está aislada. Los niveles se miden desde A.

Nivel 0Nivel 1Nivel 2Nivel 3ABCDEFSin camino desde A

Si el diagrama no cabe, deslízalo horizontalmente.

Usaremos este orden de vecinos: en A, B antes que C; en B, A antes que D; en C, A antes que D; en D, B, C y E. El frente de la cola está a la izquierda.

Estación que procesamosQué descubrimosCola después de procesarla
InicioA tiene distancia 0A
AB y C tienen distancia 1B, C
BD tiene distancia 2C, D
CD ya fue descubierta; no se agrega otra vezD
DE tiene distancia 3E
ENo hay estaciones nuevasvacía

El resultado, en orden A, B, C, D, E, F, es 0, 1, 1, 2, 3, −1. El −1 significa que no existe un camino desde A. Cambiar el orden de vecinos puede cambiar el orden dentro de un nivel, pero no estas distancias.

Por qué la primera llegada es la mejor

Al sacar una estación de distancia d, todas las estaciones de distancias menores ya se procesaron. Sus vecinas nuevas quedan al final de la cola con distancia d + 1, después de las estaciones pendientes del nivel actual. Por eso nunca procesamos el nivel siguiente antes de terminar el anterior.

Si hubiera un camino más corto hacia una vecina nueva, su penúltima estación habría sido procesada antes y ya la habría descubierto. Esta es la razón para guardar su distancia al encolarla, sin esperar a sacarla.

Cada vértice entra en la cola a lo sumo una vez. Se revisa cada lista de vecinos una vez: el tiempo es O(V + E) y la memoria adicional O(V), sin contar el grafo. En un grafo no dirigido cada arista aparece dos veces; eso no cambia el orden de complejidad.

Implementación y relación con el ejemplo

vector<int> bfs(int s, const vector<vector<int>>& g) {
    vector<int> dist(g.size(), -1);
    queue<int> q;
    dist[s] = 0; q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
    return dist;
}

Numera A…F como 0…5 y usa las listas de vecinos {{1,2}, {0,3}, {0,3}, {1,2,4}, {3}, {}}. La llamada bfs(0, g) devuelve {0,1,1,2,3,-1}.

dist tiene dos funciones: guarda la respuesta y registra qué estaciones ya descubrimos. La condición dist[v] == -1 evita que C vuelva a encolar D. El origen s debe ser un índice válido y todos los vecinos deben pertenecer al grafo.

Cuándo sirve y cuándo cambia el problema

BFS sirve en grafos sin pesos y en grillas donde cada movimiento permitido cuesta lo mismo. En una grilla, una celda es un vértice y sus vecinos son las celdas a las que puedes moverte.

Si A–B cuesta 10 y A–C–B cuesta 1 + 1, el camino con menos aristas ya no es el más barato. El BFS anterior elegiría una arista para B; para pesos no negativos usa Dijkstra. Con pesos solamente 0 y 1 existe la variante 0–1 BFS, que cambia la cola por una deque y también cambia la relajación.

Para practicar con problemas, continúa en 15 - Grafos I - BFS y DFS.