Algoritmo de Kosaraju: Guia de Componentes Fortemente Conectados

O algoritmo de Kosaraju encontra os componentes fortemente conectados (SCCs) de um grafo direcionado. Um SCC é um grupo de vértices em que todo vértice consegue alcançar todos os outros. O algoritmo executa duas buscas em profundidade: a primeira registra a ordem em que os vértices terminam, e a segunda roda no grafo com todas as arestas invertidas, processando os vértices na ordem inversa de término. Cada árvore da segunda busca é um SCC. Ele roda em tempo O(V + E).

Se você comprimir cada SCC em um único nó, o que sobra é um grafo direcionado sem ciclos. É por isso que os SCCs aparecem em análise de dependências, detecção de deadlock, 2-SAT e em qualquer problema em que os ciclos precisam ser colapsados primeiro.

As duas passagens, passo a passo

1. Rode DFS sobre o grafo inteiro. Quando um vértice termina (todos os seus vizinhos de saída já foram processados), empurre-o para uma lista.
2. Inverta todas as arestas para obter o grafo transposto.
3. Percorra a lista de término do último para o primeiro. Para cada vértice ainda não visitado, rode DFS no grafo transposto. Tudo o que essa busca alcançar é um SCC.

Os dois laços precisam começar de todo vértice não visitado, não apenas do vértice 0, porque o grafo pode não ser conectado.

Um exemplo resolvido

Considere 8 vértices e estas arestas:

0 → 1, 1 → 2, 2 → 0      (cycle A: 0, 1, 2)
2 → 3
3 → 4, 4 → 5, 5 → 3      (cycle B: 3, 4, 5)
6 → 5
6 → 7, 7 → 6             (cycle C: 6, 7)

Os SCCs devem ser 2, 5 e 7.

Primeira passagem

Comece a DFS em 0 e vá 0 → 1 → 2 → 3 → 4 → 5. O vértice 5 não tem para onde ir que ainda não tenha visitado, então ele termina primeiro, depois 4, depois 3. De volta ao 2 não sobrou nada, então 2, 1 e 0 terminam. O vértice 6 ainda não foi visitado, então comece por ele: 5 já terminou, então vá para 7, que termina, e depois 6. A ordem de término é:

5, 4, 3, 2, 1, 0, 7, 6

Segunda passagem

Inverta todas as arestas e processe os vértices a partir do fim dessa lista: 6 primeiro. No grafo invertido, 6 só consegue alcançar 7, então 7 é o primeiro SCC. O próximo não visitado é 0, que alcança 2 e 1 no grafo invertido, formando 2. A aresta 2 → 3 agora aponta 3 → 2, mas 2 já foi atribuído, então a busca para por aí. Por último, 3 alcança 5 e 4, formando 5.

Por que funciona

Pense no grafo dos SCCs (cada componente comprimido em um único nó), que não tem ciclos. Na primeira passagem, o vértice que termina por último sempre pertence a um componente "fonte", ou seja, um componente sem arestas vindas de outros componentes ainda não atribuídos. Inverter as arestas transforma essa fonte em um sumidouro, então uma DFS iniciada ali não consegue sair do próprio componente. Depois que esse componente é removido, o mesmo argumento se aplica ao próximo.

Em uma entrevista, esse costuma ser o nível de prova esperado: a ordem de término escolhe um componente inicial seguro, e inverter as arestas impede que a segunda busca vaze para outros componentes.

Implementação em Python

Esta versão usa DFS iterativa, então não esbarra no limite de recursão do Python em grafos profundos.

from collections import defaultdict

def kosaraju(n, edges):
    graph = defaultdict(list)
    reverse = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        reverse[v].append(u)

    # Pass 1: record vertices in the order they finish (iterative DFS)
    visited = [False] * n
    order = []
    for start in range(n):
        if visited[start]:
            continue
        visited[start] = True
        stack = [(start, iter(graph[start]))]
        while stack:
            node, neighbors = stack[-1]
            for nxt in neighbors:
                if not visited[nxt]:
                    visited[nxt] = True
                    stack.append((nxt, iter(graph[nxt])))
                    break
            else:
                stack.pop()
                order.append(node)

    # Pass 2: DFS on the reversed graph, latest finish time first
    visited = [False] * n
    components = []
    for start in reversed(order):
        if visited[start]:
            continue
        visited[start] = True
        component = []
        stack = [start]
        while stack:
            node = stack.pop()
            component.append(node)
            for nxt in reverse[node]:
                if not visited[nxt]:
                    visited[nxt] = True
                    stack.append(nxt)
        components.append(component)
    return components


edges = [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3), (6, 5), (6, 7), (7, 6)]
print(kosaraju(8, edges))  # [[6, 7], [0, 2, 1], [3, 5, 4]]

A ordem dos vértices dentro de cada componente depende da travessia, então compare os componentes como conjuntos nos seus testes. Validamos esta implementação contra uma verificação de alcançabilidade por força bruta em 2.000 grafos aleatórios.

Complexidade

O espaço é O(V + E) para as duas listas de adjacência, mais O(V) para o array de visitados, a ordem de término e a pilha.

Erros que quebram o algoritmo

O bug mais comum é registrar os vértices quando a DFS chega neles pela primeira vez, em vez de quando eles terminam. Outros são esquecer de inverter a ordem de término para a segunda passagem, rodar a segunda passagem no grafo original em vez do invertido, não limpar o array de visitados entre as passagens e começar apenas do vértice 0, fazendo com que as partes desconectadas sejam ignoradas. A DFS recursiva também pode estourar a pilha em cadeias longas, e é por isso que o código acima é iterativo.

Bons casos de teste: um único vértice, um vértice com auto-laço, um ciclo grande, uma cadeia de mão única (todo vértice é seu próprio SCC), dois ciclos ligados por uma aresta e um grafo desconectado.

Kosaraju vs. Tarjan

Os dois rodam em O(V + E). Kosaraju faz duas passagens e constrói o grafo invertido, o que o torna mais fácil de explicar e de acertar. O algoritmo de Tarjan faz tudo em uma passagem, sem grafo invertido, mas rastreia índices de descoberta e valores de low-link em uma pilha, o que é mais estado para manter na cabeça. Em uma entrevista, use o que você conseguir implementar corretamente e explicar. Se o entrevistador pedir uma única passagem, isso é um sinal para usar Tarjan.

Praticando problemas de grafos

Trace o exemplo acima à mão uma vez antes de escrever código; a maioria dos bugs aparece como uma ordem de término errada. Guias relacionados: Floyd–Warshall para caminhos mais curtos entre todos os pares, Bellman–Ford para grafos com arestas negativas e nosso guia de referência de Big O. Se você usa o YesToTheOffer na prática de programação, a ajuda com código por screenshot pode verificar sua abordagem, e o transcript da sessão mostra se você explicou seu raciocínio com clareza.