Algoritmos para Grafos, via Sedgewick  |  Índice remissivo

Algoritmos de ordenação topológica

Esta página discute algoritmos que produzem ordenação topológica de DAGs.  Ao receber um digrafo G, um tal algoritmo deveria devolver (1) uma ordenação topológica de G ou (2) um ciclo em G.

(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 de eliminação de fontes

A seguinte função produz uma ordenação topológica  ts[0..V-1]  de um digrafo desde que o digrafo seja um DAG. Se o digrafo não for um DAG, ela desiste da tarefa  (mas poderia, com um pouco mais de esforço, exibir um ciclo).

/* Armazena em ts[0..i-1] uma permutação de um subconjunto do conjunto de vértices de G e devolve o valor de i.  Se i = G->V então ts[0..i-1] é uma ordenação topológica de G.  Caso contrário, G não é um DAG (e há um ciclo cujos vértices não estão em ts[0..i-1]). */

/* (O código é uma versão ligeiramente modificada do Programa 19.8, p.190, de Sedgewick.) */

int DAGts1 (Digraph G, Vertex ts[]) { 
   int i, in[maxV]; Vertex v; link p;
   for (v = 0; v < G->V; v++) 
      in[v] = 0; 
   for (v = 0; v < G->V; v++) 
      for (p = G->adj[v]; p != NULL; p = p->next)
         in[p->w]++;
   /* A */
   QUEUEinit(G->V);
   for (v = 0; v < G->V; v++)
      if (in[v] == 0) 
         QUEUEput(v);
   /* B */
   for (i = 0; /* C */ !QUEUEempty(); i++) {
      ts[i] = v = QUEUEget();
      for (p = G->adj[v]; p != NULL; p = p->next)
         if (--in[p->w] == 0) 
            QUEUEput(p->w);
   }
   return i;
}

No ponto A, para cada vértice v, o número in[v] é o grau de entrada de v.  No ponto B, a fila (queue) armazena todos os vértices que têm grau de entrada nulo.

No processo iterativo final, é relevante o subdigrafo de G induzido pelos conjunto de vértices que não estão no vetor ts[0..i-1].  Digamos que esse subdigrafo induzido é H.  Podemos dizer então que, a cada passagem pelo ponto C, a fila contém exatamente os vértices de H que têm grau de entrada 0 em H.

Exemplo:  O utilitário make do sistema UNIX executa uma função semelhante à DAGts1 para decidir se as regras de precedência especificadas no arquivo Makefile são consistentes.

Exercícios

1. 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 DAGts1.

2. Que acontece se usarmos uma pilha no lugar da fila que usamos na função DAGts1 de ordenação topológica? 
3. Escreva uma função que receba uma digrafo G e diga se G é ou não um DAG.
4. Escreva uma função que receba um digrafo sem fontes e imprima um ciclo do digrafo.
5. Escreva uma variante da função DAGts1 que recebe um DAG G representado por sua matriz de adjacência e produz uma ordenação topológica "inversa" de G (ou seja, uma ordenação que começa pelos vértices de grau de saída nulo).
6. Escreva uma variante da função DAGts1 que recebe um DAG G representado por listas de adjacência e produz uma ordenação topológica "inversa" dos vértices de G (ou seja, uma ordenação que começa pelos vértices de grau de saída nulo).
7. Escreva uma variante da função DAGts1 que recebe um DAG G e produz um vetor st indexado pelos vértices tal que st[v] < st[w] para todo arco v-w.
8. Escreva uma função que gere um DAG aleatório com V vértices e A arcos.
9. Modifique o código de DAGts1 de ordenação topológica de modo que ela calcule, para cada vértice w, o número de caminhos que começam em alguma fonte e terminam em w. 

Algoritmo DFS

O algoritmo de busca em profundidade calcula uma ordenação topológica de maneira muito natural:  basta registrar os vértices visitados "em pós-ordem".  A versão abaixo só funciona se o digrafo for um DAG, mas não é difícil modificá-la de modo que receba qualquer digrafo e devolva um ordenação topológica ou um ciclo.

static int conta;
static int lbl[maxV];

/* Recebe um DAG G e armazena em ts[0..V-1] uma ordenação topológica de G.  (O código é cópia do Programa 19.6, p.187, de Sedgewick.) */

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

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

Exercícios

10. Escreva uma variante da função DAGts2 que receba um digrafo G e produza uma ordenação topológica de G ou imprima um ciclo de G.