Componentes fortemente conexos com Kosaraju
Execute DFS no grafo original para obter a ordem de término, transponha o grafo e execute DFS novamente na ordem de término inversa para identificar os componentes fortemente conexos.
Componentes fortemente conexos com Kosaraju é uma aula grátis de DSA Interview Prep no CoddyKit. Esta é a aula 4 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de DSA Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de DSA Interview Prep inclui 4 aulas no total.
Definição de componentes fortemente conexos
Um componente fortemente conexo (SCC) de um grafo direcionado é um conjunto maximal de nós tal que existe um caminho de cada nó para todos os outros nós dentro do conjunto. Por exemplo, se os nós A, B e C formarem um ciclo (A→B→C→A), todos estarão no mesmo SCC. Um único nó sem um laço para si mesmo é seu próprio SCC. Os componentes fortemente conexos revelam a estrutura cíclica de um grafo direcionado.
Algoritmo de Kosaraju: duas passagens de DFS
O algoritmo de Kosaraju encontra todos os componentes fortemente conexos em O(V + E) usando duas passagens de DFS. Passagem 1: execute o DFS no grafo original e coloque os nós em uma pilha na ordem de término (pós-ordem). Passagem 2: execute o DFS no grafo transposto (invertido), processando os nós na ordem inversa de término (retirando-os da pilha). Cada árvore de DFS na passagem 2 corresponde a um componente fortemente conexo.
Por que o algoritmo de Kosaraju funciona
Na passagem 1, o componente fortemente conexo cuja árvore de DFS termina por último é aquele que não tem arestas de saída para outros componentes fortemente conexos (um componente “sumidouro” no DAG de condensação). No grafo transposto, esse componente não tem arestas de entrada de outros componentes fortemente conexos — portanto, o DFS iniciado nele permanece confinado dentro desse componente. Cada DFS subsequente na passagem 2 permanece dentro do seu próprio componente fortemente conexo, porque todas as arestas entre componentes foram invertidas e levam de volta a componentes já visitados.
Passagem 1: construir a ordem de término
Execute o DFS no grafo original e coloque cada nó em uma pilha depois que ele terminar (pós-ordem). Nesta passagem, não nos importamos com os componentes — apenas com a ordem de término. O último nó a terminar estará em um componente “fonte” do DAG de condensação.
from collections import defaultdict
def kosaraju(n, edges):
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
rev_graph[v].append(u) # reversed edges
visited = set()
finish_stack = []
def dfs1(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited:
dfs1(nxt)
finish_stack.append(node) # push after all neighbours done
for i in range(n):
if i not in visited:
dfs1(i)
return finish_stack, rev_graphPassagem 2: DFS no grafo transposto
Retire os nós da pilha de término (primeiro o maior tempo de término) e execute o DFS no grafo transposto. Cada DFS iniciado em um nó não visitado descobre exatamente um componente fortemente conexo. Marque todos os nós alcançados nesse DFS como pertencentes ao mesmo componente.
from collections import defaultdict
def kosaraju_full(n, edges):
graph = defaultdict(list)
rev_graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
rev_graph[v].append(u)
visited = set()
finish_stack = []
def dfs1(node):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited: dfs1(nxt)
finish_stack.append(node)
for i in range(n):
if i not in visited: dfs1(i)
visited.clear()
sccs = []
def dfs2(node, component):
visited.add(node)
component.append(node)
for nxt in rev_graph[node]:
if nxt not in visited: dfs2(nxt, component)
while finish_stack:
node = finish_stack.pop()
if node not in visited:
component = []
dfs2(node, component)
sccs.append(component)
return sccs
# Graph with SCCs: {0,1,2} and {3}
edges = [(0,1),(1,2),(2,0),(1,3)]
print(kosaraju_full(4, edges)) # [[3], [0,2,1]] or similarTransposição do grafo
O grafo transposto inverte todas as arestas: se o original tiver u → v, o transposto terá v → u. A transposição preserva os componentes fortemente conexos — se A e B estiverem no mesmo componente fortemente conexo no grafo original, continuarão no mesmo componente no transposto (já que todos os caminhos são invertidos, mas continuam conectando os nós). Construir o grafo transposto durante a leitura das entradas (como mostrado acima) evita uma etapa de transposição separada.
Versão iterativa para grafos grandes
Para grafos grandes, substitua o DFS recursivo pelo DFS iterativo usando uma pilha explícita para evitar o limite de recursão do Python. A versão iterativa empilha os nós, processa-os e mantém um marcador separado de 'retorno' para simular a pós-ordem.
def dfs1_iterative(start, graph, visited, finish_stack):
stack = [(start, iter(graph[start]))]
visited.add(start)
while stack:
node, neighbours = stack[-1]
try:
nxt = next(neighbours)
if nxt not in visited:
visited.add(nxt)
stack.append((nxt, iter(graph[nxt])))
except StopIteration:
stack.pop()
finish_stack.append(node)
print('Iterative DFS for large graphs avoids recursion limit')Algoritmo de Tarjan: SCC alternativa
O algoritmo de Tarjan encontra SCCs em uma única passagem de DFS (em comparação com as duas passagens de Kosaraju). Ele mantém uma pilha de nós e atribui a cada nó um tempo de descoberta e um valor de ligação inferior. Quando o tempo de descoberta de um nó é igual ao seu valor de ligação inferior, ele é a raiz de uma SCC. O algoritmo de Tarjan é um pouco mais complexo de implementar, mas evita a construção do grafo transposto. Ambos têm complexidade O(V + E).
Aplicações das SCCs
As SCCs são usadas em: (1) Otimização de compiladores — identificação de funções mutuamente recursivas. (2) Análise de redes sociais — localização de comunidades fortemente conectadas. (3) Problema 2-SAT — determinação da satisfatibilidade de cláusulas com dois literais. (4) Rastreamento da web — identificação de agrupamentos de páginas com links cruzados densos. (5) DAG de condensação — depois de encontrar as SCCs, a condensação do grafo é um DAG, permitindo a análise topológica de grafos cíclicos.
DAG de condensação
A condensação de um grafo direcionado contrai cada SCC em um único nó e adiciona uma aresta entre dois supernós se houver uma aresta entre as SCCs que os compõem. O resultado é sempre um DAG — é possível executar uma ordenação topológica nele. Isso permite aplicar algoritmos que funcionam apenas em DAGs, como DP, a grafos direcionados gerais, trabalhando sobre sua condensação.
def build_condensation(n, edges, sccs):
# Assign each node to its SCC index
scc_id = [0] * n
for idx, component in enumerate(sccs):
for node in component:
scc_id[node] = idx
# Build condensation edges
condensation_edges = set()
for u, v in edges:
su, sv = scc_id[u], scc_id[v]
if su != sv:
condensation_edges.add((su, sv))
return list(condensation_edges)
edges = [(0,1),(1,2),(2,0),(1,3)]
sccs = [[3],[0,1,2]]
print(build_condensation(4, edges, sccs)) # [(0,1)] or [(1,0)]Número de SCCs e propriedades dos grafos
O número de SCCs em um grafo direcionado revela sua estrutura cíclica. Um DAG tem n SCCs (cada nó é sua própria SCC). Um grafo fortemente conexo tem exatamente 1 SCC. Em geral, as SCCs formam um DAG quando condensadas — a condensação. Se o DAG de condensação tiver uma fonte única (nó com grau de entrada 0) e um sorvedouro único (nó com grau de saída 0) na condensação, determinadas propriedades de conectividade serão válidas. Essas propriedades são testadas em problemas de alcançabilidade após a adição do número mínimo de arestas.
Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu que: as SCCs são conjuntos máximos nos quais cada nó é alcançável a partir de todos os outros, Kosaraju usa duas passagens de DFS — primeiro no grafo original para obter a ordem de finalização e depois no grafo transposto e a condensação de qualquer grafo direcionado é um DAG que pode ser usado para análises posteriores. A seguir, construiremos estruturas de dados TrieNode para insert, search e operações com prefixos.
Perguntas Frequentes
A aula “Componentes fortemente conexos com Kosaraju” é grátis?
Sim — o texto completo de “Componentes fortemente conexos com Kosaraju” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de DSA Interview Prep, atualize para CoddyKit PRO. O curso de DSA Interview Prep inclui 4 aulas no total.
O que vou aprender em “Componentes fortemente conexos com Kosaraju”?
Execute DFS no grafo original para obter a ordem de término, transponha o grafo e execute DFS novamente na ordem de término inversa para identificar os componentes fortemente conexos. Você pratica DSA Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar DSA Interview Prep?
Nenhuma experiência prévia é necessária. DSA Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 4 de 4.
Quanto tempo leva a aula “Componentes fortemente conexos com Kosaraju”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de DSA Interview Prep?
Sim. Cada aula de DSA Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Algoritmo de Kahn: ordenação topológica por BFS
- Ordenação topológica por pós-ordem de DFS
- Cronograma de cursos I e II
- Componentes fortemente conexos com Kosaraju