Algoritmos en Python

La búsqueda en anchura (BFS) en Python

En esta lección vas a recorrer un grafo nivel por nivel con la búsqueda en anchura y una cola deque.

  • Intermedio
  • 2 min de lectura
  • 1 ejemplo ejecutable

Introducción

El problema

¿Cuántos pasos hay de una persona a otra en una red social, o de una casilla de un laberinto a la salida? La búsqueda en anchura explora en anillos de distancia, así que la primera vez que llega a un nodo lo hace por un camino más corto.

Imagínalo así

La búsqueda en anchura es como las ondas en un estanque. Tiras una piedra en el punto de partida y la onda llega primero a todo lo que está a un paso, luego a todo lo que está a dos pasos, y así sucesivamente. Nada más lejano se toca antes de haber llegado a todo lo más cercano.

De las ondas del estanque al código
queue = deque(["A"])🪨 Tira la piedra en A
node = queue.popleft()🌊 Toma el siguiente nodo por orden de distancia
if neighbor not in visited:🔎 ¿Todavía no se ha alcanzado?
queue.append(neighbor)➕ Añádelo al siguiente anillo
Primero los nodos más cercanos, usando una cola.
En una frase

La búsqueda en anchura (BFS) recorre un grafo nivel a nivel desde un nodo inicial usando una cola, así encuentra los caminos más cortos en grafos sin pesos.

Puntos clave

  1. queue guarda los nodos que esperan ser explorados, primero los más antiguos.
  2. visited registra los nodos ya encontrados, así ninguno se añade dos veces y los ciclos no pueden repetirse sin fin.
  3. node = queue.popleft() toma el siguiente nodo; sus vecinos no visitados se ponen al final de la cola.
  4. order muestra A, luego sus vecinos B y C, y luego D y E un nivel más allá.

¿Cuándo se usa?

  • Caminos más cortos en grafos sin pesos, cuadrículas y laberintos.
  • Grados de separación en redes sociales.
  • Rastreadores web y encontrar todo lo alcanzable desde un punto de partida.

Cuándo no hace falta

  • Las aristas tienen costes distintos, como las distancias por carretera: usa el algoritmo de Dijkstra.
  • Necesitas explorar un camino entero antes que los demás, por ejemplo para backtracking: usa búsqueda en profundidad.

Visualizador de La búsqueda en anchura (BFS) en Python

O(V + E)

Usa Reproducir o Paso para seguir cada comparación y movimiento de datos.

Código de ejemplo

Ejecutar código →
main.py
from collections import deque

graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
queue = deque(["A"])
visited = {"A"}
order = []

while queue:
    node = queue.popleft()
    order.append(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)

print(order)
Obtén un botón Run para este ejemplo

Resultado de la ejecución

['A', 'B', 'C', 'D', 'E']

Explicación del código

La cola queue guarda los nodos que esperan su visita, que salen en el mismo orden en que entraron. El conjunto visited recuerda los nodos ya encontrados para no visitar el mismo nodo varias veces cuando el grafo tiene ciclos. El orden de visita es A, B, C, D, E, y la complejidad es O(V + E), donde V es el número de nodos y E el número de aristas.

Cambia los valores y ejecuta el programa en el compilador Python online de CodeUtility sin instalar Python.

Ejercicios de práctica

Prueba a modificar el código siguiendo las ideas de abajo. Cambiar el código y ver el resultado te ayudará a entender la lección mucho mejor que solo leerla.

  1. Prueba con una lista vacía, una lista de un solo elemento y una lista con repetidos.
  2. Muestra el estado después de cada paso para ver el algoritmo en acción.
  3. Mide el tiempo de ejecución con 100, 1.000 y 10.000 elementos y compáralo con otra solución.
Ejecutar en el compilador de Python →

Errores comunes

Marcar los nodos como visitados demasiado tarde

Si un nodo se marca solo cuando se saca de la cola, puede añadirse muchas veces.

Problema
node = queue.popleft()
visited.add(node)
for neighbor in graph[node]:
    if neighbor not in visited:
        queue.append(neighbor)
Solución
for neighbor in graph[node]:
    if neighbor not in visited:
        visited.add(neighbor)
        queue.append(neighbor)

¿Terminaste esta lección?

Márcala como aprendida para seguir tu progreso.

Practica con un reto

Usa lo que cubre esta lección para resolver un problema real. Cada reto se ejecuta en el navegador, con pruebas al instante y una revisión de IA.

Todos los retos