Olá, caro Deviante! Tudo bem por aí?

No artigo anterior, utilizamos a Busca por Largura (BFS) para percorrer as partidas das quartas de final da Copa do Mundo de 2022. Como vimos, a BFS explora todos os vértices de um mesmo nível antes de avançar para o próximo.

Há outra estratégia popular de busca em grafos: a Busca por Profundidade (Depth-First Search – DFS). Em vez de explorar vários caminhos simultaneamente, ela prefere “mergulhar” em um único ramo da árvore, avançando o máximo possível antes de voltar para analisar outras possibilidades.

Para entender essa diferença, vamos imaginar um cenário alternativo:

E se o Brasil tivesse vencido a Croácia nas quartas de final da Copa de 2022?

Curioso?  Veja abaixo como essa relação Grafos/Copa do Mundo pode ser interessante de acompanhar.

Introdução

A DFS é uma excelente ferramenta para explorar cenários hipotéticos. Ela permite a navegação por diferentes possibilidades, voltando atrás quando encontra um caminho concluído.

Nosso grafo dessa vez será uma árvore de decisões:

Grafo exibindo os cenários onde o Brasil venceria a Croácia. Em um cenário o Brasil vence a Argentina e chega na Final com a França, no outro a Argentina vence e chega até a Final

Cada vértice representa um estado possível do torneio.

As Propriedades dos Vértices

Semelhante ao que vimos na implementação clássica da BFS, cada vértice possui algumas propriedades importantes:

• Cor: indica o estado atual do vértice.
• Tempo de descoberta (d): indica quando a DFS encontra o vértice pela primeira vez
• Tempo de finalização (f): indica quando a DFS termina de explorar todos os caminhos descendentes desse vértice
• Vértice-pai: identifica qual vértice levou à descoberta do atual

Inicialmente as propriedades se iniciam no modo padrão:

• Cor: branca
• d: indefinido
• f: indefinido
• Vértice-pai: nulo

As Cores da DFS

Durante a execução utilizaremos:

• Branco: não visitado.
• Cinza: descoberto. Ainda em processamento.
• Azul: completamente finalizado (na literatura tradicional o valor é o preto)

A Principal Diferença para a BFS

Há uma sutil diferença na forma como BFS e a DFS armazenam o histórico das operações. A BFS utiliza a estrutura de Dados Fila, onde a lógica diz que o primeiro que entra é o primeiro que sai (FIFO: first in, first out). 

Já a DFS utiliza a estrutura de dados Pilha, na qual o último que entra é o primeiro que sai (LIFO: last in, last out).

Iniciando a Busca

Basicamente, a execução começa no vértice Brasil vence Croácia, que recebe a cor cinza e é colocado na pilha.

A partir daí, a DFS procura o primeiro caminho disponível.

Suponha que ela escolheu o vértice Brasil vence Argentina. Esse novo vértice também é empilhado, e em seguida o vértice Brasil vence França é inserido no topo da pilha.

Início de execução DFS

Neste momento não existem mais caminhos para explorar.

O Primeiro Caminho Encontrado

Nesse cenário, o mundo seria abençoado com uma combinação épica (Brasil campeão, depois de eliminar Argentinos e Franceses).

Entretanto, a DFS não terminou sua execução. Ainda existe um outro caminho pra explorar.

O Backtracking

Ao perceber que chegou ao final de um ramo, a DFS começa a voltar. Esse processo é conhecido como backtracking.

Implementação completa DFS. O Algoritmo vai desempilhando os vertices até chegar no inicial e explorar o caminho da direita, no cenário onde a Argentina vence o Brasil

Primeiro ela retorna para o vértice Brasil vence Argentina e depois vai para Brasil vence Croácia.

A partir daí, procura caminhos ainda não explorados. No nosso caso, o cenário restante é o de:

• Argentina vence Brasil
• Argentina vence França

Agora temos um cenário completamente diferente, com a Argentina sendo a  campeã mundial.

Observe que o algoritmo não precisou reiniciar a busca. Ele simplesmente voltou para o último ponto de decisão e seguiu por outro caminho.

Tempos de Descoberta e Finalização

A DFS registrou dois momentos importantes para cada vértice:

• Tempo de descoberta (d): o instante em que o vértice foi visitado pela primeira vez — quando recebe a cor cinza e entra na pilha.
• Tempo de finalização (f): o instante em que todos os seus descendentes já foram completamente explorados — quando recebe a cor azul e sai da pilha.

No nosso exemplo, a execução completa produziu os seguintes registros:

Observe um padrão importante: o tempo de finalização de um vértice é sempre maior do que o de todos os seus descendentes. O vértice Brasil vence Croácia, só foi finalizado (f=6) quando a subárvore abaixo dele foi completamente explorada.

Há vários aspectos que podemos explorar futuramente baseando-nos nessas informações. Entre eles, a detecção de ciclos, ordenação topológica e análise de dependências.

Conclusão

Sabe aquela situação no atendimento eletrônico do banco em que você chega à opção “retornar ao menu inicial”?  Esse seria um ótimo exemplo para explicar a DFS, o algoritmo também volta para pontos anteriores quando precisa explorar novos caminhos.

Vamos combinar que imaginar cenários alternativos para uma Copa do Mundo é bem mais divertido. Daí resolvemos partir da hipótese de que o Brasil venceu a Croácia.

Para simplificar a análise, desconsiderei alguns resultados possíveis, como o cenário em que a França vence a final. Essa possibilidade geraria novos ramos e aumentaria significativamente o número de execuções da DFS.

Espero muito que os exemplos acima tenham ajudado a clarear o algoritmo de Busca por Profundidade pra você. Eu acredito que, em especial, a ideia de BackTracking ficou bem mais simples de entender, em comparação aos exemplos com os quais tive contato na primeira vez que estudei esse tema.

Muito obrigado pela leitura e um grande abraço.