Componentes Fortemente Conexos¶

Em um grafo direcionado, os vértices u e v pertencem ao mesmo componente fortemente conexo (SCC) quando cada um pode alcançar o outro. Os SCCs particionam os vértices.

Contraia cada SCC em um único metavértice. O grafo de condensação resultante é direcionado e acíclico: um ciclo entre componentes os tornaria mutuamente alcançáveis e, portanto, um único componente.

Kosaraju–Sharir¶

Execute uma DFS e registre os vértices por tempo de término.
Inverta todas as arestas.
Processe os vértices em ordem decrescente do tempo de término original, executando DFS no grafo invertido. Cada novo percurso produz um SCC.

Os dois percursos e a inversão usam tempo Θ(V + E), com armazenamento adicional Θ(V + E) quando o grafo transposto é materializado.

Tarjan¶

O algoritmo de Tarjan usa uma única DFS, uma pilha, índices de descoberta e valores low-link. Um vértice é a raiz de um SCC quando seu low-link é igual ao seu índice de descoberta; a pilha é desempilhada até essa raiz. O algoritmo também usa tempo Θ(V + E) e espaço de trabalho Θ(V) além do grafo.

O low-link não é simplesmente o menor número entre os vizinhos. Sua atualização distingue uma aresta da árvore DFS de uma aresta para um vértice ainda presente na pilha ativa.

Aplicações¶

SCCs revelam ciclos de dependência mútua, permitem o processamento topológico da condensação de um grafo direcionado e apoiam decomposições para alcançabilidade e análise de programas.

Exercícios¶

Prove que o grafo de condensação é acíclico.
Execute os dois algoritmos em um grafo com três SCCs.
Explique por que componentes conexos são insuficientes para grafos direcionados.