Cómo funciona
BFS (breadth-first search, búsqueda en anchura) guarda en una cola las
celdas vistas pero aún no expandidas. Saca siempre la primera, mira sus vecinos (norte, este, sur y
oeste) y mete al final los que no había visto, a una distancia más y recordando de dónde vienen.
Como la cola respeta el orden de llegada, las celdas salen en orden de distancia:
primero todas las que están a 1 paso, luego las de 2… La búsqueda avanza como una onda, y la primera
vez que el destino sale de la cola se ha llegado por el camino con menos pasos.
Paso a paso: de A3 a G3
Un mapa de 7 × 5 con muros en C2–E2, E3–E4 y C4–C5. Las columnas son letras y las filas, números.
- 01Saco A3 (d = 0): entran A2, B3 y A4 a d = 1. Cola:
[A2, B3, A4].
- 02Capa d = 1: A2 aporta A1 y B2; B3, C3 y B4; A4, A5. Cuando se vacía la capa, la cola contiene la capa d = 2 completa:
[A1, B2, C3, B4, A5].
- 03La onda rodea los muros por arriba y por abajo. G3 sale de la cola con d = 10, tras expandir las 28 celdas libres: es la más lejana del mapa.
- ΣCamino de 10 pasos: A3 → A2 → A1 → … → G1 → G2 → G3. Hay 12 caminos distintos de 10 pasos; BFS devuelve el primero que encuentra según el orden norte, este, sur, oeste.
Cuándo sirve
BFS encuentra el camino más corto en número de pasos: vale cuando todos los
movimientos cuestan lo mismo. Si unas casillas cuestan más que otras (barro, cuestas), el camino con
menos pasos puede no ser el más barato; para eso está Dijkstra. Su punto débil es la memoria: la cola
guarda todo el frente de la onda a la vez.
Complejidad
- Tiempo
- O(V + E)
- Memoria
- O(V)
- Estructura
- Cola FIFO
- Óptimo
- Sí, sin pesos
- Completo
- Sí
- En una rejilla
- V celdas, E ≤ 4V