BFS — Algoritmo de búsqueda en anchura explicado

La búsqueda en anchura, o BFS, es un algoritmo de grafos que visita los nodos según su distancia desde un nodo inicial. Revisa primero todos los nodos que están a una arista de distancia antes de pasar a los que están a dos aristas, luego a tres, y así sucesivamente.

Ese orden por capas es la idea clave. Si el grafo es no ponderado, o si todas las aristas tienen el mismo costo, BFS también da la longitud del camino más corto desde el nodo inicial hasta cada nodo alcanzable.

Qué hace la búsqueda en anchura

BFS usa una cola, que es una lista de primero en entrar, primero en salir. La cola es lo que mantiene el orden por capas: los nodos descubiertos antes se procesan antes.

El patrón habitual es:

• marcar el nodo inicial como visitado
• ponerlo en la cola
• sacar el nodo del frente
• añadir cada vecino no visitado al final de la cola
• repetir hasta que la cola esté vacía

Si además guardas el padre de cada nodo, puedes reconstruir un camino más corto cuando termine la búsqueda.

Por qué la cola crea capas

Supón que el nodo $A$ es el inicial. Sus vecinos directos están a distancia $1$ de $A$, así que entran primero en la cola. Solo después de procesar esos nodos entran sus vecinos no visitados, lo que significa que la siguiente ola está a distancia $2$.

Por eso BFS agrupa de forma natural los nodos según su distancia al inicio. No está estimando qué camino es corto. La cola obliga a que la búsqueda termine todos los caminos con menos aristas antes de considerar los más largos.

Ejemplo de BFS: encontrar el camino más corto por número de aristas

Usa este grafo:

$$A \to \{B, C\}, \qquad B \to \{D\}, \qquad C \to \{E\}, \qquad D \to \{F\}, \qquad E \to \{F\}$$

Empieza en $A$. La cola cambia así:

$$[A] \to [B, C] \to [C, D] \to [D, E] \to [E, F] \to [F]$$

Esto es lo que significa:

Primero, procesa $A$ y luego añade $B$ y $C$. Después, procesa $B$ y luego $C$, lo que añade $D$ y $E$. Tras eso, procesa $D$ y $E$, con lo que se llega a $F$.

Así que el orden de visita de BFS es:

$$A,\ B,\ C,\ D,\ E,\ F$$

Las distancias desde $A$ son:

$$\operatorname{dist}(A)=0,\quad \operatorname{dist}(B)=1,\quad \operatorname{dist}(C)=1,\quad \operatorname{dist}(D)=2,\quad \operatorname{dist}(E)=2,\quad \operatorname{dist}(F)=3$$

Esto muestra la ventaja principal. BFS llega a $F$ con distancia $3$, así que el camino más corto de $A$ a $F$ usa $3$ aristas. Un camino más corto es $A \to B \to D \to F$. Otro es $A \to C \to E \to F$.

Errores comunes en BFS

Suponer que BFS siempre encuentra el camino más barato

Eso solo es cierto cuando todas las aristas tienen el mismo costo, o cuando el grafo se trata como no ponderado. Si las aristas tienen pesos distintos, BFS puede encontrar un camino con menos aristas pero con un costo total mayor.

Marcar un nodo demasiado tarde

En BFS estándar, un nodo normalmente se marca como visitado cuando se encola, no cuando se saca después. Eso evita que el mismo nodo se añada a la cola muchas veces.

Confundir BFS con DFS

BFS explora por capas. La búsqueda en profundidad, o DFS, sigue una rama antes de retroceder. Cada una responde bien a tipos de preguntas diferentes.

Olvidar que el orden puede depender del orden de los vecinos

El orden exacto de visita dentro de una misma capa puede cambiar según cómo estén listados los vecinos. Las garantías sobre la distancia se mantienen, pero el recorrido puede variar.

Cuándo se usa la búsqueda en anchura

BFS es útil cuando te importa la alcanzabilidad, el recorrido por niveles en árboles o las longitudes de caminos más cortos medidas por número de aristas.

También aparece en problemas de espacio de estados donde cada movimiento tiene el mismo costo. En esa condición, BFS suele ser la forma más clara de encontrar el número mínimo de movimientos.

Una forma sencilla de recordar BFS

Piensa en BFS como una onda que se expande hacia afuera desde el nodo inicial. Cada paso de la onda añade una arista más de distancia.

Para probar tu propia versión, dibuja un grafo pequeño, elige un nodo inicial y escribe la cola después de cada paso. Si quieres ir más allá, resuelve un problema parecido de recorrido de grafos y comprueba si la afirmación sobre el camino más corto sigue siendo válida cuando el grafo es ponderado.