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.
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.
queue = deque(["A"])🪨 Tira la piedra en Anode = queue.popleft()🌊 Toma el siguiente nodo por orden de distanciaif neighbor not in visited:🔎 ¿Todavía no se ha alcanzado?queue.append(neighbor)➕ Añádelo al siguiente anilloLa 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
queueguarda los nodos que esperan ser explorados, primero los más antiguos.visitedregistra los nodos ya encontrados, así ninguno se añade dos veces y los ciclos no pueden repetirse sin fin.node = queue.popleft()toma el siguiente nodo; sus vecinos no visitados se ponen al final de la cola.ordermuestra 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
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)
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.
- Prueba con una lista vacía, una lista de un solo elemento y una lista con repetidos.
- Muestra el estado después de cada paso para ver el algoritmo en acción.
- Mide el tiempo de ejecución con 100, 1.000 y 10.000 elementos y compáralo con otra solución.
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.
node = queue.popleft()
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
queue.append(neighbor)
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.
- Can We Split Into Two Teams? Decide whether people can be assigned to two teams so that each listed pair is on opposite teams. Intermedio
- Diámetro de un Árbol Un árbol es un grafo no dirigido, conexo y sin ciclos. Intermedio
- Count Islands Count groups of connected land cells in a grid. Intermedio