Exercício 22.5-5 do CLRS3 ou CLRS2. Dê um algoritmo de tempo \mathrm{O}(\mathrm{V}+\mathrm{E}) para calcular o grafo de componentes de um grafo dirigido \mathrm{G}=(\mathrm{V}, \mathrm{E}). Certifique-se de que haja no máximo uma aresta entre dois vértices no grafo de componentes que o seu algoritmo produz.

Passo 1

O enunciado pede que, dado um grafo dirigido G=(V,E), a gente produza o grafo de componentes fortemente conectadas (chamado também de condensação) em tempo \mathrm{O}(|V|+|E|). Deve haver no máximo uma aresta entre dois vértices no grafo de componentes que o algoritmo produz.
Informações relevantes fornecidas:
  • Entrada: um grafo dirigido G=(V,E), representado por listas de adjacência (uma lista de arestas saindo de cada vértice).
  • Saída esperada: um grafo dirigido G_C=(V_C,E_C) onde:
    • Cada vértice em V_C representa uma componente fortemente conectada (SCC) de G.
    • Há uma aresta (C_i \to C_j) em E_C se e somente se existe pelo menos uma aresta (u\to v)\in E com u em C_i e v em C_j, e devemos garantir que haja no máximo uma aresta entre quaisquer C_i e C_j.
  • Restrições de tempo: tempo total \mathrm{O}(|V|+|E|).

Passo 2

Ideia geral do algoritmo (resumida; vamos detalhar cada parte depois):
  1. Encontrar as componentes fortemente conectadas de G e atribuir a cada vértice u\in V um identificador de componente \mathrm{comp}[u].
  2. Construir o grafo contraído (grafo de componentes) G_C cuja lista de adjacência contém, para cada componente i, os componentes distintos j tais que existe alguma aresta de um vértice de i para um vértice de j em G. Ao construir essas listas, garantir que cada par (i,j) apareça no máximo uma vez.
Motivo da escolha (breve): calcular SCCs é necessário para saber como agrupar vértices; depois percorrer as arestas originais e mapear para arestas entre componentes gera o grafo de componentes. A dificuldade técnica é evitar múltiplas arestas paralelas entre dois componentes sem exceder \mathrm{O}(|V|+|E|) de tempo — usaremos uma técnica simples de marcação por componente para deduplicar em tempo proporcional ao número de arestas únicas entre componentes.

Passo 3

Como encontrar as componentes fortemente conectadas (SCCs) em \mathrm{O}(|V|+|E|): explicação do método usado (Kosaraju), passo a passo e por que é linear.
Conceito básico de DFS e tempos de finalização:
  • Uma busca em profundidade (DFS) em grafos visita vértices a partir de um vértice inicial, seguindo arestas e marcando vértices como visitados para não repetir. Usamos um vetor \mathrm{visited}[u] inicialmente falso.
  • Ao finalizar a exploração de um vértice u (todas as arestas saindo de u foram processadas), registramos u numa pilha ou lista de ordem de finalização (push u em uma pilha). Essa ordem será usada na segunda fase.
Algoritmo (primeira fase):
  • Para cada vértice u\in V, se \mathrm{visited}[u] for falso, chama-se DFS-visit(u):
    • marca \mathrm{visited}[u]= true,
    • para cada v na lista de adjacência de u, se \mathrm{visited}[v] é falso, chama DFS-visit(v),
    • ao terminar, push u numa pilha \mathrm{S}.
  • Custo: cada aresta é examinada no máximo uma vez, cada vértice processado uma vez, logo tempo \mathrm{O}(|V|+|E|).

Passo 4

Construir o grafo transposto G^T (trocar direção de todas as arestas) e explicar o porquê e o custo.
Construção de G^T:
  • G^T tem mesmas vértices V. Para cada aresta (u\to v)\in E, inserimos (v\to u) em G^T.
  • Se G está em listas de adjacência, percorremos todas as listas; para cada aresta fazemos uma inserção em G^T. Isso custa \mathrm{O}(|V|+|E|) (visitar cada lista + inserir cada aresta uma vez).
Por que usar G^T:
  • Kosaraju usa o fato de que, se processarmos os vértices em ordem de decrescimento dos tempos de finalização obtidos na primeira DFS, as DFSs no grafo transposto retornarão exatamente os vértices de cada SCC como uma árvore de recobrimento. Assim identificamos SCCs.

Passo 5

Segunda fase de Kosaraju: obter rótulos de componente \mathrm{comp}[u] fazendo DFSs em G^T na ordem de decrescimento de finalização.
Procedimento detalhado:
  • Inicialize \mathrm{comp}[u] \leftarrow undefined para todo u e \mathrm{visited}[u]\leftarrow false para o segundo passe.
  • Enquanto a pilha \mathrm{S} não estiver vazia: pop u de \mathrm{S}. Se \mathrm{visited}[u] for falso, iniciar uma DFS-visit-assign(u, id) em G^T que:
    • marca \mathrm{visited}[u]= true, \mathrm{comp}[u]= id,
    • para cada v em adjacência de u em G^T, se \mathrm{visited}[v] é falso, chama recursivamente DFS-visit-assign(v, id).
  • Ao terminar a DFS de um componente, incrementa id (próximo identificador de componente).
  • Ao final teremos \mathrm{comp}[u]\in\{1,\dots,k\} onde k é o número de SCCs.
  • Custo: novamente \mathrm{O}(|V|+|E|), pois cada aresta e cada vértice é visitado no máximo uma vez nesta fase.

Passo 6

Resumo do que temos até agora (resultado intermediário que vamos usar):
  • Um inteiro k = número de componentes.
  • Um vetor \mathrm{comp}[\,\cdot\,] tal que cada vértice u\in V tem \mathrm{comp}[u]\in\{1,\dots,k\}.
  • Objetivo agora: construir G_C=(V_C,E_C) onde V_C=\{1,\dots,k\} (cada número representa uma componente) e E_C contém arestas sem paralelas (ou seja, no máximo uma aresta entre quaisquer i e j).

Passo 7

Construção do grafo de componentes sem criar arestas paralelas — técnica eficiente que garante \mathrm{O}(|V|+|E|).
Problema a resolver aqui: ao percorrer cada aresta original (u\to v), se \mathrm{comp}[u]\neq\mathrm{comp}[v] devemos adicionar aresta (\mathrm{comp}[u]\to\mathrm{comp}[v]). Se fizermos isso sem checar, poderemos inserir várias cópias da mesma aresta entre dois componentes. Precisamos deduplicar mantendo complexidade linear.
Técnica de marcação por componente (sem usar estruturas pesadas):
  • Vamos criar para cada componente i uma lista de adjacência vazia \mathrm{AdjC}[i] (o grafo G_C).
  • Teremos um vetor auxiliar \mathrm{seen}[1..k] inicializado com falso (ou zeros).
  • Percorremos todas as arestas originais (u\to v)\in E:
    • Seja i=\mathrm{comp}[u] e j=\mathrm{comp}[v].
    • Se i=j então ignore — arestas internas à mesma componente não geram arestas no G_C.
    • Caso contrário, testamos \mathrm{seen}[j] relativo ao componente-fonte i. Precisamos que esse teste seja rápido e que possamos “limpar” as marcações de forma eficiente após processarmos todas as arestas que saem do componente i.
  • Implementação eficiente para cada componente i:
    • Percorra todos os vértices u cujo \mathrm{comp}[u]=i e em cada um percorra suas arestas (u\to v). (Para obter os vértices por componente podemos, se quisermos, manter durante a etapa de rotulagem uma lista de vértices por componente — isso custa \mathrm{O}(|V|) para construir.)
    • Para o componente corrente i, mantenha uma lista temporária \mathrm{newNbrs} vazia.
    • Para cada aresta (u\to v) encontrada, calcule j=\mathrm{comp}[v].
      • Se j\neq i e \mathrm{seen}[j] for falso, então:
        • adiciona j em \mathrm{AdjC}[i],
        • adiciona j em \mathrm{newNbrs},
        • seta \mathrm{seen}[j]= true.
      • Caso \mathrm{seen}[j] já seja true, ignora (já adicionamos anteriormente).
    • Depois de processar todos os vértices u com \mathrm{comp}[u]=i, percorra \mathrm{newNbrs} e para cada j faça \mathrm{seen}[j]\leftarrow false (limpeza). Assim, limpamos apenas os marcadores que foram realmente usados, em tempo proporcional ao número de vizinhos distintos encontrados.
  • Por que isso é \mathrm{O}(|V|+|E|)?
    • Cada aresta original (u\to v) é examinada uma vez quando percorremos as arestas dos vértices; logo custo \mathrm{O}(|E|) para os exames.
    • A cada vez que encontramos um novo vizinho distinto j para um componente i fazemos uma inserção em \mathrm{AdjC}[i] e um push em \mathrm{newNbrs}; cada vizinho distinto corresponde a uma aresta distinta no grafo contraído. O total de vizinhos distintos sobre todos os componentes é |E_C|\le |E|.
    • A limpeza de \mathrm{seen} faz um trabalho proporcional ao número de vizinhos distintos por componente; somando sobre todos os componentes dá \mathrm{O}(|E_C|)\le\mathrm{O}(|E|).
    • Construir as listas de vértices por componente custa \mathrm{O}(|V|) se armazenarmos cada vértice em uma lista pelo seu \mathrm{comp}[u].
    • Portanto tempo total desta etapa é \mathrm{O}(|V|+|E|).

Passo 8

Pseudocódigo compacto e detalhado (cada linha usa notação simples; todas as variáveis matemáticas em TeX):
Inicializações:
\text{stack }S \leftarrow \text{vazia}
\text{visited}[u]\leftarrow \text{false for all }u\in V
Primeira fase — preencher S com ordem de finalização:
Proceda para cada u\in V:
\text{if }\neg\text{visited}[u]\text{ then DFS-visit}(u)
onde
\text{DFS-visit}(u):\\ \text{visited}[u]\leftarrow\text{true};\\ \text{for each }v\in \text{Adj}[u]\\ \text{if }\neg\text{visited}[v]\\ \text{then DFS-visit}(v);\\ S.\text{push}(u)
Construir G^T:
\text{para cada }u\in V\\ \text{e cada }v\in\text{Adj}[u]\\ \text{fazer insert }u\\ \text{em AdjT}[v]
Segunda fase — obter \mathrm{comp}[u]:
\text{visited}[u]\leftarrow\text{false for all }u;\\ id\leftarrow 0
\text{while }S\\ \text{não vazia do }u\leftarrow S.\text{pop}()\\ \text{se }\neg\text{visited}[u]\\ \text{then } id\leftarrow id+1;\\ \text{DFS-assign}(u,id)ã
onde
\text{DFS-assign}(u,id):\\ \text{visited}[u]\leftarrow\text{true};\\ \mathrm{comp}[u]\leftarrow id;\\ \text{for each }v\in\text{AdjT}[u]\\ \text{if }\neg\text{visited}[v]\\ \text{then DFS-assign}(v,id)
Criar lista de vértices por componente (opcional, para facilitar a etapa seguinte):
\text{para }u\in V\\ \text{fazer append }u\\ \text{em VerticesInComp}[\mathrm{comp}[u]]
Construir G_C sem paralelas:
\text{para }i=1\text{ até }k\\ \text{fazer }\mathrm{AdjC}[i]\leftarrow\text{vazia}é
\mathrm{seen}[1..k]\leftarrow\text{false}
\text{para }i=1\text{ até }k\\ \text{fazer}é
\quad \mathrm{newNbrs}\leftarrow\text{vazia}
\quad \text{para cada }u\in \text{VerticesInComp}[i]\\ \text{e cada }v\in\text{Adj}[u]\\ \text{fazer}
\quad\quad j\leftarrow \mathrm{comp}[v]
\quad\quad \text{if }j\ne i \text{ and } \neg\mathrm{seen}[j]\\ \text{then append } j \text{ em } \mathrm{AdjC}[i];\\ \mathrm{seen}[j]\leftarrow\text{true};\\ \text{append } j \text{ em } \mathrm{newNbrs}
\quad \text{para cada }j\in \mathrm{newNbrs}\\ \text{fazer }\mathrm{seen}[j]\leftarrow\text{false}
Resultado: G_C com vértices 1..k e listas \mathrm{AdjC}[1..k]; cada par (i,j) aparece no máximo uma vez.

Passo 9

Análise de complexidade final e correção.
Complexidade:
  • Primeira DFS (order finish): \mathrm{O}(|V|+|E|).
  • Construção de G^T: \mathrm{O}(|V|+|E|).
  • Segunda DFS (atribuir componentes): \mathrm{O}(|V|+|E|).
  • Construção de listas VerticesInComp: \mathrm{O}(|V|).
  • Percorrer todas as arestas e construir \mathrm{AdjC} com a técnica de marcação: examinamos cada aresta original exatamente uma vez (quando percorremos adjacências de seus vértices), e cada inserção de vizinho distinto corresponde a uma aresta no grafo de componentes; a soma das limpezas \mathrm{seen} é proporcional ao número de arestas distintas no grafo de componentes (no máximo |E|). Logo essa etapa é \mathrm{O}(|V|+|E|).
  • Somando tudo: tempo total \mathrm{O}(|V|+|E|).
Corretude:
  • Kosaraju garante que \mathrm{comp}[u] identifica corretamente as SCCs.
  • Para cada aresta (u\to v) com \mathrm{comp}[u]\ne\mathrm{comp}[v] nós inserimos exatamente uma aresta (\mathrm{comp}[u]\to\mathrm{comp}[v]) na lista \mathrm{AdjC}[\mathrm{comp}[u]] — e a técnica de \mathrm{seen} impede duplicatas, assegurando no máximo uma aresta entre dois componentes.
  • Assim G_C é o grafo de condensação correto, e não contém paralelas.

Passo 10

Observações práticas e implementação:
  • Representação: usar listas de adjacência para G e G_C (vetor de vetores ou vetores de listas encadeadas).
  • Em linguagens com hash-sets rápidas (por exemplo, unordered_set em C++), uma alternativa prática é, ao ler cada aresta (u\to v), inserir j=\mathrm{comp}[v] em um \text{set} associado a \mathrm{comp}[u]. Isso também funciona em tempo esperado \mathrm{O}(|V|+|E|) amortizado, mas a técnica de \mathrm{seen} dá tempo determinístico linear sem depender de hashing.
  • Se quiser retornar também o mapeamento de vértices originais para vértices do grafo de componentes, retorne o vetor \mathrm{comp}[\,\cdot\,] junto com G_C.

Resposta

Execute Kosaraju para obter \mathrm{comp}[u] para todo u\in V em \mathrm{O}(|V|+|E|); então, para cada componente i, percorra todos os vértices u com \mathrm{comp}[u]=i e todas as arestas (u\to v); se j=\mathrm{comp}[v]\neq i e j ainda não foi registrado como vizinho de i, adicione j em \mathrm{AdjC}[i] e marque j temporariamente; ao terminar i, limpe as marcações de seus vizinhos. O algoritmo inteiro roda em \mathrm{O}(|V|+|E|) e garante no máximo uma aresta entre dois vértices em G_C.

Exercícios relacionados