Projeto de Algoritmos → Busca → Busca em Largura (BFS) · Parte 6

6. Árvore BFS & Reconstrução de Caminho

Roteiro (o que você aprenderá nesta parte):

Entender o que a BFS produz (vetores π e d)
Definir o subgrafo de predecessores e por que ele é uma árvore
Formalizar a “reconstrução de caminho” a partir dos ponteiros π
Implementar um procedimento de reconstrução (estilo CLRS)
Ver um pequeno exemplo resolvido
Extrair padrões de engenharia (pais, roteamento, breadcrumbs)

A BFS faz mais do que calcular distâncias. Ela produz uma relação de predecessores π que codifica uma árvore BFS enraizada na origem.

Nesta parte, tornamos essa saída explícita e mostramos como reconstruir um caminho mínimo de s até qualquer vértice alcançável v.

6.1 O que a BFS Produz

Após executar BFS a partir de uma origem s, cada vértice v possui:

d[v] — distância mínima de s até v
π[v] — predecessor de v em um caminho mínimo (ou NIL)

Regra fundamental: Se π[v] = u, então d[v] = d[u] + 1.

6.2 O Subgrafo de Predecessores

E π = { (π[v], v) ∣ v \in V, v \neq s, π[v] \neq NIL }

O grafo T = (V, E_π) é chamado de subgrafo de predecessores da BFS.

Restrito aos vértices alcançáveis, ele forma uma árvore enraizada em s.

6.3 Por que Isso é uma Árvore

Cada vértice alcançável tem exatamente um predecessor.
As distâncias diminuem estritamente ao seguir predecessores.

Logo, não há ciclos e todos os caminhos levam à raiz.

Próxima: Parte 7 — Aplicações

Agora que entendemos como a BFS constrói uma árvore e reconstrói caminhos mínimos, vamos explorar onde essa estrutura é utilizada na prática. Na Parte 7, analisamos aplicações reais da BFS em redes, grades (grids), grafos de dependência e sistemas de engenharia.

Continuar: Parte 7 — Aplicações →