Análise de Algoritmos | Aulas | Dicionário | Índice

Ciclos e digrafos acíclicos

Ciclos tornam digrafos complexos, interessantes e difíceis. Digrafos sem ciclos são fáceis, mas bastante úteis. Digrafos com ciclos são como animais selvagens, enquanto digrafos sem ciclos são como animais domesticados.

Esta página trata do problema de encontrar um ciclo num digrafo. O problema tem uma solução muito elegante e eficiente que começa com uma busca em profundidade.

Esta página é inspirada na seção 22.4 de CLRS).  

Ciclos

Um ciclo (= cycle) é um caminho com dois ou mais arcos cujo primeiro vértice coincide com o último. Em outras palavras, um ciclo é um caminho  (v₀, v₁, … , v_k-1, v_k)  tal que v_k = v₀ e k ≥ 2. (Convém lembrar que caminhos não têm arcos repetidos.)

Os arcos de um ciclo apontam todos na mesma direção. Para enfatizar esse fato, usam-se ocasionalmente as expressões ciclo orientado e ciclo digrigido (= directed cycle) no lugar de ciclo.

Um ciclo é simples se não tem vértices repetidos exceto o último, que é igual ao primeiro. Todo ciclo contém um ciclo simples: se C é um ciclo então alguma subsequência de C é um ciclo simples.

Problema do ciclo:  Encontrar um ciclo num digrafo dado.

Nem toda instância do problema tem solução, pois muitos digrafos são acíclicos, ou seja, não têm ciclos.  Digrafos acíclicos são conhecidos como DAGs (= Directed Acyclic Graphs). Faz parte do problema verificar se o digrafo dado é um DAG.

A versão booleana do problema consiste em decidir, tão somente, se um digrafo tem um ciclo. Diremos que essa é a versão de decisão do problema.

Exemplo A:  No digrafo da figura à direita, (4, 1, 6, 4, 5, 4) é um ciclo. Os ciclos (1, 6, 4, 1) e (1, 6, 1) são simples. Nem (6) nem (6, 4, 1, 6, 4, 5, 6) são ciclos.  A figura abaixo mostra um DAG.

Algoritmo

O seguinte algoritmo decide, de uma maneira muito elegante e eficiente, se um digrafo G tem um ciclo. O algoritmo faz uma busca em profundidade, calcula uma floresta DFS, e em seguida procura arcos que sejam de retorno em relação à floresta.

A linha 1 constrói uma floresta DFS, representada pelo vetor pai. Na linha 4, a desigualdade pós[v] < pós[w] mostra que vw é um arco de retorno, ou seja, que w é ancestral de v na floresta. Portanto, existe um caminho, digamos P, de w a v na floresta. A concatenção P + vw é um ciclo. Portanto, o devolva true na linha 5 está correto!

Resta mostrar que o return false na linha 6 está correto. Suponha que estamos no início da linha 6. Nessa ocasião, temos

Isso garante que não existe ciclo algum! Com efeito, qualquer ciclo teria que voltar ao ponto de partida, e (*) torna isso impossível. Portanto, o devolva falso na linha 6 está correto.

O análise do algoritmo prova o seguinte teorema: dada uma floresta DFS de um digrafo, todo ciclo do digrafo tem um arco de retorno em relação à floresta.

Desempenho.  Tal como a busca em profundidade, o algoritmo Ciclo consome

Ο(n + m)

unidades de tempo, sendo n o número de vértices e m o número de arcos do digrafo. Essa estimativa é justa, pois para algumas famílias de digrafos o algoritmo consome Ω(n + m) unidades de tempo.

Permutação topológica

A condição (*) acima é tão importante que merece uma discussão mais geral. Uma permutação (v₁, v₂, … , v_n) dos vértices de um digrafo é topológica se

i < j  para todo arco v_i v_j ,

ou seja, se todos os arcos do digrafo apontam da esquerda para a direita em relação à permutação. Uma permutação (v₁, v₂, … , v_n) é anti-topológica se i > j para todo arco v_i v_j , ou seja, se todos os arcos apontem da direita para esquerda.  Qualquer permutação anti-topológica pode ser representada por um vetor numérico, digamos t, tal que t[v] > t[w] para todo arco vw. Como vimos em (*) acima, o vetor pós no algoritmo Ciclo tem essa propriedade.

Exemplo B.  As duas figuras representam o mesmo digrafo. A figura à direita sugere a permutação topológica (8, 7, 2, 3, 0, 6, 9, 10, 11, 12, 1, 5, 4). Todos os arcos apontam de cima para baixo.

A existência de uma permutação topológica é uma prova simples e cabal de que o digrafo é acíclico. De fato, como já observamos acima, qualquer ciclo precisa voltar ao ponto de partida, e a permutação topológica impede essa volta.

Na linha 6 do algoritmo Ciclo, a permutação dos vértices em pós-ordem inversa — ou seja, a permutação que coloca os vértices em ordem decrescente de pós — é topológica. Assim, o algoritmo prova o seguinte teorema:

Teorema:  Um digrafo é acíclico se e somente se seu conjunto de vértices admite um permutação topológica.

Mas o algoritmo Ciclo faz mais que provar o teorema. Suponha que na linha 6 o algoritmo devolva o vetor pós e na linha 5 devolva o arco vw e o vetor pai. Com esse aparelhamento, o algoritmo não só diz se G tem um ciclo como também fornece um certificado que habilita o usuário a verificar, por conta própria, se a resposta está correta:

• se a resposta for true, a sequência (v, pai[v], pai[pai[v]], … , w) é um ciclo de G;
• se a resposta for false, pós define uma permutação dos vértices que prova que G não tem ciclo algum.

Apêndice: versão on-the-fly do algoritmo

O algoritmo Ciclo examina o digrafo todo duas vezes: uma vez na linha 1 e outra no bloco de linhas 2-5. Embora isso resulte em um algoritmo linear, é preferível obter o mesmo efeito examinando o digrafo uma só vez. Para fazer isso, é preciso inserir o código de Busca-em-Profundidade na linha 1 de Ciclo e interromper a busca assim que um ciclo for encontrado. Diremos que essa é a versão on-the-fly de Ciclo.