Overview
La búsqueda en anchura (BFS) explora un grafo nivel por nivel, visitando todos los vecinos de un nodo antes de avanzar al siguiente nivel.
Analogy
Como las ondas en el agua: cuando tiras una piedra, las ondas se expanden en círculos concéntricos, tocando cada punto a su distancia mínima.
Step-by-step
- Añade el nodo de inicio a una cola
- Mientras la cola no esté vacía: saca el frente
- Visita todos sus vecinos no visitados y los añade a la cola
- Marca los nodos como visitados para evitar repeticiones
Visual
1
/ \
2 3
/ \
4 5
BFS: 1 → 2 3 → 4 5
Common mistakes
- No marcar los nodos como visitados → bucle infinito
- Usar pila en lugar de cola → se convierte en DFS
Practice questions
- Encuentra el camino más corto en un laberinto
- Comprueba si un grafo es bipartito con BFS
Time
O(V+E) — vertices más aristas
Space
O(V) — para la cola y el conjunto visitado