Exercício 22.4-5 de CLRS3 ou CLRS2 - Outro modo de executar ordenação topológica em um grafo acíclico dirigido \mathrm{G}=(\mathrm{V}, \mathrm{E}) é encontrar repetidamente um vértice de grau de entrada 0 , imprimi-lo e removê-lo do grafo, bem como todas as suas arestas de saída. Explique como implementar essa ideia, de modo que seja executada no tempo \mathrm{O}(\mathrm{V}+\mathrm{E}). O que acontecerá a esse algoritmo se G tiver ciclos?

Passo 1

O enunciado pede que a gente implemente a ideia “repetir: encontrar um vértice de grau de entrada 0, imprimi‑lo e removê‑lo com suas arestas de saída” para produzir uma ordenação topológica de um grafo dirigido G=(V,E), e que a implementação rode em tempo \mathrm{O}(|V|+|E|). Também pergunta o que acontece se G tiver ciclos.
Informações relevantes dadas pelo enunciado:
  • O grafo é dirigido, G=(V,E).
  • A operação permitida é remover vértices de grau de entrada 0 repetidamente até não sobrar mais.
  • Queremos uma implementação que rode em \mathrm{O}(|V|+|E|).
  • Precisamos dizer o comportamento do algoritmo caso G contenha ciclos.

Passo 2

Escolha de representação e estruturas de apoio (explicação didática).
  • Para conseguir tempo \mathrm{O}(|V|+|E|) vamos representar o grafo por listas de adjacência: para cada vértice u temos Adj[u], a lista dos vértices v tais que (u,v)\in E. Essa representação permite percorrer todas as arestas gastando tempo proporcional a |E|.
  • Precisamos manter, para cada vértice v, seu grau de entrada atual; chamaremos esse vetor de in\_deg[v]. Isso nos permite encontrar rapidamente (em tempo constante por vértice) quando um vértice atinge grau de entrada zero.
  • Para processar vértices de grau de entrada zero na ordem em que aparecem, usamos uma fila Q (FIFO). A fila garante que cada vértice seja enfileirado e desenfileirado no máximo uma vez.

Passo 3

Inicialização do vetor de graus de entrada (como calcular e por que é \mathrm{O}(|V|+|E|)).
  • Inicialize in\_deg[v]=0 para todo v\in V. Isso custa \mathrm{O}(|V|).
  • Em seguida, percorra todas as listas de adjacência: para cada u\in V e para cada v\in Adj[u] faça in\_deg[v] := in\_deg[v] + 1. Esse passo visita cada aresta exatamente uma vez, portanto custa \mathrm{O}(|E|).
  • Logo, a construção de in\_deg custa \mathrm{O}(|V|+|E|).

Passo 4

Construir a fila inicial com vértices de grau de entrada zero.
  • Percorra todos os vértices v. Se in\_deg[v] = 0 então enfileire v em Q. Esse passo é \mathrm{O}(|V|).
  • No final deste passo Q contém exatamente os vértices que hoje têm grau de entrada zero no grafo original.

Passo 5

Loop principal: remover vértice de grau zero, emitir e atualizar vizinhos (descrição passo a passo do procedimento).
  • Mantenha uma lista L (inicialmente vazia) onde iremos anexar, na ordem, os vértices impressos (essa lista será a ordenação topológica).
  • Enquanto Q não estiver vazia:
    1. Remova (desenfileire) um vértice u de Q.
    2. Anexe u ao fim de L (ou “imprima” u).
    3. Para cada v\in Adj[u]: faça in\_deg[v] := in\_deg[v] - 1. Se in\_deg[v] = 0 após a decrementação, enfileire v em Q.
  • Observação de custo: cada aresta (u,v) é considerada exatamente uma vez, no instante em que processamos u, então o total gasto nas decrementações é \mathrm{O}(|E|). Cada vértice é enfileirado e desenfileirado no máximo uma vez, então o custo total com filas é \mathrm{O}(|V|).

Passo 6

Como detectar ciclo e por que isso funciona (intuição e prova curta).
  • Conte quantos vértices foram colocados em L. Ao final, se |L| = |V| então imprimimos todos os vértices e L é uma ordenação topológica válida. Se |L| < |V| então o algoritmo terminou com Q vazio antes de processar todos os vértices — isso só pode acontecer se houver um ou mais ciclos.
  • Intuição: num ciclo todos os vértices têm grau de entrada pelo menos 1 (entre si), então nenhum deles jamais chega a ter in\_deg=0 enquanto o ciclo inteiro estiver presente; assim o algoritmo não conseguirá remover esses vértices e a fila esvazia.
  • Prova de validade do ordenamento (argumento simples): quando o algoritmo coloca u em L, todas as arestas de entrada para u já foram removidas (porque in\_deg[u]=0). Portanto nenhum predecessor de u pode aparecer depois de u em L. Assim, para toda aresta (x,y) teremos x antes de y em L, provando que L é uma ordenação topológica.

Passo 7

Análise de complexidade detalhada e conclusão de \mathrm{O}(|V|+|E|).
  • Cálculo de in\_deg: \mathrm{O}(|V|+|E|).
  • Inicialização da fila Q: \mathrm{O}(|V|).
  • Loop principal: cada vértice é enfileirado/desenfileirado no máximo uma vez \Rightarrow \mathrm{O}(|V|); e cada aresta é processada (decremento de in\_deg) exatamente uma vez \Rightarrow \mathrm{O}(|E|).
  • Somando tudo dá \mathrm{O}(|V|+|E|). Memória extra usada é O(|V|) para in\_deg e O(|V|) para Q e L.

Passo 8

Pseudocódigo compacto (para visualizar a implementação — todas as variáveis matemáticas em TeX):
  • Inicialização: para todo v\in V faça in\_deg[v]\leftarrow 0.
  • Para todo u\in V e para todo v\in Adj[u] faça in\_deg[v]\leftarrow in\_deg[v]+1.
  • Q\leftarrow fila vazia. Para todo v\in V se in\_deg[v]=0 então enfileire v em Q.
  • L\leftarrow lista vazia. Enquanto Q não vazia: desenfileire u\leftarrow Q; anexe u a L; para todo v\in Adj[u] faça in\_deg[v]\leftarrow in\_deg[v]-1; se in\_deg[v]=0 então enfileire v.
  • Ao final, se |L|<|V| então existe ciclo (não foi possível ordenar todos os vértices); caso contrário L é uma ordenação topológica.

Passo 9

Exemplos curtinhos para fixar a ideia (mão na massa mental).
  • Exemplo acíclico: V=\{1,2,3\}, E=\{(1,2),(1,3),(2,3)\}. Inicialmente in\_deg(1)=0, in\_deg(2)=1, in\_deg(3)=2. Q=[1]. Processando obtemos ordem 1,2,3.
  • Exemplo cíclico: V=\{1,2,3\}, E=\{(1,2),(2,3),(3,1)\}. Inicialmente in\_deg(1)=1, in\_deg(2)=1, in\_deg(3)=1. Q fica vazio imediatamente; o algoritmo não imprime vértices e conclui que há ciclo.

Passo 10

Resumo e observações finais (tom encorajador).
  • A ideia é simples, e a implementação com lista de adjacência + vetor de in\_deg + fila leva a um algoritmo linear em |V|+|E|.
  • Se você estiver com pressa na prova: escreva claramente a inicialização dos graus, a fila dos zeros e o loop que decrementa os graus dos vizinhos — mostre o argumento de que cada aresta é processada uma vez. Isso demonstra a complexidade e a correção. Vai dar certo, confia!

Resposta

Algoritmo: calcular in\_deg[v] para todo v percorrendo todas as listas Adj[u]; enfileirar todos os vértices com in\_deg=0 numa fila Q; enquanto Q não vazia desenfileirar u, anexar u à ordenação L e para cada v\in Adj[u] fazer in\_deg[v]\leftarrow in\_deg[v]-1 e enfileirar v se in\_deg[v]=0. Complexidade: \mathrm{O}(|V|+|E|).
Se G tem ciclos: o algoritmo terminará com Q vazio antes de emitir todos os vértices, ficando |L|<|V|; isso indica a presença de ciclo (nenhum vértice do(s) ciclo(s) chega a ter in\_deg=0), e portanto não existe ordenação topológica completa.

Exercícios relacionados