Busca em profundidade: ir fundo primeiro

Mergulhar antes de espalhar

Se a busca em largura é como as ondas de um lago, a busca em profundidade é como andar por um labirinto com uma regra teimosa: sempre siga em frente enquanto puder, e só quando bater numa parede volte um passo para tentar outra porta. Ela escolhe um vizinho, vai até ele, de lá escolhe outro vizinho, e continua descendo por esse fio único até não haver mais para onde ir. Nesse ponto ela recua até o último cruzamento onde ainda havia uma saída não testada e mergulha de novo. Em vez de cobrir tudo por perto antes de avançar, a DFS aposta em ir longe primeiro.

A estrutura que sustenta esse comportamento é a pilha, a estrutura LIFO em que o último a entrar é o primeiro a sair. Faz sentido: o vértice mais recente que você visitou é o que deve ser explorado em seguida, e é também o primeiro para onde você volta ao recuar. Na prática, muita gente escreve a DFS de forma recursiva, e aí a pilha nem aparece no código: quem guarda o caminho de volta é a pilha de chamadas de função, aquela mesma que você estudou nos módulos de pilha e recursão. Chamar a busca para um vizinho é descer; a chamada retornar é o backtrack acontecendo sozinho.

Pilha explícita ou recursão

Existem duas formas de escrever a busca em profundidade, e as duas fazem a mesma coisa. A versão recursiva é curta e lê quase como uma frase: visite este vértice, marque-o como visitado e, para cada vizinho ainda não visto, chame a busca nele. A recursão cuida do backtrack de graça, porque quando uma chamada termina o controle volta para a anterior. A versão com pilha explícita troca a recursão por uma pilha de verdade, empilhando os vizinhos e desempilhando o próximo a visitar. É útil quando o grafo é muito profundo e a recursão correria o risco de estourar a pilha de chamadas. As duas usam o mesmo conjunto de visitados da BFS, pelo mesmo motivo: não repetir e não entrar em loop.

função busca_profundidade(atual):
  adiciona atual em visitados
  escreva("visitando ", atual)
  para cada vizinho de atual faça
    se vizinho não está em visitados então
      busca_profundidade(vizinho)   // desce; o retorno é o backtrack
    fim
  fim

A versão recursiva da DFS. A pilha de chamadas guarda o caminho; quando a chamada retorna, a busca faz backtrack.

Quando cada busca serve melhor

As duas buscas visitam os mesmos vértices, mas em ordens bem diferentes, e cada uma brilha num tipo de problema. A busca em largura é a escolha quando você quer o caminho mais curto em passos, porque encontra cada vértice pela rota com menos arestas. A busca em profundidade é mais econômica de memória em grafos largos e é a base natural de qualquer coisa que envolva tentar um caminho e desistir dele: resolver um labirinto por tentativa e erro, descobrir se duas partes do grafo estão conectadas, encontrar todos os vértices de um mesmo bloco. Ela também é o esqueleto do backtracking, a técnica de tentar e voltar que aparece adiante no curso. Escolher entre largura e profundidade é escolher entre garantir o menor caminho e ir fundo com pouca memória.