Búsqueda en anchura BFS en Python
BFS visita primero los vecinos directos mediante una queue.
¿Qué es Búsqueda en anchura BFS en Python?
BFS visita primero los vecinos directos mediante una queue.
Explora un grafo nivel por nivel.
¿Cuándo se utiliza?
- Comprender algoritmos y estructuras de datos.
- Observar cada paso y tratar casos límite.
- Comparar tiempo de ejecución y memoria.
Visualizador de 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
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)Resultado esperado
['A', 'B', 'C', 'D', 'E']Cómo funciona
visited evita repeticiones: tiempo O(V+E), memoria O(V).
Cambia los valores y ejecuta el programa en el compilador Python online de CodeUtility sin instalar Python.
Ejercicios prácticos
Modifica las entradas y prueba casos límite antes de usar conjuntos de datos mayores.
- Prueba una entrada vacía, un elemento y duplicados.
- Muestra el estado después de cada paso.
- Compara el rendimiento con otra solución.