1. A Ideia Central
A Busca em Profundidade explora um grafo seguindo um caminho o mais profundamente possível antes de explorar caminhos alternativos.
Começando a partir de um vértice de origem s, o algoritmo move-se repetidamente para um vizinho ainda não visitado até alcançar um vértice que não possui mais arestas não exploradas.
2. Exploração Profunda
A DFS expande a busca sempre selecionando um vizinho que ainda não foi visitado.
Isso produz cadeias longas de exploração que seguem um único ramo do grafo.
Somente quando nenhuma expansão adicional é possível o algoritmo retorna ao vértice anterior e continua a exploração.
3. Backtracking
Quando um vértice não possui vizinhos não visitados, a DFS realiza backtracking.
O algoritmo retorna ao vértice mais recente que ainda possui arestas não exploradas.
4. A Pilha Implícita
O processo de exploração naturalmente forma uma estrutura de pilha.
- Cada chamada recursiva empilha um vértice
- O retorno da recursão desempilha o vértice
Portanto, a DFS pode ser implementada tanto com recursão quanto com uma pilha explícita.
5. Intuição Visual
A travessia se comporta como explorar um labirinto.
- Escolha uma direção
- Caminhe até encontrar um beco sem saída
- Volte até a última interseção
- Tente outra direção
Essa estratégia explora sistematicamente todos os caminhos alcançáveis.
Próximo: Parte 3 — O Algoritmo (Pseudocódigo do CLRS)
Agora que entendemos a intuição por trás da DFS, vamos formalizar o algoritmo usando o pseudocódigo clássico do livro Introduction to Algorithms (CLRS).