Ricerca in ampiezza BFS in Python
BFS visita prima i vicini diretti usando una queue.
Che cos’è Ricerca in ampiezza BFS?
BFS visita prima i vicini diretti usando una queue.
Esplora un grafo livello per livello.
Quando si usa?
- Comprendere algoritmi e strutture dati.
- Osservare ogni passaggio e gestire i casi limite.
- Confrontare tempo di esecuzione e memoria.
Visualizzatore di Ricerca in ampiezza BFS in Python
O(V+E)Usa Avvia o Passo per seguire ogni confronto e spostamento dei dati.
Codice di esempio
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)Output previsto
['A', 'B', 'C', 'D', 'E']Come funziona
visited evita ripetizioni: tempo O(V+E), memoria O(V).
Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.
Esercizi pratici
Modifica gli input e verifica i casi limite prima di usare dataset più grandi.
- Prova input vuoto, un elemento e duplicati.
- Stampa lo stato dopo ogni passaggio.
- Confronta le prestazioni con un’altra soluzione.