Exercício 22.4-5 de CLRS3 ou CLRS2 - Outro modo de executar ordenação topológica em um grafo acíclico dirigido
é 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
. 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
, e que a implementação rode em tempo
. Também pergunta o que acontece se
tiver ciclos.
Informações relevantes dadas pelo enunciado:
Informações relevantes dadas pelo enunciado:
- O grafo é dirigido,
. - A operação permitida é remover vértices de grau de entrada
repetidamente até não sobrar mais. - Queremos uma implementação que rode em
. - Precisamos dizer o comportamento do algoritmo caso
contenha ciclos.
Passo 2
Escolha de representação e estruturas de apoio (explicação didática).
- Para conseguir tempo
vamos representar o grafo por listas de adjacência: para cada vértice temos , a lista dos vértices tais que . Essa representação permite percorrer todas as arestas gastando tempo proporcional a . - Precisamos manter, para cada vértice
, seu grau de entrada atual; chamaremos esse vetor de . 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
(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 é
).
- Inicialize
para todo . Isso custa . - Em seguida, percorra todas as listas de adjacência: para cada
e para cada faça . Esse passo visita cada aresta exatamente uma vez, portanto custa . - Logo, a construção de
custa .
Passo 4
Construir a fila inicial com vértices de grau de entrada zero.
- Percorra todos os vértices
. Se então enfileire em . Esse passo é . - No final deste passo
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
(inicialmente vazia) onde iremos anexar, na ordem, os vértices impressos (essa lista será a ordenação topológica). - Enquanto
não estiver vazia: - Remova (desenfileire) um vértice
de . - Anexe
ao fim de (ou “imprima” ). - Para cada
: faça . Se após a decrementação, enfileire em .
- Remova (desenfileire) um vértice
- Observação de custo: cada aresta
é considerada exatamente uma vez, no instante em que processamos , então o total gasto nas decrementações é . Cada vértice é enfileirado e desenfileirado no máximo uma vez, então o custo total com filas é .
Passo 6
Como detectar ciclo e por que isso funciona (intuição e prova curta).
- Conte quantos vértices foram colocados em
. Ao final, se então imprimimos todos os vértices e é uma ordenação topológica válida. Se então o algoritmo terminou com 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
(entre si), então nenhum deles jamais chega a ter 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
em , todas as arestas de entrada para já foram removidas (porque ). Portanto nenhum predecessor de pode aparecer depois de em . Assim, para toda aresta teremos antes de em , provando que é uma ordenação topológica.
Passo 7
Análise de complexidade detalhada e conclusão de
.
- Cálculo de
: . - Inicialização da fila
: . - Loop principal: cada vértice é enfileirado/desenfileirado no máximo uma vez
; e cada aresta é processada (decremento de ) exatamente uma vez . - Somando tudo dá
. Memória extra usada é para e para e .
Passo 8
Pseudocódigo compacto (para visualizar a implementação — todas as variáveis matemáticas em TeX):
- Inicialização: para todo
faça . - Para todo
e para todo faça . -
fila vazia. Para todo se então enfileire em . -
lista vazia. Enquanto não vazia: desenfileire ; anexe a ; para todo faça ; se então enfileire . - Ao final, se
então existe ciclo (não foi possível ordenar todos os vértices); caso contrário é uma ordenação topológica.
Passo 9
Exemplos curtinhos para fixar a ideia (mão na massa mental).
- Exemplo acíclico:
, . Inicialmente , , . . Processando obtemos ordem . - Exemplo cíclico:
, . Inicialmente , , . 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
+ fila leva a um algoritmo linear em . - 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
para todo
percorrendo todas as listas
; enfileirar todos os vértices com
numa fila
; enquanto
não vazia desenfileirar
, anexar
à ordenação
e para cada
fazer
e enfileirar
se
. Complexidade:
.
Se tem ciclos: o algoritmo terminará com
vazio antes de emitir todos os vértices, ficando
; isso indica a presença de ciclo (nenhum vértice do(s) ciclo(s) chega a ter
), e portanto não existe ordenação topológica completa.
Se