Esta página é inspirada na seção 22.4 de CLRS). Ela é uma espécie de epílogo do par de páginas Digrafos munidos de enumeração topológica e Ciclos e digrafos acíclicos, e mostra que ambas trataram essencialmente do mesmo assunto.
Veja também a seção 3.6 de KT e os verbetes Directed acyclic graph e Topological sorting na Wikipedia.
A classe dos digrafos acíclicos é idêntica à classe dos digrafos que admitem enumeração topológica. Em outras palavras,
Teorema: Um digrafo é acíclico se e somente se admite um enumeração topológica.
A parte "se" desse teorema é fácil de verificar: um digrafo munido de enumeração topológica certamente não tem ciclos. A prova do "somente se" é um pouco mais elaborada. Ela consiste em um algoritmo que, ao receber um digrafo, devolve um ciclo ou uma enumeração topológica. Discutiremos esse algoritmo ao longo das próximas seções desta página.
Uma enumeração topológica pode ser representada por uma pilha de vértices em ordem topológica inversa: o primeiro vértice da enumeração fica no topo da pilha, o segundo logo abaixo, etc., e o último fica na base da pilha. (Em particular, o vértice no topo da pilha é uma fonte e o vértice na base da pilha é um sorvedouro.) [É claro que poderíamos armazenar a enumeração na pilha em ordem direta, da base para o topo. Mas a ordem inversa é mais conveniente para o algoritmo que examinaremos abaixo.]
Um ciclo pode, também, ser representado por uma pilha de vértices. Mais precisamente, nossa pilha armazenará um "6": o primeiro vértice do "6" ficará na base da pilha, o segundo vértice ficará logo acima, etc., e o último vértice ficará no topo do pilha. Assim, o ciclo propriamente dito ficará na parte superior da pilha.
O algoritmo Digrafo-Acíclico, discutido na página Ciclos e digrafos acíclicos, pode ser adaptado para resolver dois problemas ao mesmo tempo: o problema do digrafo acíclico e o problema da enumeração topológica. O algoritmo adaptado recebe um digrafo e devolve
O algoritmo usa duas pilhas, S e T. A pilha S é a mesma que figura na rotina Terr-Acicl; ela armazena os vértices de um eventual ciclo da maneira sugerida na seção anterior. A pilha T armazena uma eventual enumeração topológica, como sugerimos na seção anterior. No fim da execução da rotina, uma e apenas uma das pilhas será devolvida como resposta.
Como de hábito, vamos supor que os vértices do digrafo são 1, … , n e os arcos são dados por listas de adjacência Adj[1..n]:
| Ciclo-ou-Enum-Topológica (n, Adj) |
| C1 o para u ← 1 até n faça |
| C2 oooo cor[u] ← branco |
| C3 o S ← Cria-Pilha-Vazia ( ) |
| C4 o T ← Cria-Pilha-Vazia ( ) |
| C5 o para r ← 1 até n faça |
| C6 oooo se cor[r] = branco |
| C7 ooooooo então x ← Explora (r, S, T) |
| C8 ooooooo então se x = 0 então devolva S e pare |
| C9 o devolva T |
O código de Ciclo-ou-Enum-Topológica é praticamente idêntico ao da rotina Digrafo-Acíclico. Para facilitar a comparação, aplicamos uma cor mais escura às linhas novas.
A rotina Explora é praticamente idêntica à rotina Terr-Acicl da página Ciclos e digrafos acíclicos. Para facilitar a comparação, usamos a mesma numeração de linhas daquela rotina. Com argumento r, Explora devolve 0 se o território de r tem um ciclo sem vértices pretos e devolve 1 em caso contrário. Antes de devolver 0, a rotina armazena um ciclo na pilha S, conforme convenção estabelecida na seção anterior. Antes de devolver 1, ela armazena os vértices pretos na pilha T.
| Explora (r, S, T) |
| 11 o cor[r] ← cinza |
| 12 o Coloca-na-Pilha (r, S) |
| 13 o enquanto S não estiver vazia faça |
| 14 oooo u ← Copia-Topo-da-Pilha (S) |
| 15 oooo v ← Próximo (Adj[u]) |
| 16 oooo se v ≠ nil |
| 17 ooooooo então se cor[v] ≠ preto |
| 18 ooooooo então ooo então Coloca-na-Pilha (v, S) |
| 19 ooooooo então ooo então se cor[v] = cinza |
| 10 ooooooo então ooo então ooo então devolva 0 e pare |
| 11 ooooooo então ooo então ooo senão cor[v] ← cinza |
| 12 ooooooo senão cor[u] ← preto |
| 13 ooooooo senão Tira-da-Pilha (S) |
| 14 ooooooo senão Coloca-na-Pilha (T, u) |
| 15 o devolva 1 |
A construção da pilha T obedece o seguinte princípio: um vértice é inserido na pilha T no momento em que fica preto. Eis os invariantes que regem a construção da pilha T: no início de cada iteração,
Portanto, na linha C9 de Ciclo-ou-Enum-Topológica, a pilha T contém uma enumeração topológica dos vértices do digrafo.
Compare nosso algoritmo Ciclo-ou-Enum-Topológica com o algoritmo Eliminação-Iterada-de-Fontes, discutido na página Digrafos munidos de enumeração topológica. Se o digrafo é acíclico, o primeiro algoritmo tem o mesmo efeito que o segundo, mas se o digrafo não é acíclico então Eliminação-Iterada-de-Fontes não é capaz de exibir um ciclo.
A análise do consumo de tempo do algoritmo Ciclo-ou-Enum-Topológica é essencialmente igual à análise do algoritmo Digrafo-Acíclico. Assim o consumo de tempo de Ciclo-ou-Enum-Topológica é
Ο(n+m) ,
sendo m o número de arcos do digrafo. Portanto, o algoritmo é linear.
Uma enumeração topológica dos vértices de um digrafo constitui uma prova facilmente verificável de que o digrafo é acíclico. Por outro lado, um ciclo constitui uma prova facilmente verificável de que o digrafo não admite enumeração topológica.
Em suma, uma enumeração topológica é um certificado da inexistência de ciclos e um ciclo é um certificado da inexistência de enumeração topológica. De posse de uma enumeração topológica, por exemplo, um usuário cético pode se convencer, por conta própria, de que o digrafo é acíclico.