8. DFS vs BFS
- A diferença central entre DFS e BFS
- Pilha vs fila
- O que a BFS calcula naturalmente
- O que a DFS calcula naturalmente
- Comparação lado a lado
- Quando usar DFS
- Quando usar BFS
- Comparação de complexidade
- Equívocos comuns
- Resumo e encerramento da série
DFS e BFS são as duas estratégias fundamentais de travessia em grafos. Ambas exploram grafos em tempo linear, mas revelam diferentes tipos de estrutura.
BFS é orientada a distância. DFS é orientada à estrutura.
8.1 A Diferença Central
- BFS explora o grafo camada por camada.
- DFS explora um caminho profundamente antes de voltar (backtracking).
Essa diferença muda não apenas a ordem de visita, mas também o tipo de informação que cada algoritmo revela naturalmente.
8.2 Fila vs Pilha
A estrutura de dados explica o comportamento de cada algoritmo:
- BFS usa uma fila (FIFO).
- DFS usa uma pilha (explícita ou via recursão).
8.3 O que a BFS Calcula Naturalmente
- menores caminhos em grafos não ponderados
- estrutura por camadas
- número mínimo de passos
- alcance por número de saltos
8.4 O que a DFS Calcula Naturalmente
- tempos de descoberta e finalização
- relações de ancestralidade
- classificação de arestas
- detecção de ciclos
- ordenação topológica
- componentes fortemente conexas
8.5 Comparação Lado a Lado
| Aspecto | BFS | DFS |
|---|---|---|
| Estratégia | Exploração por camadas | Exploração profunda com retorno |
| Estrutura de dados | Fila | Pilha / recursão |
| Melhor para | Distância | Estrutura |
| Menor caminho | Sim | Não |
| Detecção de ciclos | Possível | Natural |
8.8 Complexidade
A principal diferença não está na complexidade, mas no tipo de informação estrutural revelada.
Série concluída
Isso encerra a série sobre Busca em Profundidade (DFS). Agora você domina tanto o algoritmo quanto sua interpretação estrutural em grafos.