1. Modelo de Grafo
A Busca em Profundidade (DFS) opera sobre um grafo formalmente definido como
- V — o conjunto de vértices
- E — o conjunto de arestas
Os grafos podem ser:
- Direcionados
- Não direcionados
A DFS funciona em ambos os casos e permite explorar a estrutura do grafo a partir de um vértice inicial.
2. O Problema de Exploração
Dado um grafo G = (V,E) e um vértice inicial s ∈ V, o objetivo é explorar todos os vértices alcançáveis a partir de s.
A DFS realiza essa exploração seguindo um caminho o mais profundamente possível antes de retornar e explorar caminhos alternativos.
3. Estrutura da Exploração
A DFS explora o grafo seguindo um único caminho até que não existam mais vértices não visitados alcançáveis a partir do vértice atual.
Quando isso acontece, o algoritmo retorna ao vértice anterior e continua explorando outras arestas ainda não visitadas.
4. Alcançabilidade
Um vértice v é considerado alcançável a partir de s se existir um caminho de s até v.
A DFS descobre exatamente o conjunto de vértices alcançáveis a partir da origem.
5. Por que a DFS é Importante
A Busca em Profundidade é um dos algoritmos fundamentais de travessia em grafos.
Ela serve como base para diversos algoritmos importantes da ciência da computação.
- Detecção de ciclos
- Ordenação topológica em DAGs
- Componentes fortemente conectados
- Análise estrutural de grafos
Próximo: Parte 2 — A Ideia Central (Exploração Profunda + Backtracking)
Agora que definimos o modelo de grafo e o problema de exploração, podemos estudar a ideia central da DFS: como o algoritmo explora caminhos profundamente antes de retornar.