Exercício 22.5-3 do CLRS3 ou CLRS2-O professor Bacon afirma que o algoritmo para componentes fortemente conexas seria mais simples se usasse o grafo original (em lugar da transposta) na segunda busca em profundidade e varresse os vértices na ordem crescente de tempos de término. Esse algoritmo mais simples sempre produzirá resultados corretos?
Passo 1
O enunciado dá a descrição verbal do algoritmo do professor Bacon e pergunta se ele sempre produzirá resultados corretos. Especificamente, o que nos é dado e o que se pede:
- Dado: um grafo direcionado
. - Dado: executar uma busca em profundidade (DFS) em
para computar os tempos de término de cada vértice . - Dado: em seguida, executar uma segunda série de buscas em profundidade no próprio grafo
(ou seja, sem transpor as arestas), varrendo os vértices na ordem crescente de tempos de término (isto é, do menor para o maior). - Pergunta: esse procedimento (usar
na segunda fase e a ordem crescente de tempos de término) sempre produzirá as componentes fortemente conexas (CFCs) corretamente?
Passo 2
Vamos primeiro entender, bem devagar, as peças que o enunciado usa (sem pular etapas).
- O que é componente fortemente conexa (CFC)?
Na prática, o grafo é particionado em CFCs, e se você contrair cada CFC a um nó, obtém-se um DAG (grafo acíclico) chamado grafo de componentes (condensação).
- O que é DFS e tempo de término
?
- Na DFS cada vértice recebe um tempo de descoberta
quando é primeiro visitado e um tempo de término quando acabamos de explorar todo o seu ramo recursivo. - Importante: se durante a exploração de
a DFS descobre , então a recursão só “volta” de depois de terminar ; ou seja, quando é descoberto durante a visita a .
- Intuição que usamos (resumida):
- As relações entre tempos de término das CFCs carregam informação topológica sobre o DAG de componentes. Vamos explorar isso com cuidado no próximo passo.
Passo 3
A ideia-chave que vamos provar é esta propriedade essencial (lembrando: explico com calma e por casos):
Proposição: se existir uma aresta de um vértice
em uma componente
para um vértice
em outra componente
(com
), então os tempos de término satisfazem
Vou provar isso com atenção para você poder reproduzir na prova.
Prova por análise de dois casos (da execução da primeira DFS em
):
-
Caso A: algum vértice de
é descoberto (visitado) antes de qualquer vértice de . - Como existe aresta
(ou caminho de para ), quando a DFS começar em ela eventualmente alcançará durante a mesma chamada recursiva (porque há caminho). Logo, todos os vértices de serão descobertos e terminados antes de a chamada recursiva que começou em terminar. Portanto cada vértice de tem menor que os vértices de explorados naquela chamada; em particular .
- Como existe aresta
-
Caso B: algum vértice de
é descoberto antes de qualquer vértice de . - Como
e são componentes diferentes e assumimos que existe aresta de para , não existe caminho de para (caso contrário seriam a mesma CFC). Assim, ao explorar a DFS não pode alcançar ; então toda a componente será completamente terminada antes da DFS começar a explorar . Logo, para quaisquer e vale (pois foi atribuído antes de sequer ser descoberto).
- Como
Nos dois casos, concluímos que sempre
para toda aresta
entre componentes distintas. Ou seja: as arestas entre componentes apontam sempre de vértices com tempo de término maior para vértices com tempo de término menor.
Passo 4
Agora usemos essa propriedade para entender a segunda fase do algoritmo proposto (rodar DFS em
processando vértices em ordem crescente de
).
-
Tome um vértice
que seja um vértice de menor tempo de término entre todos os vértices ainda não processados. Seja a componente que contém . Por minimalidade de , para qualquer aresta que saia de para outra componente (i.e., ) teríamos, pela proposição, . Mas é o menor restante, logo não existe com entre os não-processados — a única forma de haver aresta para outra componente seria ter com menor, o que contradiz a escolha de . Conclusão: não existem arestas que saiam de para componentes com tempo de término menor (porque foi escolhido mínimo) — na verdade, pela proposição, todas as arestas entre componentes vão de tempos maiores para menores, então um vértice de tempo mínimo pertence necessariamente a uma componente que não aponta para componentes cujo vértice não processado tenha tempo ainda menor. -
Na prática isso significa que, ao iniciar uma DFS em
a partir de (o vértice de menor não-processado), essa DFS não pode alcançar vértices de outras componentes que ainda não foram processadas — porque qualquer aresta que saísse de apontaria para vértices com tempo de término menor que os de , e por escolha de esses vértices já teriam sido processados (ou então não existem). Em suma: a DFS iniciada em explora exatamente os vértices de (a própria componente). -
Assim, cada chamada da segunda fase identifica uma CFC inteira e somente ela. Ao marcar os vértices visitados e pular os já visitados, percorremos componente por componente corretamente.
Passo 5
Exemplo concreto e curto para fixar a intuição (faça mentalmente na prova, ajuda bastante):
Considere duas CFCs
e
com aresta de
para
(ou seja, no DAG de componentes há
). Qual é a relação entre seus tempos de término após a primeira DFS? Pela proposição, qualquer
e
satisfaz
. Portanto os vértices de
têm tempos de término menores. Se processarmos em ordem crescente, visitamos
primeiro: uma DFS em
iniciada em algum vértice de
não chega a
(não existe caminho
); assim identificamos
corretamente. Depois, ao processar
, os vértices de
já estarão marcados, e então
será identificada sozinha. Esse raciocínio generaliza para todo o DAG de componentes.
Passo 6
Conclusão formal e observação final:
-
A razão pela qual a versão tradicional usa
e ordem decrescente é porque, nessa formulação, o vértice com maior tempo de término pertence a uma componente “especial” (e a DFS em a partir dele não vaza para outras componentes). Mas a análise acima mostra que a mesma coisa pode ser obtida sem transpor as arestas, apenas trocando a ordem (usar ordem crescente em ). Ambos os procedimentos usam a mesma propriedade fundamental dos tempos de término entre componentes. -
Portanto o algoritmo de Bacon é correto: a segunda fase, executada em
com ordem crescente de tempos de término, extrai exatamente as componentes fortemente conexas.
Resposta
Sim. O algoritmo de Bacon (segunda DFS no próprio
varrendo vértices em ordem crescente de tempos de término) sempre produzirá corretamente as componentes fortemente conexas.