Exercício
do CLRS3 ou CLRS2. Dê um algoritmo de tempo
para calcular o grafo de componentes de um grafo dirigido
. 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
, a gente produza o grafo de componentes fortemente conectadas (chamado também de condensação) em tempo
. 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
, representado por listas de adjacência (uma lista de arestas saindo de cada vértice). - Saída esperada: um grafo dirigido
onde: - Cada vértice em
representa uma componente fortemente conectada (SCC) de . - Há uma aresta
em se e somente se existe pelo menos uma aresta com em e em , e devemos garantir que haja no máximo uma aresta entre quaisquer e .
- Cada vértice em
- Restrições de tempo: tempo total
.
Passo 2
Ideia geral do algoritmo (resumida; vamos detalhar cada parte depois):
- Encontrar as componentes fortemente conectadas de
e atribuir a cada vértice um identificador de componente . - Construir o grafo contraído (grafo de componentes)
cuja lista de adjacência contém, para cada componente , os componentes distintos tais que existe alguma aresta de um vértice de para um vértice de em . Ao construir essas listas, garantir que cada par 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
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
: 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
inicialmente falso. - Ao finalizar a exploração de um vértice
(todas as arestas saindo de foram processadas), registramos numa pilha ou lista de ordem de finalização (push em uma pilha). Essa ordem será usada na segunda fase.
Algoritmo (primeira fase):
- Para cada vértice
, se for falso, chama-se DFS-visit(u): - marca
true, - para cada
na lista de adjacência de , se é falso, chama DFS-visit(v), - ao terminar, push
numa pilha .
- marca
- Custo: cada aresta é examinada no máximo uma vez, cada vértice processado uma vez, logo tempo
.
Passo 4
Construir o grafo transposto
(trocar direção de todas as arestas) e explicar o porquê e o custo.
Construção de
:
-
tem mesmas vértices . Para cada aresta , inserimos em . - Se
está em listas de adjacência, percorremos todas as listas; para cada aresta fazemos uma inserção em . Isso custa (visitar cada lista + inserir cada aresta uma vez).
Por que usar
:
- 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
fazendo DFSs em
na ordem de decrescimento de finalização.
Procedimento detalhado:
- Inicialize
undefined para todo e false para o segundo passe. - Enquanto a pilha
não estiver vazia: pop de . Se for falso, iniciar uma DFS-visit-assign(u, id) em que: - marca
true, id, - para cada
em adjacência de em , se é falso, chama recursivamente DFS-visit-assign(v, id).
- marca
- Ao terminar a DFS de um componente, incrementa id (próximo identificador de componente).
- Ao final teremos
onde é o número de SCCs. - Custo: novamente
, 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
= número de componentes. - Um vetor
tal que cada vértice tem . - Objetivo agora: construir
onde (cada número representa uma componente) e contém arestas sem paralelas (ou seja, no máximo uma aresta entre quaisquer e ).
Passo 7
Construção do grafo de componentes sem criar arestas paralelas — técnica eficiente que garante
.
Problema a resolver aqui: ao percorrer cada aresta original
, se
devemos adicionar aresta
. 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
uma lista de adjacência vazia (o grafo ). - Teremos um vetor auxiliar
inicializado com falso (ou zeros). - Percorremos todas as arestas originais
: - Seja
e . - Se
então ignore — arestas internas à mesma componente não geram arestas no . - Caso contrário, testamos
relativo ao componente-fonte . 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 .
- Seja
- Implementação eficiente para cada componente
: - Percorra todos os vértices
cujo e em cada um percorra suas arestas . (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 para construir.) - Para o componente corrente
, mantenha uma lista temporária vazia. - Para cada aresta
encontrada, calcule . - Se
e for falso, então: - adiciona
em , - adiciona
em , - seta
true.
- adiciona
- Caso
já seja true, ignora (já adicionamos anteriormente).
- Se
- Depois de processar todos os vértices
com , percorra e para cada faça false (limpeza). Assim, limpamos apenas os marcadores que foram realmente usados, em tempo proporcional ao número de vizinhos distintos encontrados.
- Percorra todos os vértices
- Por que isso é
? - Cada aresta original
é examinada uma vez quando percorremos as arestas dos vértices; logo custo para os exames. - A cada vez que encontramos um novo vizinho distinto
para um componente fazemos uma inserção em e um push em ; cada vizinho distinto corresponde a uma aresta distinta no grafo contraído. O total de vizinhos distintos sobre todos os componentes é . - A limpeza de
faz um trabalho proporcional ao número de vizinhos distintos por componente; somando sobre todos os componentes dá . - Construir as listas de vértices por componente custa
se armazenarmos cada vértice em uma lista pelo seu . - Portanto tempo total desta etapa é
.
- Cada aresta original
Passo 8
Pseudocódigo compacto e detalhado (cada linha usa notação simples; todas as variáveis matemáticas em TeX):
Inicializações:
Primeira fase — preencher
com ordem de finalização:
Proceda para cada :
Proceda para cada
onde
Construir
:
Segunda fase — obter
:
onde
Criar lista de vértices por componente (opcional, para facilitar a etapa seguinte):
Construir
sem paralelas:
Resultado:
com vértices
e listas
; cada par
aparece no máximo uma vez.
Passo 9
Análise de complexidade final e correção.
Complexidade:
- Primeira DFS (order finish):
. - Construção de
: . - Segunda DFS (atribuir componentes):
. - Construção de listas VerticesInComp:
. - Percorrer todas as arestas e construir
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 é proporcional ao número de arestas distintas no grafo de componentes (no máximo ). Logo essa etapa é . - Somando tudo: tempo total
.
Corretude:
- Kosaraju garante que
identifica corretamente as SCCs. - Para cada aresta
com nós inserimos exatamente uma aresta na lista — e a técnica de impede duplicatas, assegurando no máximo uma aresta entre dois componentes. - Assim
é 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
e (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
, inserir em um associado a . Isso também funciona em tempo esperado amortizado, mas a técnica de 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
junto com .
Resposta
Execute Kosaraju para obter
para todo
em
; então, para cada componente
, percorra todos os vértices
com
e todas as arestas
; se
e
ainda não foi registrado como vizinho de
, adicione
em
e marque
temporariamente; ao terminar
, limpe as marcações de seus vizinhos. O algoritmo inteiro roda em
e garante no máximo uma aresta entre dois vértices em
.