La búsqueda en amplitud (BFS, por sus siglas en inglés) es un algoritmo fundamental para explorar estructuras de datos como grafos o árboles. Su principio central consiste en visitar todos los vecinos directos de un nodo antes de avanzar al siguiente nivel de profundidad, expandiéndose de manera horizontal como las ondas en el agua.

Contextos de aplicación

La naturaleza por capas de BFS lo hace especialmente adecuado para resolver una variedad de problemas específicos.

• Camino más corto en grafos no ponderados: La primera vez que se alcanza un nodo mediante BFS, se garantiza que el camino utilizado es el más corto posible en términos de número de aristas.
• Recorrdio por niveles: Permite procesar un árbol o grafo nivel por nivel, como en el ordenamiento por niveles de un árbol binario.
• Verificación de conectividad: Se puede usar para determinar si dos nodos están conectados o para contar componentes conexas en un grafo.
• Ordenamiento topológico: Aplicado en grafos dirigidos acíclicos (DAG), puede ayudar a establecer un orden lineal de tareas que respetan dependencias.
• Simulación de procesos de difusión: Es ideal para modelar la propagación de virus, la inundación de un laberinto o cualquier fenómeno que se expanda desde un punto origen.

Principio de funcionamiento

El algoritmo utiliza una cola (estructura FIFO - Primero en entrar, primero en salir) para gestionar los nodos pendientes de visita. Un array booleano o un conjunto es esencial para marcar los nodos ya explorados y evitar ciclos infinitos en grafos con ciclos.

La implementación iterativa es la estándar y recomendada. Una versión recursiva es posible pero menos intuitiva, ya que no refleja directamente la exploración por capas y puede causar desbordamiento de pila (stack overflow) en grafos muy profundos.

Plantilla de implementación iterativa

funcion bfs_desde(origen):
    crear conjunto visitados vacío
    crear cola pendientes

    agregar origen a pendientes
    marcar origen como visitado

    mientras pendientes no esté vacía:
        nodo_actual = extraer el frente de pendientes
        procesar(nodo_actual)

        para cada vecino en obtener_vecinos(nodo_actual):
            si vecino no está en visitados:
                marcar vecino como visitado
                agregar vecino al final de pendientes

Métodos comunes de la cola

• esta_vacia(): Devuelve verdadero si la cola no tiene elementos.
• insertar(elemento): Añade un elemento al final de la cola.
• extraer(): Remueve y devuelve el elemento del frente.
• consultar_frente(): Devuelve el elemento del frente sin rmeoverlo.

Flujo de trabajo detallado (ejemplo con grafo)

Consideremos un grafo representado mediante listas de adyacencia. El proceso sería el siguiente:

1. Preparación: Inicializar una lista de adyacencia para el grafo, un array o conjunto visitados y una cola pendientes. Opcionalmente, un array distancias para registrar la longitud del camino más corto desde el origen.
2. Arranque: Encolar el nodo origen, marcarlo como visitado y, si se calculan distancias, asignarle distancia 0.
3. Bucle principal: Mientras la cola no se vacíe, desencolar un nodo u. Procesarlo. Luego, por cada vecino v de u: si v no ha sido visitado, marcarlo, encolarlo y, si se calculan distancias, asignrale distancia[u] + 1.
4. Finalización: El bucle termina cuando la cola queda vacía, indicando que todos los nodos alcanzables han sido explorados.

La garantía del camino más corto en grafos no ponderados se debe a que BFS explora los nodos en orden creciente de su distancia al origen. Un nodo en el nivel k es alcanzado exactamente por un camino de longitud k en su primera visita.

Ejemplo de código en Python

Tomemos un grafo no dirigido con 5 nodos (etiquetados 0-4) para ilustrar tanto el recorrido como el cálculo de distancias mínimas.

from collections import deque

def bfs_con_distancias(grafo, inicio):
    """
    Realiza BFS desde 'inicio' e imprime el recorrido
    y la distancia mínima a cada nodo alcanzable.
    """
    visitados = set()
    distancia = {}
    cola = deque()

    # Inicialización
    visitados.add(inicio)
    distancia[inicio] = 0
    cola.append(inicio)

    recorrido = []
    while cola:
        nodo = cola.popleft()
        recorrido.append(nodo)

        for vecino in grafo[nodo]:
            if vecino not in visitados:
                visitados.add(vecino)
                distancia[vecino] = distancia[nodo] + 1
                cola.append(vecino)
    
    return recorrido, distancia

# Definición del grafo (lista de adyacencia)
mi_grafo = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0],
    3: [1],
    4: [1]
}

# Ejecución
orden_recorrido, distancias = bfs_con_distancias(mi_grafo, 0)

print("Orden de visita por BFS:", orden_recorrido)
print("Distancias mínimas desde el nodo 0:")
for nodo, d in distancias.items():
    print(f"  Hacia el nodo {nodo}: {d} pasos")

Salida esperada:

Orden de visita por BFS: [0, 1, 2, 3, 4]
Distancias mínimas desde el nodo 0:
  Hacia el nodo 0: 0 pasos
  Hacia el nodo 1: 1 pasos
  Hacia el nodo 2: 1 pasos
  Hacia el nodo 3: 2 pasos
  Hacia el nodo 4: 2 pasos

Complejidad temporal

La complejidad de BFS es O(V + E), donde V es el número de vértices (nodos) y E es el número de aristas en el grafo. Esto se debe a que cada vértice se encola y procesa una sola vez, y cada arista se considera una sola vez (para nodos ya no visitados) durante el procesamiento de sus vértices extremos.

Comparación con DFS

La elección entre BFS y DFS depende del problema a resolver:

• BFS: Ideal para encontrar el camino más corto en grafos no ponderados o para recorrer por niveles. Usa una cola y explora de forma horizontal.
• DFS: Más adecuado para explorar todos los caminos posibles (backtracking), detectar ciclos, o cuando el grafo es muy ancho pero no muy profundo. Usa una pila (o recursión) y explora de forma vertical hasta agotar un camino.