Matemática Discretapara Engenheiros

A Ideia Central da BFS

Antes de escrever código, precisamos entender a geometria do algoritmo.

Busca em Largura não é simplesmente visitar vizinhos.

Ela é a exploração sistemática de um grafo em camadas de distância.

A BFS se expande a partir de um vértice fonte como uma onda.

Camadas de Distância

Seja G = (V, E) e seja s ∈ V um vértice fonte.

Defina a função distância δ(s, v) como o menor número de arestas em qualquer caminho de s até v.

Agora defina as camadas:

Esses conjuntos particionam os vértices alcançáveis:

• L₀ = {s}
• L₁ = vizinhos de s
• L₂ = vértices a distância 2
• L₃, e assim por diante

Essa estrutura em camadas é o coração geométrico da BFS.

Por que as Camadas Importam

A BFS garante: se um vértice é descoberto na camada L_i, então não existe caminho mais curto até esse vértice.

Por quê?

Porque a BFS explora todos os vértices a distância i antes de explorar qualquer vértice a distância i + 1.

Isso não é acidental. É imposto pela fila.

A Disciplina da Fila

A BFS usa uma fila.

Fila = Primeiro a Entrar, Primeiro a Sair (FIFO).

• Vértices são enfileirados quando descobertos.
• Vértices são desenfileirados na mesma ordem em que foram inseridos.

Essa regra simples força o algoritmo a respeitar as camadas.

A Interpretação de Frente de Onda

Pense na BFS como uma onda se expandindo a partir de s.

No passo i:

• Todos os vértices em L_i são processados.
• Seus vizinhos ainda não descobertos tornam-se L_i+1.

A fronteira entre o conjunto explorado e o não explorado é chamada de frente de onda.

Essa interpretação explica tanto a correção quanto a optimalidade.

Interpretação para Engenharia

Por que isso funciona:

• Todas as arestas têm o mesmo peso (grafo não ponderado).
• A distância é medida pela contagem de arestas.
• A ordem FIFO preserva primeiro as menores distâncias.

Portanto:

para todo vértice alcançável v.

Resumo Conceitual

A essência da BFS:

Não é travessia por acaso. É travessia por estrutura métrica.