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.
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 procesamos | Qué descubrimos | Cola después de procesarla |
|---|---|---|
| Inicio | A tiene distancia 0 | A |
| A | B y C tienen distancia 1 | B, C |
| B | D tiene distancia 2 | C, D |
| C | D ya fue descubierta; no se agrega otra vez | D |
| D | E tiene distancia 3 | E |
| E | No hay estaciones nuevas | vací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.
¿Qué pasa si también conectamos B con E?
Al procesar B se descubren D y E, ambas a distancia 2. Cuando llegue el turno de D, E ya tendrá distancia. La nueva arista reduce la distancia a E de 3 a 2; la cola permite encontrarlo sin enumerar los caminos completos.
Para practicar con problemas, continúa en 15 - Grafos I - BFS y DFS.