Página preparada por Paulo
Feofiloff para a disciplina MAC 338 Análise de
Algoritmos, versão 1999.
O endereço original desta página é http://www.ime.usp.br/~pf/mac338/aulas/topo.htm.
Esta página é um resumo do capítulo 23, seções 3 e 4, de CLR. Palavras chave: grafos orientados acíclicos, busca em profundidade.
Uma ordem total v1, v2, . . . , vn dos vértices de um grafo é topológica se todas as arestas apontam no mesmo sentido. Mais especificamente, a ordem é topológica se
para cada aresta (vj,vi) temos j > i ,
ou seja, se todas as arestas apontam "pra trás". (A definição do CLR diz que todas as arestas devem apontar "pra frente", mas no fundo estamos falando da mesma coisa.)
PROBLEMA: Colocar os vértices de um grafo em ordem topológica.
Não é difícil perceber que o problema pode não ter solução: se o grafo tem um ciclo então qualquer ordem dos vértices terá pelo menos uma aresta apontando na direção errada. "O que é um ciclo?", perguntareis vós. Um ciclo (orientado), responderei eu, é uma seqüência (w0,w1,...,wk-1,wk) de vértices tal que
(wk,w0) é uma aresta,
(w0,w1) é uma aresta, (w1,w2) é uma aresta, etc., (wk-1,wk) é uma aresta. (Compare com a definição de caminho.) Note que o ciclo é orientado: todas as suas arestas apontam "pra frente".
Pergunta importante: que mais, além de um ciclo, pode impedir um grafo de possuir uma ordem topológica?
Um sorvedouro (ou ralo, ou buraco negro) é um vértice do qual não "saem" arestas, ou seja, um vértice que não é ponta inicial de aresta alguma. É claro que o primeiro vértice de uma ordem topológica é necessariamente um sorvedouro.
Sorvedouros são mais-ou-menos complementares com ciclos: se um grafo não tem sorvedouro então certamente tem algum ciclo. Do ponto de vista de nosso problema de ordenação topológica, se eu encontrar um ciclo durante a tentativa de encontrar um sorvedouro, posso parar. Eis um algoritmo que faz isso; ele devolve um sorvedouro ou devolve NIL se encontrar um ciclo.
O algoritmo deixa um rastro à medida que percorre um caminho no grafo. Se o algoritmo tentar cruzar seu próprio rastro, temos um ciclo. Se chegar a beco, temos um sorvedouro.
SORVEDOURO-OU-CIRCUITO (n, Adj)
para v := 1 até n faça
rastro[v] := BRANCO
seja u um vértice qualquer
enquanto 0 = 0 faça
rastro[u] := CINZA
se Adj[u] <> NIL
então seja v um vértice em Adj[u]
se rastro[v] = CINZA
então devolva NIL
senão u := v
senão devolva u
(Os comandos "seja ..." parecem um pouco estranhos, mas são fáceis de implementar. Eu não estou mostrando a implementação porque não quero entrar em maiores detalhes sobre a estrutura de Adj.) Examine o código com cuidado: você tem certeza de que o "enquanto 0 = 0" não produz um loop infinito?
Agora já sabemos como encontrar o primeiro vértice da ordem topológica (ou um ciclo). Como encontrar o segundo, terceiro, etc.? Digamos que nosso grafo tem dois tipos de vértices: os NEGROs (que já foram colocados na ordem topológica e portanto estão "fora do jogo") e os BRANCOs. (Não confunda a cor do vértice com o rastro que o algoritmo deixa.) O algoritmo abaixo procura um sorvedouro no grafo G-N, onde N é o conjunto dos vértices NEGROs. O que é um sorvedouro em G-N? Fácil: trata-se de um vértice u tal que cor[v] = NEGRO para toda aresta (u,v).
O algoritmo só faz sentido se existe pelo menos um vértice BRANCO. O usuário deve fornecer um tal vértice u.
1
2
3
4
5
6
7
8
9
SORV-OU-CIRC-COM-CORES (n, Adj, cor, u)
comentário: cor[u] = BRANCO
para v := 1 até n faça
rastro[v] := BRANCO
enquanto 0 = 0 faça
rastro[u] := CINZA
se existe v em Adj[u] tal que cor[v] = BRANCO
então se rastro[v] = CINZA
então devolva NIL
senão u := v
senão devolva u
O comando "se existe ..." da linha 5 parece um pouco estranho mas é fácil implementar: basta percorrer a lista Adj[u] à procura de um vértice BRANCO.
Quanto tempo o algoritmo consome? O loop das linhas 3-9 é repetido no máximo n vezes, pois em cada iteração um novo vértice fica CINZA. Em cada iteração, a lista Adj[u] é percorrida na linha 5. Essa lista tem <= m elementos, onde m é o número de arestas (a delimitação é exagerada, mas não sei fazer melhor). Conclusão: o algoritmo consome O(nm) unidades de tempo.
Correto mas exagerado. É mais justo dizer que o loop das linhas 3-9 consome O(m) unidades de tempo pois durante o processo todo cada aresta é examinada (na linha 5) no máximo uma vez (graças ao "se" da linha 6). (Pense assim: toda vez que visita uma nova aresta (u,v) na linha 5, o algoritmo cobra $4. Esta quantia é mais que suficiente para manter o algoritmo andando até visitar a próxima aresta. A visita a uma próxima aresta pode acontecer dentro da própria linha 5, ou pode ser precedida pela execução das linhas 6,8,4.) Além disso, temos as linhas 1-2, o que dá um total de
O(n+m).
Eu acho que esta estimativa é justa: eu acho que o algoritmo consome Omega(n+m) no pior caso.
Como é a "saída" de nosso algoritmo? Para simplificar nossa vida (que já é tão difícil), vamos adotar uma saída suja. Nosso algoritmo imprime uma lista de vértices; a lista pode ser interrompida pela mensagem "encontrei um ciclo" (caso em que não existe ordem topológica); se a lista não for interrompida, ela estará em ordem topológica.
TOPO-RASCUNHO (n, Adj)
para v := 1 até n faça
cor[v] := BRANCO
para s := 1 até n faça
u := s
enquanto cor[u] = BRANCO faça
x := SORV-OU-CIRC-COM-CORES (n, Adj, cor, u)
se x = NIL
então imprima "encontrei ciclo" e pare
senão cor[x] := NEGRO
imprima x
No início de cada iteração de nosso algoritmo todo vértice é BRANCO ou NEGRO. Os vértices NEGROs já foram colocados na ordem certa. Cada iteração procura um sorvedouro em G-N, onde N é o conjunto de todos os vértices NEGROS.
Acho que o algoritmo consome O(nm) tempo. Acho até que consome Omega(nm) no pior caso.
Não gostei. Deve haver algo melhor.
Por que TOPO-RASCUNHO é ineficiente? O algoritmo SORV-OU-CIRC-COM-CORES constroi um caminho CINZA para descobrir um sorvedouro; depois entrega o sorvedouro ao TOPO-RASCUNHO e esquece o caminho CINZA que construiu com tanto sacrifício. Quando TOPO-RASCUNHO chamar SORV-OU-CIRC-COM-CORES de novo, a penosa construção de um caminho CINZA começará "do zero".
Meu segundo algoritmo procura procura aproveitar as observações acima e faz uma busca em profundidade no grafo. A saída do algoritmo tem uma saída ainda mais suja que a do anterior (para fazer uma saída mais limpa eu teria que complicar o código). O algoritmo imprime uma lista de vértices, possivelmente entremeada com mensagens "encontrei um ciclo". Se não houver mensagem alguma desse tipo, a lista dos vértices estará em ordem topológica; caso contrário, o grafo não admite ordem topológica alguma.
1
2
3
4
5
ORDEM-TOPOLÓGICA (n, Adj)
para v := 1 até n faça
cor[v] := BRANCO
para s := 1 até n faça
se cor[s] = BRANCO
então BUSCA-EM-PROFUNDIDADE (s,cor,n,Adj)
O grosso do algoritmo está na rotina recursiva BUSCA-EM-PROFUNDIDADE, que é muito parecida com SORV-OU-CIRC-COM-CORES mas mais esperta (em particular, o vetor rastro agora se confunde com o vetor cor):
6
7
8
9
10
11
12
13
BUSCA-EM-PROFUNDIDADE (u, cor, n, Adj)
cor[u] := CINZA
para cada v em Adj[u] faça
se cor[v] = CINZA
então imprima "encontrei ciclo"
senão se cor[v] = BRANCO
então BUSCA-EM-PROFUNDIDADE (v,cor,n,Adj)
cor[u] := NEGRO
imprima u
Infelizmente não é fácil explicar o que, exatamente, BUSCA-EM-PROFUNDIDADE faz. Apesar da dificuldade, eu vou tentar. O BUSCA-EM-PROFUNDIDADE recebe um grafo cujos vértices estão coloridos com três cores: BRANCO, CINZA e NEGRO. Recebe também um vértice BRANCO u. Os vértices CINZA formam um caminho C que termina em u. O algoritmo só toma conhecimento de um certo subgrafo H do grafo dado: trata-se do subgrafo formado pelos vértices que puderem ser alcançados a partir de u por meio de caminhos BRANCOs. O algoritmo muda para NEGRO a cor de cada vértice de H e imprime uma lista de todos os vértices de H, possivelmente entremeada com mensagens "encontrei ciclo"; se não houver mensagem alguma então a lista estará exibindo os vértices de H em ordem topológica. Os eventuais ciclos que o algoritmo detecta pertencem ao grafo H+C. Ufa! É isso que o algoritmo BUSCA-EM-PROFUNDIDADE faz.
Quanto tempo o algoritmo ORDEM-TOPOLÓGICA consome? A análise não é fácil.
Em primeiro lugar, é preciso se convencer de que o sub-algoritmo BUSCA-EM-PROFUNDIDADE é chamado (nas linhas 5 e 11) exatamente uma vez para cada vértice. (De fato, BUSCA-EM-PROFUNDIDADE é invocado com argumento u somente se cor[u] = BRANCO; e durante a execução do sub-algoritmo a cor de u é alterada para NEGRO, o que impede nova invocação com argumento u.)
Agora observe que a chamada BUSCA-EM-PROFUNDIDADE com argumento u examina (linhas 7-10) as arestas que saem de u. (É claro que outras arestas também serão examinadas em virtude da chamada recursiva na linha 11. Mas essa atividade será associada, em nossa análise, a outras chamadas de BUSCA-EM-PROFUNDIDADE.)
Portanto, ao longo de toda a execução do algoritmo ORDEM-TOPOLÓGICA, cada aresta do grafo é examinada exatamente uma vez. O exame de uma aresta (u,v) consome uma quantidade limitada de tempo (verificar cor[v] na linha 8, imprimir mensagem na linha 9, verificar cor[v] novamente na linha 10, disparar chamada do sub-algoritmo BUSCA-EM-PROFUNDIDADE na linha 11). Portanto, o tempo total gasto na execução das linhas 7-11, ao longo de toda a vida de ORDEM-TOPOLÓGICA, é O(m).
Além disso, há ainda um consumo de O(n) por conta das linhas 6 e 12-13 e mais outro tanto por conta das linhas 1-2. Enfim, o glorioso total é apenas
O(n+m).