Grafo e menor caminho
Em mapas digitais, encontrar a rota mais curta entre duas cidades é uma operação cotidiana. Algoritmos de busca em largura (BFS) são usados em sistemas de navegação, redes sociais e até para roteamento de pacotes na internet. Dominar essa técnica com estruturas simples como dicionários e conjuntos te dá uma ferramenta prática para resolver problemas de conectividade e caminhos mínimos.
O PROBLEMA
BFS para encontrar caminho entre cidades em grafo.
EXEMPLO
caminho(A,D) → A→B→D
SOBRE O CONCEITO
O BFS percorre um grafo nível a nível a partir de um nó inicial, usando uma fila (simulada com pop(0)) para explorar vizinhos. Ele garante a menor distância em arestas não ponderadas. O erro comum é não marcar os nós visitados, fazendo com que o algoritmo entre em loop infinito ao revisitar o mesmo nó (exemplo: cidade A conectada a B, B a A). Usar um set para armazenar visitados evita esse problema e reduz o esforço computacional. No código, você deve iniciar com um set vazio e adicionar cada nó ao ser visitado, verificando antes de enfileirar.
RESOLUÇÃO