El algoritmo BFS (Breadth First Search) te permite recorrer un grafo, árbol o matriz moviéndote a lo ancho en lugar de profundizar. Si ya dominas DFS, esta técnica te abre otra forma de explorar relaciones entre nodos, ideal cuando la jerarquía importa más que la profundidad.

¿Qué significa recorrer un grafo a lo ancho con BFS?

La idea central de BFS es avanzar por niveles. Imagina un árbol binario: empiezas en la raíz y, en lugar de bajar hasta el final por una rama, primero revisas todos los nodos del siguiente nivel antes de pasar al siguiente.

En la práctica, esto se traduce en un recorrido jerárquico. Si un nodo está más arriba, tiene prioridad. Y aquí viene lo interesante: no importa cuántos hijos tenga ese nodo, primero terminas de revisar a todos los que están en su mismo nivel.

¿Qué es BFS? Es un algoritmo que recorre un grafo o árbol por niveles, empezando por la raíz y revisando todos los nodos de un mismo nivel antes de bajar al siguiente.

¿En qué se diferencia BFS de DFS al recorrer nodos?

La diferencia clave está en la prioridad. Mientras DFS profundiza por una rama hasta el final, BFS se mueve a lo ancho respetando la altura de cada nodo.

• DFS prioriza profundidad: baja hasta el fondo de una rama antes de regresar.
• BFS prioriza jerarquía: revisa primero los nodos más cercanos a la raíz.
• Ambos terminan recorriendo todo el árbol o grafo, pero en orden distinto.

Piensa en una corona: lo que está más arriba pesa más. En BFS, los nodos de mayor jerarquía se revisan primero, y solo cuando terminas con ellos pasas a los de menor nivel.

¿Cuándo conviene usar BFS en lugar de DFS?

BFS es útil cuando necesitas encontrar el camino más corto en términos de niveles, explorar relaciones cercanas antes que lejanas, o trabajar con jerarquías donde la cercanía a la raíz es lo que importa.

¿Cuál es la complejidad temporal de BFS?

La complejidad temporal de BFS es la misma que la de DFS, porque también iteras por todo el árbol o grafo. Lo único que cambia es el orden en que visitas los nodos.

En notación Big O, la complejidad es O(V + E), donde V es el número de nodos (vertices) y E es el número de aristas (edges), es decir, las relaciones entre nodos.

¿Cuál es la complejidad de BFS? Es O(V + E), donde V son los nodos y E las aristas. Recorres cada nodo y cada relación una sola vez.

Esto significa que el costo no depende de si vas a lo ancho o a lo profundo, sino de cuántos elementos y conexiones tiene tu estructura.

Conceptos clave que aparecen en BFS

Para dominar este algoritmo conviene tener claros algunos términos que se mencionan en el recorrido.

• Nodo o vertex: cada elemento dentro del grafo o árbol.
• Arista o edge: la relación o conexión entre dos nodos.
• Raíz: el nodo inicial desde donde arranca el recorrido en un árbol.
• Nivel: el conjunto de nodos que están a la misma distancia de la raíz.
• Jerarquía: el criterio de prioridad que usa BFS para decidir qué nodo revisar primero.

Con estos conceptos en mente, el siguiente paso natural es ver cómo se traduce esta lógica en código. ¿Te animas a implementarlo y compartir tu versión en los comentarios?