Búsqueda en anchura (BFS)
Explora en oleadas de distancia creciente, usando una queue.
El primero en llegar a un nodo = camino más corto.
La queue es lo que da el camino más corto
- Toma del frente, agrega los vecinos al final (FIFO)
- Termina la distancia d antes de tocar la distancia d+1
- Primer descubrimiento de un nodo = menos aristas = camino más corto
- Cambia queue → stack y se convierte en DFS
Observa la frontera expandirse
Naranja = procesando · azul = frontera (en la queue) · verde = listo.
El anillo azul barre hacia afuera por distancia.
BFS es óptimo; DFS no
Mismo grafo, mismos pares: camino de BFS 5.2 aristas, DFS 53 → 10× más largo. O(V+E) los dos.
El detalle: solo sin pesos
- Aristas con peso → menos saltos ≠ menor distancia → usa Dijkstra
- Dijkstra = BFS con una priority queue
- Marca visitado al ENCOLAR, no al desencolar
Para llevar
Elige por la garantía, no nada más por la cota de tiempo.
El camino más corto de BFS es una propiedad en la que DFS no se puede convertir a base de tuning. Sigue: DFS.