8. BFS vs DFS
- A diferença central: ordem de exploração
- Estruturas de dados: fila vs pilha (ou recursão)
- O que cada travessia produz (árvores + metadados)
- Quando BFS é a ferramenta correta
- Quando DFS é a ferramenta correta
- Comparação de complexidade
- Erros comuns & diretrizes de engenharia
BFS e DFS são as duas travessias fundamentais em grafos. Elas parecem semelhantes no código, mas seu comportamento estrutural é diferente: a BFS expande por camadas; a DFS aprofunda ao máximo antes de retroceder.
Esta parte fornece um modelo mental prático para escolher rapidamente a abordagem correta.
8.1 Diferença Central: Ordem de Exploração
A ordem não é apenas estética: ela altera as garantias do algoritmo. A BFS garante caminhos mínimos em grafos não ponderados; a DFS não.
8.2 Fila vs Pilha
- BFS usa fila (FIFO) → preserva camadas.
- DFS usa pilha (LIFO) ou recursão (pilha de chamadas).
8.3 Comparação Lado a Lado
| Aspecto | BFS | DFS |
|---|---|---|
| Exploração | Camada por camada | Aprofunda e depois retrocede |
| Estrutura | Fila (FIFO) | Pilha (LIFO) / recursão |
| Caminho mínimo (não ponderado) | Sim | Não |
| Melhor para | Mínimo de saltos, camadas | Estrutura, ciclos, ordenação topológica |
| Complexidade | O(|V|+|E|) | O(|V|+|E|) |
8.8 Complexidade
A principal diferença prática está no perfil de memória:
- BFS pode armazenar uma grande fronteira.
- DFS armazena apenas o caminho atual.
Série Concluída
Você agora possui o conjunto completo da BFS: intuição, algoritmo formal, prova de correção, análise de complexidade, reconstrução de caminhos, aplicações — e comparação com DFS.