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 G.
  • Dado: executar uma busca em profundidade (DFS) em G para computar os tempos de término f(v) de cada vértice v.
  • Dado: em seguida, executar uma segunda série de buscas em profundidade no próprio grafo G (ou seja, sem transpor as arestas), varrendo os vértices na ordem crescente de tempos de término (isto é, do menor f para o maior).
  • Pergunta: esse procedimento (usar G 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).
  1. O que é componente fortemente conexa (CFC)?
\text{Uma CFC é um conjunto máximo de vértices tal que, para quaisquer }u,v\text{ no conjunto, existe um caminho de }u\text{ a }v\text{ e de }v\text{ a }u.éáé
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).
  1. O que é DFS e tempo de término f(v)?
  • Na DFS cada vértice recebe um tempo de descoberta d(v) quando é primeiro visitado e um tempo de término f(v) quando acabamos de explorar todo o seu ramo recursivo.
  • Importante: se durante a exploração de u a DFS descobre v, então a recursão só “volta” de u depois de terminar v; ou seja, f(v) < f(u) quando v é descoberto durante a visita a u.
  1. 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 u em uma componente C para um vértice v em outra componente C' (com C\neq C'), então os tempos de término satisfazem
f(u) > f(v).
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 G):
  • Caso A: algum vértice de C é descoberto (visitado) antes de qualquer vértice de C'.
    • Como existe aresta u\in C \to v\in C' (ou caminho de C para C'), quando a DFS começar em C ela eventualmente alcançará C' durante a mesma chamada recursiva (porque há caminho). Logo, todos os vértices de C' serão descobertos e terminados antes de a chamada recursiva que começou em C terminar. Portanto cada vértice de C' tem f(\cdot) menor que os vértices de C explorados naquela chamada; em particular f(u) > f(v).
  • Caso B: algum vértice de C' é descoberto antes de qualquer vértice de C.
    • Como C' e C são componentes diferentes e assumimos que existe aresta de C para C', não existe caminho de C' para C (caso contrário seriam a mesma CFC). Assim, ao explorar C' a DFS não pode alcançar C; então toda a componente C' será completamente terminada antes da DFS começar a explorar C. Logo, para quaisquer u\in C e v\in C' vale f(u) > f(v) (pois f(v) foi atribuído antes de C sequer ser descoberto).
Nos dois casos, concluímos que sempre f(u) > f(v) para toda aresta u\in C \to v\in C' 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 G processando vértices em ordem crescente de f).
  • Tome um vértice w que seja um vértice de menor tempo de término entre todos os vértices ainda não processados. Seja C_w a componente que contém w. Por minimalidade de f(w), para qualquer aresta que saia de C_w para outra componente C' (i.e., x\in C_w \to y\in C') teríamos, pela proposição, f(x) > f(y). Mas f(w) é o menor restante, logo não existe y com f(y) < f(w) entre os não-processados — a única forma de haver aresta para outra componente seria ter f(x) > f(y) com f(y) menor, o que contradiz a escolha de w. Conclusão: não existem arestas que saiam de C_w para componentes com tempo de término menor (porque w 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 G a partir de w (o vértice de menor f 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 C_w apontaria para vértices com tempo de término menor que os de C_w, e por escolha de w esses vértices já teriam sido processados (ou então não existem). Em suma: a DFS iniciada em w explora exatamente os vértices de C_w (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 A e B com aresta de A para B (ou seja, no DAG de componentes há A\to B). Qual é a relação entre seus tempos de término após a primeira DFS? Pela proposição, qualquer u\in A e v\in B satisfaz f(u) > f(v). Portanto os vértices de B têm tempos de término menores. Se processarmos em ordem crescente, visitamos B primeiro: uma DFS em G iniciada em algum vértice de B não chega a A (não existe caminho B\to A); assim identificamos B corretamente. Depois, ao processar A, os vértices de B já estarão marcados, e então A 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 G^T 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 G^T 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 G). 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 G 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 G varrendo vértices em ordem crescente de tempos de término) sempre produzirá corretamente as componentes fortemente conexas.

Exercícios relacionados