Introducción

La búsqueda en anchura (Breadth‑First Search, BFS) es un algoritmo fundamental para recorrer estructuras de datos como árboles y grafos. A diferencia de la búsqueda en profundidad (DFS), BFS explora primero todos los nodos del nivel actual antes de pasar al siguiente nivel, garantizando la mínima distancia en grafos no ponderados.

Conceptos Clave

• Cola (FIFO): estructura de datos que mantiene el orden de visita.
• Complejidad temporal: O(V + E) – donde V es el número de vértices y E el número de aristas.
• Complejidad espacial: O(V) – la cola puede contener hasta todos los nodos del nivel más ancho.

Pseudocódigo General

BFS(Grafo, nodo_inicial):
    crear una cola Q
    marcar nodo_inicial como visitado y encolar
    mientras Q no esté vacía:
        v = Q.desencolar()
        procesar(v)
        para cada vecino w de v:
            si w no está visitado:
                marcar w como visitado
                Q.encolar(w)

Implementación en Python (Árbol Binario)

from collections import deque
class Nodo:
    def __init__(self, valor, izquierda=None, derecha=None):
        self.valor = valor
        self.izquierda = izquierda
        self.derecha = derecha
def bfs_raiz(raiz):
    if not raiz:
        return []
    orden = []
    cola = deque([raiz])
    while cola:
        nodo = cola.popleft()
        orden.append(nodo.valor)
        if nodo.izquierda:
            cola.append(nodo.izquierda)
        if nodo.derecha:
            cola.append(nodo.derecha)
    return orden
# --- Ejemplo de uso ---
if __name__ == "__main__":
    # Árbol de ejemplo:
    #        1
    #      /   \
    #     2     3
    #    / \   / \
    #   4   5 6   7
    n4, n5, n6, n7 = Nodo(4), Nodo(5), Nodo(6), Nodo(7)
    n2 = Nodo(2, n4, n5)
    n3 = Nodo(3, n6, n7)
    raiz = Nodo(1, n2, n3)
    print("Orden BFS:", bfs_raiz(raiz))

Salida esperada:

Orden BFS: [1, 2, 3, 4, 5, 6, 7]

Comparativa BFS vs DFS

Casos de Uso Reales

• Generación de árboles de decisión en IA.
• Exploración de niveles en juegos (p.ej., búsqueda de caminos).
• Encontrar la mínima distancia entre dos usuarios en redes sociales.
• Rastrear dependencias en sistemas de paquetes.

Optimización y Buenas Prácticas

1. Usar collections.deque en lugar de listas para popleft() O(1).
2. Marcar nodos como visitados al momento de encolarlos para evitar duplicados y ciclos.
3. Limitar la profundidad con un parámetro opcional cuando el árbol es muy profundo y solo se necesita un nivel.
4. Utilizar generadores si se desea procesar los nodos bajo demanda, ahorrando memoria.

def bfs_generador(raiz):
    if not raiz:
        return
    cola = deque([raiz])
    while cola:
        nodo = cola.popleft()
        yield nodo.valor
        if nodo.izquierda:
            cola.append(nodo.izquierda)
        if nodo.derecha:
            cola.append(nodo.derecha)
# Consumo bajo demanda
for valor in bfs_generador(raiz):
    print(valor, end=' ')

Resolución de Problemas Comunes (Troubleshooting)

• Memoria excesiva: Ocurre en árboles muy anchos. Solución: procesar niveles por lotes o usar bidirectional BFS cuando se busca entre dos nodos.
• Bucles infinitos: Aparecen si no se marca el nodo como visitado antes de encolarlo. Asegúrese de colocar la marca de visita justo antes de cola.append().
• Errores de tipo: Verifique que los hijos sean objetos Nodo o None. Un AttributeError suele indicar que se intentó acceder a .izquierda de None.

Extensiones Avanzadas

Bidirectional BFS

Cuando se busca la distancia mínima entre dos nodos, iniciar BFS simultáneamente desde ambos extremos reduce la complejidad a O(b^{d/2}) (donde b es factor de ramificación y d la distancia).

BFS en Grafos Ponderados (0‑1 BFS)

Para grafos con aristas de peso 0 o 1, se puede usar una deque donde los pesos 0 se añaden al frente y los de peso 1 al final, logrando O(V + E) sin Dijkstra.

Compatibilidad, Rendimiento y Escalabilidad

• Versiones de Python: El código presentado funciona en Python 3.8+ (uso de := opcional para versiones 3.8+).
• Plataformas: Totalmente portable entre Windows, Linux y macOS.
• Escalabilidad: En entornos distribuidos, el algoritmo se puede paralelizar nivel‑a‑nivel usando colas compartidas (e.g., multiprocessing.Queue).