Esta página trata do problema de decidir se um digrafo é acíclico. A solução eficiente desse problema usa uma busca em profundidade.
Veja o verbete Directed acyclic graph na Wikipedia.
Um ciclo num digrafo é qualquer passeio (v0,v1,…,vk−1,vk) que satisfaça as seguintes restrições: k ≥ 1, vk = v0 e os vértices v0,v1,…,vk−1 são distintos dois a dois. Os arcos do ciclo apontam todos na mesma direção. Para enfatizar esse fato, usam-se ocasionalmente as expressões ciclo orientado e ciclo dirigido no lugar de ciclo.
Ciclos são aparentados com caminhos: se (v0,v1,…,vk−1,vk) é um ciclo então (v1,…,vk−1,vk) é um caminho.
Exemplo 1: No digrafo da figura abaixo, (1,6,1) e (1,6,4,1) são ciclos. Nem (6), nem (4,1,6,4,5,4), nem (2,3,6,2) são ciclos. Se houvesse um laço 11, o passeio (1,1) seria um ciclo.
Um digrafo é acíclico se não tem ciclos. Digrafos acíclicos também são conhecidos como DAGs (abreviatura de "directed acyclic graphs"). As arborescências, por exemplo, são digrafos acíclicos. Esta página discute o seguinte
Problema do digrafo acíclico: Decidir se um dado digrafo é acíclico.
Para resolver o problema, precisamos de um algoritmo que receba um digrafo e devolva
1 se o digrafo é acíclico e
0 em caso contrário.
Seria desejável que além de devolver 0 o algoritmo exibisse um ciclo. Mas não queremos desviar a atenção para esses detalhes por enquanto. Trataremos do assunto na página Digrafos acíclicos e enumeração topológica.
Comecemos por examinar um algoritmo muito simples: para cada arco uv do digrafo, o algoritmo procura um ciclo que contenha uv. Um tal ciclo existe se e somente se u está no território de v. Para decidir se u está no território de v, basta recorrer ao algoritmo Território. Como aquele algoritmo consome tempo Ο(n+m), sendo n o número de vértices e m o número de arcos do digrafo, nosso algoritmo consumirá tempo
Ο(m(n+m)).
Essa estimativa é justa: para alguns digrafos o algoritmo consumirá tempo proporcional a m(n+m). Para muitas aplicações, esse tempo não é tolerável.
O algoritmo é ineficiente: em cada iteração, ele repete boa parte do trabalho realizado em iterações anteriores. Trataremos a seguir de um algoritmo bem mais eficiente.
A seguinte heurística dá um pequeno passo na direção de uma solução eficiente de nosso problema. A heurística "penetra" no digrafo a partir de um vértice r à procura de um ciclo. O caminho percorrido pela heurística é pintado de cinza. Se chegar a um sorvedouro (ou seja, um vértice de grau de saída nulo), a heurística para e desiste de encontrar um ciclo.
| Heurística (n, Adj, r) |
| 11 o para u ← 1 até n faça |
| 12 oooo cor[u] ← branco |
| 13 o cor[r] ← cinza |
| 14 o u ← r |
| 15 o enquanto Adj[u] não é vazia faça |
| 16 oooo escolha v em Adj[u] |
| 17 oooo se cor[v] = cinza |
| 18 ooooooo então devolva 0 e pare |
| 19 ooooooo senão cor[v] ← cinza |
| 10 ooooooo senão u ← v |
| 11 o devolva 2 |
Na linha 8, a heurística devolve 0 pois encontrou um ciclo. Na linha 11, a heurística devolve 2 para dizer que desistiu de encontrar um ciclo, embora não possa garantir que o digrafo é acíclico. (Se o digrafo tiver um ciclo no território de r e se todas as escolhas de v na linha 6 forem "corretas", a heurística encontrará o ciclo.)
Embora um tanto ridícula, essa heurística contém o germe do algoritmo de busca em profundidade. Pode-se mesmo dizer que a heurística deu origem àquele algoritmo.
A heurística da seção anterior pode ser aperfeiçoada de modo a não desistir de encontrar um ciclo enquanto não constatar que o território de r não tem ciclos. Diremos, nesse caso, que o território de r é acíclico. Esse aperfeiçoamento da heurística resolve o seguinte subproblema do problema principal:
SubProblema: Decidir se o território de um vértice r é acíclico.
A versão aperfeiçoada da heurística nada mais é que uma variante do algoritmo de busca em profundidade. Eis a interface do algoritmo com o usuário:
| Território-Acíclico (n, Adj, r) |
| o para u ← 1 até n faça |
| oooo cor[u] ← branco |
| o devolva Terr-Acicl (r) |
Ao receber um vértice r, a rotina Terr-Acicl devolve 1 se o território de r é acíclico e 0 em caso contrário:
| Terr-Acicl (r) |
| 11 o cor[r] ← cinza |
| 12 o P ← Cria-Pilha (r) |
| 13 o enquanto P não estiver vazia faça |
| 14 oooo u ← Copia-Topo-da-Pilha (P) |
| 15 oooo v ← Próximo (Adj[u]) |
| 16 oooo se v ≠ nil |
| 17 ooooooo então se cor[v] = cinza |
| 18 ooooooo então ooo então devolva 0 e pare |
| 19 ooooooo então se cor[v] = branco |
| 10 ooooooo então ooo então cor[v] ← cinza |
| 11 ooooooo então ooo então Coloca-na-Pilha (v, P) |
| 12 ooooooo senão cor[u] ← preto |
| 13 ooooooo senão Tira-Topo-da-Pilha (P) |
| 14 o devolva 1 |
A rotina Próximo devolve o "próximo" elemento da lista que receber como argumento. Se a lista estiver vazia, Próximo devolve nil.
Para entender o funcionamento da rotina Terr-Acicl, basta observar que, no início de cada repetição do bloco de linha 4-13,
Ao final do processo iterativo, se o algoritmo devolver 1 então, em virtude dos invariantes ii, iii, iv e v, o território de r é acíclico.
O código de Terr-Acicl fica mais simples se for escrito em estilo recursivo. (Veja a versão recursiva da busca em profundidade.) A pilha de vértices passa a ser administrada pelo mecanismo de recursão, e assim fica invisível. A função Próximo também fica invisível.
| Terr-Acicl-R (u) |
| 11 o cor[u] ← cinza |
| 12 o para cada v em Adj[u] faça |
| 13 oooo se cor[v] = cinza |
| 14 ooooooo então devolva 0 e pare |
| 15 oooo se cor[v] = branco |
| 16 ooooooo então x ← Terr-Acicl-R (v) |
| 17 ooooooo então se x = 0 então devolva 0 e pare |
| 18 o cor[u] ← preto |
| 19 o devolva 1 |
Não é fácil explicar, com precisão, o que faz a rotina Terr-Acicl-R. Para dar essa explicação, convém introduzir uma generalização do conceito de ciclo que lembra a forma tipográfica do caractere "6". Um "6" é um passeio (w0,w1,…,wk−1,wk) tal que k ≥ 1, os vértices w0, w1, … , wk−1 são distintos dois a dois, e wk = wj para algum j em 0..k−1. É claro que (wj,wj+1,…,wk) é um ciclo no território de w0. Para qualquer i < k, diremos que o "6" é um prolongamento do caminho (w0,…,wi).
Podemos dizer agora o que Terr-Acicl-R faz. A rotina recebe um vértice u e um vetor cor que pinta cada vértice de branco, cinza ou preto. O vértice u é branco. O conjunto dos vértices cinza, tomados na ordem apropriada, define um caminho C. O vértice u é adjacente ao último vértice de C, de modo que C+u também é um caminho. A rotina devolve
Além disso, no segundo caso, a rotina atribui cor preta a todos os vértices no território de u. Em qualquer dos dois casos, vértices que eram pretos permanecem pretos e vértices que eram cinza não ficam brancos.
Agora que aprendemos a decidir se um território é acíclico, podemos retomar o problema de decidir se o digrafo todo é acíclico. É fácil verificar que, para qualquer ciclo O e qualquer vértice r, vale uma e apenas uma das seguintes alternativas:
Portanto, basta aplicar o algoritmo Território-Acíclico a cada vértice do digrafo. Mas é possível fazer o serviço de maneira mais eficiente se os vértices pintados de preto permanecerem pretos até o fim da execução do algoritmo. Eis o resultado:
| Digrafo-Acíclico (n, Adj) |
| 1 o para u ← 1 até n faça |
| 2 oooo cor[u] ← branco |
| 3 o para r ← 1 até n faça |
| 4 oooo se cor[r] = branco |
| 5 ooooooo então x ← Terr-Acicl (r) |
| 6 ooooooo então se x = 0 então devolva 0 e pare |
| 7 o devolva 1 |
No início de cada iteração do bloco de linhas 4-6, valem as seguintes propriedades (compare o invariante v com o invariante iii):
Portanto, na linha 7, o digrafo é acíclico.
Para calcular uma cota superior do consumo de tempo de Digrafo-Acíclico, podemos supor que nosso digrafo é acíclico e portanto a linha 8 de Terr-Acicl jamais é executada. Podemos supor também que cada invocação de Próximo, Cria-Pilha, Copia-Topo-da-Pilha, Coloca-na-Pilha e Tira-Topo-da-Pilha consome tempo constante.
Para cada valor de r, o bloco de linhas 4-13 de Terr-Acicl é executado um certo número de vezes. Qualquer que seja o valor de r, cada execução daquele bloco de linhas
Como na análise de desempenho da Busca-em-Profundidade, o consumo total das ocorrências de (b) ao longo da execução do algoritmo é Ο(n) e o consumo total de todas as ocorrências de (a) é Ο(m), sendo m o número de arcos. Assim, o consumo de tempo do algoritmo Digrafo-Acíclico é
Ο(m+n) .
Portanto, o algoritmo é linear.
o
/ \
/ \
/ \
o o
/ \ / \
o o o
/ \ / \ / \
o --- o --- o --- o
|
o
/ \
/ \
o --- o
/ \
o o
|
Esta página discutiu um algoritmo que decide se um digrafo é ou não acíclico. É fácil modificar o algoritmo de modo que ele imprima um ciclo se tal existir. Mesmo com essa modificação, entretanto, o algoritmo teria um aspecto insatisfatório: ao responder que um digrafo é acíclico, o algoritmo não fornece qualquer "certificado" que ajude um usuário cético a conferir a resposta. Continuaremos essa discussão na página Digrafos acíclicos e enumeração topológica.
