Algoritmos para Grafos, via Sedgewick | Índice remissivo

Algoritmo de ordenação topológica

Esta página discute um algoritmo de ordenação topológica para DAGs. [O adjetivo "topológica" não tem muita relação com o conceito de topologia em matemática.]

Uma extensão simples de um tal algoritmo aceita qualquer digrafo e devolve uma ordenação topológica ou mostra que tal ordenação não existe. Para provar a inexistência de uma ordenação topológica, basta exibir um ciclo. O utilitário make do sistema UNIX, por exemplo, executa um algoritmo semelhante para decidir se as regras de precedência especificadas no arquivo Makefile são consistentes.

[Esta página corresponde aproximadamente à seção 19.6 (Topological Sorting) do capítulo 19 (Digraphs and DAGs), p.183-193, do livro de Sedgewick.]

Algoritmo DFS de ordenação topológica

Imagine imprimir os vértices de um DAG, um a um, em ordem contrária à topológica (ou seja, começando com um sorvedouro em vez de uma fonte). Em cada passo desse processo, um vértice está pronto para ser impresso quando todos os arcos que saem do vértice apontam para vértices que já foram impressos. Ora, isto corresponde, precisamente, à enumeração dos vértices em pós-ordem, uma vez que DAGs não têm arcos de retorno. (Numa busca DFS, um vértice "morre" quando todos os arcos que saem dele já foram visitados. Todos os arcos visitados — exceto os de retorno — vão para vértices que já morreram; e DAGs não têm arcos de retorno!)

A função DAGts abaixo implementa essa ideia. Para representar a ordenação topológica, podemos optar por uma de duas representações: um vetor ts de vértices indexado pelos números 0..V-1 ou um vetor tsi de números indexado pelos vértices. (Uma das representações é apenas o inverso da outra.) No código abaixo optamos pela segunda representação.

static int conta, pre[maxV], tsi[maxV];

/* Recebe um DAG G e armazena em tsi[0..V-1] uma ordenação topológica de G: para cada arco v-w teremos tsi[v] < tsi[w]. (O código é cópia do Programa 19.6, p.187, de Sedgewick.) */

void DAGts( Digraph G) { 
   Vertex v; 
   conta = G->V - 1;
   for (v = 0; v < G->V; v++)  
      pre[v] = -1; 
   for (v = 0; v < G->V; v++)
      if (pre[v] == -1) 
         TSdfsR( G, v);
}

void TSdfsR( Digraph G, Vertex v) { 
   link p; 
   pre[v] = 0; 
   for (p = G->adj[v]; p != NULL; p = p->next)
      if (pre[p->w] == -1) 
         TSdfsR( G, p->w); 
   tsi[v] = conta--;
}

A função DAGts só funciona se G for um DAG, mas não é difícil modificá-la de modo que receba um digrafo arbitrário e devolva um ordenação topológica ou um ciclo.

Desempenho

A função DAGts, combinada com TSdfsR, consome tempo proporcional a V+A quando aplicada a um DAG com V vértices e A arcos. (Isso é da mesma ordem de grandeza que o tempo necessário para ler os dados.)

Exercícios

[Sedgewick 19.97, p.192] Construa as listas de adjacência do digrafo abaixo inserindo os arcos, na ordem dada, num digrafo inicialmente vazio.
```
     3-7 1-4 7-8 0-5 5-2 3-8 2-9 0-6 4-9 2-6 6-4 4-3 2-3
```
Depois, submeta o digrafo à função DAGts.
Calcule uma ordenação topológica do digrafo definido pelos arcos 0-1 0-2 0-4 1-2 2-3 4-2 4-5 5-3 6-4 6-7 7-5.
Escreva uma variante da função DAGts que represente a ordenação topológica por uma vetor ts de vértices indexado pelos números 0..V-1.
[Importante] Escreva uma extensão da função DAGts que receba um digrafo arbitrário G e produza (1) uma ordenação topológica de G ou (2) um ciclo de G.
Quantos arcos, no máximo, pode ter um DAG com V vértices?
[Muito bom] Escreva uma função que tenha o mesmo comportamento que DAGts mas seja baseada na seguinte ideia: repetidamente remova fontes do digrafo; a ordem em que os vértices são removidos dá a ordenação topológica.

Conclusão

Para todo digrafo G vale uma e apenas uma das seguintes afirmações:

G tem um ciclo;
G tem uma ordenação topológica.

(No segundo caso, G é um DAG.)