Visitados e ciclos: como não andar em círculos

O herói silencioso das buscas

Nas duas aulas de busca, o conjunto de visitados apareceu quase de passagem, mas é ele que separa um algoritmo que termina de um que trava. A árvore, que você estudou antes, tem uma propriedade cômoda: não há ciclos, então nunca se chega ao mesmo nó por dois caminhos, e uma busca pode até dispensar a marcação. O grafo geral não dá esse conforto. Como ele pode ter ciclos, dois vértices podem se ligar por várias rotas, e sem marcar quem já foi visto a busca redescobre os mesmos vértices repetidamente. Num grafo com ciclo, isso vira um loop sem fim: a busca dá voltas eternas na mesma região.

Pense em explorar um prédio com corredores que se conectam em anel. Se você não marca as portas por onde já passou, corre o risco de dar voltas no mesmo circuito para sempre, sem nunca cobrir o prédio inteiro. Marcar cada sala visitada com um giz é o que garante que você olhe cada sala uma vez e termine. O conjunto de visitados é esse giz. Ele custa pouco, uma anotação por vértice, e em troca torna a busca finita e eficiente em qualquer grafo, tenha ele ciclos ou não. É o tipo de detalhe que não chama atenção quando está lá e derruba tudo quando falta.

A aresta que volta revela o ciclo

O mesmo conjunto que evita o loop serve para uma pergunta importante: este grafo tem ciclo? A ideia é direta. Durante a busca, cada vez que você olha um vizinho, verifica se ele já está no conjunto de visitados. Num grafo sem ciclos, todo vizinho novo é inédito. Mas se a busca encontra uma aresta que leva a um vértice já visitado, e que não é simplesmente o vértice de onde ela acabou de vir, isso significa que existe outra rota até aquele vértice, ou seja, um ciclo. Detectar ciclos é essencial em muitos sistemas: descobrir dependências circulares entre tarefas, tabelas de banco de dados que se referenciam em anel, ou impasses em que A espera B que espera A.

visitados <- {}
tem_ciclo <- falso
função visita(atual, anterior):
  adiciona atual em visitados
  para cada vizinho de atual faça
    se vizinho não está em visitados então
      visita(vizinho, atual)
    senão se vizinho é diferente de anterior então
      tem_ciclo <- verdadeiro   // aresta para um já visitado: ciclo
    fim
  fim

Numa DFS, achar um vizinho já visitado que não seja o de onde viemos denuncia um ciclo no grafo.

Grafos com e sem ciclo no dia a dia

Saber se um grafo tem ciclo muda como você raciocina sobre ele. Grafos acíclicos aparecem sempre que existe uma ordem natural sem voltas: a hierarquia de pastas, a sequência de pré-requisitos de matérias, os passos de uma receita, as dependências de um projeto que precisam ser feitas numa ordem. Nesses casos, um ciclo seria um problema: uma matéria que exige a si mesma como pré-requisito, uma tarefa que depende de outra que depende dela. Detectar esse ciclo cedo evita impasses. Já grafos com ciclo são a regra em redes livres: mapas de ruas têm quarteirões que se fecham, redes sociais têm grupos de amigos que se conhecem entre si, a web tem páginas que se linkam em círculo. Nesses, o conjunto de visitados não é um luxo, é o que permite qualquer exploração terminar.