BFS esplora un grafo livello per livello, visitando tutti i vicini di un nodo prima di andare più in profondità. Utilizza una coda e trova il percorso più breve (meno archi) nei grafi non ponderati.
Partire da una sorgente, inserirla in coda, quindi ripetutamente estrarre un nodo, visitare i suoi vicini non visitati e inserirli in coda. Un insieme visited previene la rivisitazione.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft() # FIFO: explore nearest first
order.append(node)
for nbr in graph[node]:
if nbr not in visited:
visited.add(nbr)
queue.append(nbr)
return order
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
bfs(graph, 'A') # -> ['A', 'B', 'C', 'D']
Usare BFS per il percorso più breve nei grafi non ponderati, traversal in ordine di livello e ricerca di componenti connesse. Usa più memoria di DFS (un'intera frontiera alla volta). Tracciare sempre visited o potresti fare un ciclo infinito su cicli.
BFS è l' algoritmo per i percorsi più brevi quando ogni arco conta ugualmente — routing, web crawling, gradi di separazione nelle reti sociali.
La sua struttura basata su coda e livello per livello è un pattern di traversal fondamentale.
Conoscere BFS vs DFS ti permette di scegliere lo strumento giusto per problemi di raggiungibilità, percorsi e ordinamento.