3. O Algoritmo
- Definir o modelo formal usado pelo BFS
- Especificar o estado armazenado em cada vértice
- Apresentar o pseudocódigo do CLRS
- Explicar por que os predecessores formam uma árvore
- Analisar a complexidade de tempo
Nesta seção, formalizamos a Busca em Largura (BFS) utilizando a apresentação clássica do Introduction to Algorithms (CLRS).
Saímos da intuição e entramos na estrutura: estado preciso, passos precisos e garantias formais.
3.1 Objetivo
Dado um grafo G e um vértice fonte s, o BFS explora o grafo em ordem crescente de distância a partir de s.
Em grafos não ponderados, isso significa que o BFS calcula as menores distâncias (em número de arestas) de s até cada vértice alcançável.
3.2 Modelo Formal
Seja:
- G = (V, E) um grafo
- s ∈ V o vértice fonte
3.3 Estado dos Vértices
Cada vértice v ∈ V armazena:
color[v]→ WHITE, GRAY, BLACKd[v]→ distância a partir da fonteπ[v]→ predecessor
| Cor | Significado |
|---|---|
| WHITE | Ainda não descoberto |
| GRAY | Descoberto, mas ainda não totalmente explorado |
| BLACK | Totalmente explorado |
Essa coloração impõe estrutura e evita revisitar vértices.
3.4 Pseudocódigo CLRS — BFS
BFS(G, s):
para cada vértice u em V[G]:
color[u] = WHITE
d[u] = ∞
π[u] = NIL
color[s] = GRAY
d[s] = 0
π[s] = NIL
Q = fila vazia
ENQUEUE(Q, s)
enquanto Q não estiver vazia:
u = DEQUEUE(Q)
para cada v em Adj[u]:
se color[v] == WHITE:
color[v] = GRAY
d[v] = d[u] + 1
π[v] = u
ENQUEUE(Q, v)
color[u] = BLACK3.5 Garantias Estruturais
- Os vértices são explorados em ordem crescente de distância.
- A primeira vez que alcançamos um vértice, encontramos um caminho mínimo (em grafos não ponderados).
- Os predecessores π[v] formam uma árvore BFS.
3.6 Por que Isso Produz uma Árvore
Cada vértice (exceto a fonte) recebe exatamente um predecessor.
- A relação de predecessores define uma árvore.
- Se n vértices são alcançáveis, a árvore BFS possui exatamente n − 1 arestas.
3.7 Complexidade de Tempo
Cada vértice é enfileirado no máximo uma vez. Cada aresta é examinada no máximo duas vezes (caso não direcionado).
Próxima: Parte 4 — Prova de Correção
Agora que temos o algoritmo em forma precisa, o próximo passo é justificá-lo formalmente. Na Parte 4, provaremos sua correção usando invariantes: por que as distâncias são mínimas e por que a ordem de exploração é garantida.