MAC0338   Análise de Algoritmos

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.

Ordenação topológica

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.

Ordem topológica

Uma ordem total  v₁, v₂, . . . , v_n  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  (v_j,v_i)  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  (w₀,w₁,...,w_k-1,w_k)  de vértices tal que

(w_k,w₀) é uma aresta,

(w₀,w₁) é uma aresta, (w₁,w₂) é uma aresta, etc., (w_k-1,w_k) é 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?

Exercícios

1. Escreva um algoritmo que verifica se uma dada ordenação dos vértices é ou não é uma ordem topológica.

Sorvedouros

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.

Exercícios

2. Um grafo é acíclico se não tem ciclo. Prove que todo grafo acíclico admite uma ordem topológica dos vértices.
   
   
3. Um grafo é acíclico se não tem ciclo. Escreva uma versão simplificada do algoritmo SORVEDOURO-OU-CIRCUITO para grafos acíclicos (é claro que será preciso mudar o nome do algoritmo). Documente corretamente o seu algoritmo.
   
   
4. Um grafo é acíclico se não tem ciclo. Escreva uma versão simplificada do algoritmo SORV-OU-CIRC-COM-CORES para grafos acíclicos. É claro que será preciso mudar o nome do algoritmo. Documente corretamente o seu algoritmo.
   
   
5. Escreva uma versão melhorada de SORV-OU-CIRC-COM-CORES: em lugar de devolver NIL, a versão melhorada deve devolver a seqüência de vértices de um ciclo. SUGESTÃO: ao explorar o grafo, guarde o precedecessor de cada vértice CINZA.
   
   

Primeiro algoritmo de ordem topológica

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.

Segundo algoritmo: busca em profundidade

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.

Consumo de tempo (do segundo algoritmo)

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).

Exercícios

6. [CLR 23.3-8] Suponha que um vértice u não é sorvedouro nem fonte. Mostre que u pode fazer o papel de s na linha 4 de ORDEM-TOPOLÓGICA de tal modo que a correspondente chamada de BUSCA-EM-PROFUNDIDADE com argumento s envolva apenas o exame da lista Adj[s], sem que as linhas 9 ou 11 sejam executadas.
   
   
7. Um grafo é acíclico se não tem ciclos. Escreva uma versão simplificada do algoritmo ORDEM-TOPOLÓGICA para grafos acíclicos. Documente corretamente o seu algoritmo.
   
   
8. Escreva uma versão do algoritmo de ordenação topológica supondo que o grafo tem vértices 1, 2, . . . , n e é representado por sua matriz de adjacência A:  para cada par u,v de vértices, A[u,v]=1 se (u,v) é uma aresta e A[u,v]=0 em caso contrário.  Estime o consumo de tempo do algoritmo.
   
   
9. Escreva uma versão iterativa de BUSCA-EM-PROFUNDIDADE. Antes de fazer isso, será preciso descrever em mais detalhe a estrutura das listas de adjacência. É claro que o seu algoritmo terá uma pilha de vértices CINZA simulando a recursão.
   
   
10. Escreva uma versão melhorada de ORDEM-TOPOLÓGICA: essa versão deve devolver uma lista dos vértices em ordem topológica ou a lista dos vértices de um ciclo.
    
    
11. [IP 365] Um grafo simétrico é bicromático se é possível atribuir uma de duas cores a cada um de seus vértices de tal modo que as pontas de cada aresta tenham cores diferentes. Escreva um algoritmo que decide se um dado grafo é ou não bicromático. Se algoritmo pode consumir O(n+m) unidades de tempo, ao processar um grafo com n vértices e m arestas.
    
    
12. [CLR 23.4-5]  Escreva um algoritmo de ordenação topológica (muito diferente do que discutimos acima) baseado nas seguintes idéias. Calcule o grau de entrada de cada vértice (o grau de entrada de v é o número de arestas da forma (u,v)). Os vértices com grau de entrada igual a 0 serão os últimos da ordem topológica. Toda vez que um tal vértice u é descoberto e impresso, podemos atualizar o grau de entrada de todo vértice v tal que (u,v) é uma aresta. Mostre que o consumo de tempo do seu algoritmo é O(n+m), onde n é o número de vértices e m o número de arestas.