DFS — Algoritmo de Busca em Profundidade Explicado

A busca em profundidade, ou DFS, é um algoritmo para explorar uma árvore ou grafo seguindo um caminho o mais longe possível antes de fazer backtracking. Em termos simples: o DFS continua indo mais fundo até ficar sem saída, e então volta ao último ponto onde ainda havia outro ramo disponível.

Se você lembrar de uma ideia só, lembre desta: DFS significa "vá fundo e depois volte".

O Que a Busca em Profundidade Faz

O DFS pode ser usado em árvores e em grafos gerais. Começando por um nó, ele se move repetidamente para um vizinho ainda não visitado. Quando chega a um nó sem vizinhos não visitados restantes, faz backtracking para o nó anterior e continua a partir dali.

Esse backtracking é o comportamento que define o algoritmo. Em implementações recursivas, a pilha de chamadas cuida disso automaticamente. Em implementações iterativas, uma pilha explícita cumpre o mesmo papel.

Por Que a Ordem do DFS Pode Mudar

O DFS não produz uma única ordem universal de visita. A ordem exata depende da ordem em que os vizinhos são considerados.

Por exemplo, se um nó tem os vizinhos $B$ e $C$, visitar $B$ primeiro pode gerar uma ordem de DFS diferente de visitar $C$ primeiro. A busca ainda é DFS nos dois casos, porque a regra é a mesma: continuar indo mais fundo antes de explorar um ramo irmão.

Exemplo de DFS em um Grafo Pequeno

Suponha que o grafo tenha estas conexões:

• $A$ se conecta a $B$ e $C$
• $B$ se conecta a $D$ e $E$
• $C$ se conecta a $F$

Assuma que sempre analisamos os vizinhos da esquerda para a direita e começamos em $A$.

O DFS acontece assim:

1. Visite $A$
2. Vá para $B$
3. Vá para $D$
4. $D$ não tem vizinhos não visitados, então faça backtracking para $B$
5. A partir de $B$, vá para $E$
6. $E$ terminou, então faça backtracking para $B$ e depois para $A$
7. A partir de $A$, vá para $C$
8. A partir de $C$, vá para $F$

Então, uma ordem válida de visita no DFS é:

$$A, B, D, E, C, F$$

A ideia principal é que o DFS termina o lado $A \to B$ antes de começar o lado $A \to C$. Se você mudasse a ordem dos vizinhos, a ordem de visita também poderia mudar.

Por Que o Backtracking Usa uma Pilha

O DFS sempre precisa de uma forma de lembrar para onde voltar depois de chegar a um beco sem saída. É por isso que pilhas aparecem naturalmente no DFS.

No DFS recursivo, cada chamada de função espera enquanto a busca vai mais fundo, e o programa retorna em ordem inversa quando faz backtracking. No DFS iterativo, você coloca nós em uma pilha e os remove quando chega a hora de continuar a partir do ponto inacabado mais recente.

Complexidade de Tempo e Espaço do DFS

Se o grafo for armazenado como uma lista de adjacência e cada vértice for marcado na primeira vez em que for visitado, o DFS executa em

$$O(V + E)$$

tempo para a parte alcançável do grafo, em que $V$ é o número de vértices e $E$ é o número de arestas.

O espaço extra é tipicamente

$$O(V)$$

porque a estrutura de visitados e a pilha de recursão ou pilha explícita podem crescer com o número de vértices.

Erros Comuns no DFS

Esquecer de Marcar os Nós Visitados

Em um grafo geral, esquecer a verificação de visitados pode fazer o DFS percorrer um ciclo para sempre. Mesmo em uma árvore armazenada como grafo não direcionado, você ainda precisa evitar voltar imediatamente ao pai, a menos que seu código trate esse caso explicitamente.

Assumir Que o DFS Encontra o Caminho Mais Curto

O DFS pode encontrar um caminho, mas em geral não garante o caminho mais curto em um grafo não ponderado. Se o objetivo for o caminho mais curto e todas as arestas tiverem o mesmo peso, o BFS geralmente é o ponto de partida certo.

Tratar a Ordem do DFS Como Única

A ordem depende da ordem dos vizinhos. Se essa ordem mudar, a ordem de travessia também pode mudar.

Quando a Busca em Profundidade É Usada

O DFS é útil quando você quer explorar a estrutura, e não apenas a menor distância primeiro. Usos comuns incluem:

• verificar se um nó é alcançável
• encontrar componentes conexas
• detectar ciclos em alguns contextos de grafos
• percorrer árvores
• resolver problemas de backtracking, como labirintos ou busca em quebra-cabeças

A principal razão para ele aparecer com tanta frequência é que "vá fundo e depois volte" combina com muitas estruturas de problemas recursivos.

DFS Vs BFS: A Diferença Prática

O DFS desce por um ramo primeiro. O BFS explora todos os nós a uma mesma distância antes de passar para a próxima distância.

Se você se importa com exploração exaustiva ou com estrutura recursiva, o DFS costuma ser natural. Se você se importa com o caminho mais curto em um grafo não ponderado, o BFS costuma ser a escolha inicial mais segura.

Tente uma Travessia Parecida

Desenhe um grafo pequeno com seis nós e escolha uma ordem fixa para os vizinhos. Execute o DFS à mão e anote exatamente quando você avança e quando faz backtracking. Se sua ordem mudar depois que você reorganizar os vizinhos, isso não é um bug. Faz parte de como o DFS funciona.