O que a DFS Resolve
Dado um grafo G = (V, E), a Busca em Profundidade (DFS) explora o grafo aprofundando-se o máximo possível em cada ramo antes de retroceder.
Diferentemente da BFS, a DFS não é orientada por distância. Ela é orientada à estrutura. Ela revela propriedades globais do grafo, como ciclos, componentes fortemente conexas e ordenação topológica.
Referência: a apresentação segue o tratamento clássico em
Introduction to Algorithms (CLRS).
Partes
- Parte 1 — Modelo de Grafo & Definição do Problema
- Parte 2 — A Ideia Central (Exploração Profunda + Retrocesso)
- Parte 3 — O Algoritmo (Pseudocódigo CLRS)
- Parte 4 — Propriedades Estruturais & Tempos de Descoberta
- Parte 5 — Classificação de Arestas
- Parte 6 — Aplicações I (Ciclos & Ordenação Topológica)
- Parte 7 — Aplicações II (SCC & Estruturas Avançadas)
- Parte 8 — DFS vs BFS