Recorrer un árbol o grafo de forma ordenada por niveles es una de las técnicas fundamentales en estructuras de datos y algoritmos. Aquí se explica cómo implementar BFS (Breadth-First Search) usando colas en Python, cómo contar niveles y cómo adaptar la solución tanto para árboles binarios como n-arios.
¿Cómo funciona BFS con colas?
El algoritmo BFS recorre una estructura nivel por nivel, comenzando desde la raíz. La clave está en utilizar una cola (queue), que sigue el principio FIFO: el primer elemento en entrar es el primero en salir. Esto contrasta con DFS (Depth-First Search), que usa pilas (stacks) [0:44].
La idea central es la siguiente:
Se inicia colocando la raíz dentro de la cola.
Mientras la cola tenga elementos, se extraen todos los nodos del nivel actual.
Por cada nodo extraído, se agregan sus hijos a la cola para ser procesados en la siguiente iteración.
Cuando la cola queda vacía, significa que ya se visitaron todos los nodos.
¿Cómo se estructura el código en Python?
Primero se crea una función llamada bfs que recibe la raíz como entrada. Si la raíz no existe, se retorna una lista vacía de inmediato [1:07].
python
def bfs(raiz):
if not raiz:
return []
respuesta =[raiz]cola =[raiz]nivel =1whilecola: nivel +=1for _ inrange(len(cola)): nodo_actual = cola.pop(0) respuesta.append(nodo_actual)for hija in nodo_actual.hijas: cola.append(hija)print(f"La cantidad de niveles de este árbol es: {nivel}")return respuesta
La variable respuesta almacena los nodos en el orden BFS. La variable nivel permite contar cuántos niveles tiene el árbol o grafo [2:23].
¿Por qué se itera con range(len(cola))?
Este detalle es crucial. Cuando se llega al while, todo lo que hay en la cola representa un nivel completo del árbol [3:00]. Al iterar exactamente len(cola) veces, se extraen todos los nodos de ese nivel. Mientras se extraen, se van agregando los hijos, que corresponden al siguiente nivel. Así, al terminar el for, la cola contiene únicamente los nodos del próximo nivel por revisar.
¿Cómo se adapta para un árbol binario?
En un árbol n-ario, cada nodo tiene una lista de hijas que se recorre con un for. Pero si se trabaja con un árbol binario, donde cada nodo solo tiene un hijo izquierdo y uno derecho, el bloque se simplifica [5:16]:
python
if nodo_actual.izquierda:
cola.append(nodo_actual.izquierda)
if nodo_actual.derecha:
cola.append(nodo_actual.derecha)
La lógica es idéntica: se pasa de revisar una lista de hijos a verificar directamente dos atributos. Es la misma transición del caso binario al n-ario, solo cambia cómo se acceden los hijos [5:30].
¿Qué más se puede hacer durante el recorrido?
Durante la iteración, cada vez que se extrae un nodo_actual, se puede imprimir su valor para ver el orden de recorrido en tiempo real [4:51]:
python
print(nodo_actual.valor)
Esto resulta útil para depuración o para visualizar cómo BFS procesa cada nivel antes de pasar al siguiente.
Algunos puntos para recordar:
BFS usa colas, DFS usa pilas.
La cola se inicializa con la raíz.
Se procesan todos los nodos de un nivel antes de avanzar al siguiente.
El while termina cuando la cola está vacía, es decir, cuando no quedan nodos por visitar.
Contar niveles es tan simple como incrementar un contador después de procesar cada nivel completo.
Aunque el ejemplo usa Python, la implementación aplica a cualquier lenguaje; solo cambia la sintaxis para operaciones como pop o append. ¿Ya probaste implementar BFS en tu lenguaje favorito? Comparte tu experiencia en los comentarios.
