BFS explora um grafo nível por nível, visitando todos os vizinhos de um nó antes de ir mais fundo. Usa uma fila e encontra o caminho mais curto (menos arestas) em grafos não ponderados.
Comece em uma fonte, enfileire-a, depois repetidamente remova um nó da fila, visite seus vizinhos não visitados e enfileire-os. Um conjunto visited evita revisitas.
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']
Use BFS para caminho mais curto em grafos não ponderados, travessia em nível e localização de componentes conectados. Usa mais memória que DFS (toda a fronteira de uma vez). Sempre rastreie visited ou você pode entrar em um loop infinito em ciclos.
BFS é o algoritmo para caminhos mais curtos quando cada aresta conta igualmente — roteamento, web crawling, graus de separação de redes sociais.
Sua estrutura baseada em fila, nível após nível, é um padrão de travessia fundamental.
Conhecer BFS versus DFS permite escolher a ferramenta certa para problemas de alcançabilidade, caminhos e ordenação.