Breadth-First Traversal (BFT), o Recorrido en Anchura, es un algoritmo para explorar todos los nodos de un grafo o estructura de árbol de manera sistemática. Comienza en un nodo raíz (o un nodo arbitrario en un grafo) y explora todos sus nodos vecinos antes de moverse a los vecinos de esos vecinos, y así sucesivamente. Utiliza una cola (queue) para gestionar el orden de los nodos a visitar, asegurando que todos los nodos a una profundidad 'k' sean visitados antes que cualquier nodo a una profundidad 'k+1'. Esto contrasta con Depth-First Traversal (DFT), que explora lo más profundo posible a lo largo de cada rama antes de retroceder.
BFT tiene aplicaciones extensas en el mundo real. Es la base para algoritmos de búsqueda del camino más corto en grafos no ponderados, como el algoritmo de Dijkstra en su forma básica. Los "web crawlers" lo utilizan para indexar páginas web, explorando enlaces de forma sistemática. En sistemas distribuidos, se emplea para descubrir nodos en una red o para propagar información (como actualizaciones de estado) a través de un clúster. También se usa en algoritmos de "garbage collection" para identificar objetos accesibles en la memoria y en la construcción de árboles de expansión mínimos (Minimum Spanning Trees) como el algoritmo de Prim.
Para un arquitecto, comprender BFT es crucial debido a sus propiedades y trade-offs. Su garantía de encontrar el camino más corto en grafos no ponderados lo hace ideal para problemas de conectividad y routing donde el número de saltos es la métrica principal. Sin embargo, su uso de una cola puede requerir una cantidad significativa de memoria (O(V+E) en el peor caso, donde V son vértices y E son aristas) para almacenar los nodos pendientes de visitar, especialmente en grafos anchos o densos. Esto es una consideración importante en sistemas con restricciones de memoria. Además, su naturaleza exploratoria por niveles puede ser menos eficiente que DFT para encontrar un nodo objetivo específico que se sabe que está muy profundo en una rama particular. La elección entre BFT y DFT a menudo depende de la topología del grafo, los recursos disponibles y el objetivo específico de la búsqueda o el recorrido.