Busca em largura BFS em Python
BFS visita primeiro os vizinhos diretos usando uma queue.
O que é Busca em largura BFS em Python?
BFS visita primeiro os vizinhos diretos usando uma queue.
Explore um grafo nível por nível.
Quando usar?
- Entender algoritmos e estruturas de dados.
- Observar cada etapa e tratar casos de borda.
- Comparar tempo de execução e memória.
Visualizador de Busca em largura BFS em Python
O(V+E)Use Executar ou Passo para acompanhar cada comparação e movimento dos dados.
Código de exemplo
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)Saída esperada
['A', 'B', 'C', 'D', 'E']Como funciona
visited evita repetições: tempo O(V+E), memória O(V).
Altere os valores e execute o programa no compilador Python online CodeUtility sem instalar Python.
Exercícios práticos
Altere as entradas e teste casos de borda antes de usar conjuntos de dados maiores.
- Teste entrada vazia, um elemento e duplicados.
- Mostre o estado após cada etapa.
- Compare o desempenho com outra solução.