Búsqueda en Anchura (BFS) explora un grafo capa por capa desde un nodo fuente, como una onda que se expande en el agua. Es el algoritmo de referencia para “¿qué tan lejos está todo desde aquí?” en grafos no ponderados.
Funciona manteniendo una cola FIFO de vecinos pendientes: primero en llegar, primero en salir. Eso garantiza que siempre visitas todos los nodos en la distancia d antes de tocar cualquier nodo en la distancia d+1.
Cómo Funciona
- Inicializa: coloca la fuente en una cola, márcala como visitada.
- Saca el frente de la cola; ese es el nodo actual.
- Visita a cada vecino no visitado: márcalo, registra su padre/distancia, y mételo en la cola.
- Repite hasta que la cola esté vacía.
Idea Clave
La cola es la garantía: al procesar nodos en orden de llegada, BFS naturalmente descubre el camino más corto en número de aristas desde la fuente. Si llegas a un nodo por primera vez, esa trayectoria no puede ser superada porque cualquier ruta alternativa pasaría por más nodos intermedios.
Ejemplo Trabajado
Fuente S en el visualizador:
| Ronda | Frente de cola | Vecinos añadidos | Distancia |
|---|---|---|---|
| 1 | S | A, B | S=0 |
| 2 | A | C, D | A=1 |
| 3 | B | E | B=1 |
| 4 | C | F | C=2 |
| 5 | D | — | D=2 |
| 6 | E | G | E=2 |
| 7 | F | — | F=3 |
| 8 | G | — | G=3 |
Resultado: distancias por niveles S=0, A=B=1, C=D=E=2, F=G=3. Observa el visualizador expandir el grafo en ondas concéntricas.
Casos Extremos y Trampas
- Grafos con ciclos — el conjunto de visitados previene bucles infinitos.
- Grafos desconectados — los nodos inalcanzables nunca se encolan; reporta
∞. - Grafos muy ramificados — la cola puede crecer hasta
O(V)en el peor caso. - Grafos ponderados — BFS no garantiza caminos más cortos cuando las aristas tienen peso; usa Dijkstra.
Comparación con DFS
| Aspecto | BFS | DFS |
|---|---|---|
| Estructura | Cola (FIFO) | Pila (LIFO / recursión) |
| Camino más corto | Sí (no ponderado) | No |
| Uso de memoria | O(V) en peor caso | O(h) donde h es la altura |
| Natural para | Caminos mínimos, niveles | Backtracking, ciclos, topológico |
Aplicaciones
- Redes sociales — grados de separación, amigos de amigos
- Enrutamiento — saltos mínimos en redes no ponderadas
- IA / juegos — expansión de nodos en grid (p. ej., pathfinding 4-direcciones)
- Verificación de bipartitos — coloreo por niveles detecta aristas intra-nivel
Trayectoria de Práctica
- Ejecuta BFS a mano desde S en el grafo del visualizador, registrando la cola después de cada extracción.
- Explica por qué BFS encuentra el camino más corto en número de aristas, pero no necesariamente en peso.
- Marca cada nodo con su nivel y argumenta por qué dos nodos del mismo nivel nunca pueden ser adyacentes en un grafo bipartito.
- Extiende BFS para reconstruir el camino real desde S hasta cualquier nodo usando punteros padre.