Escrito por Theo Sampaio
Contemple o seguinte problema:
“Dado um grafo direcionado, diz-se que dois nós $$\mathcal{u}$$ e $$\mathcal{v}$$ estão no mesmo reino se e somente se é possível chegar de $$\mathcal{u}$$ até $$\mathcal{v}$$ e de $$\mathcal{v}$$ até $$\mathcal{u}$$ usando as arestas do grafo. Conte quantos reinos existem no grafo e para cada nó, atribua um reino a ele.”
Esse é o enunciado (resumido e traduzido) do problema Planets and Kingdoms, do CSES. Atribuamos então um nome formal a cada “reino” do grafo: Componente Fortemente Conexa. Esse conceito expande a questão da conectividade para grafos direcionados.
A solução para o problema acima se dá pelo algoritmo de Kosaraju, que será explicado nessa aula.
Algoritmo de Kosaraju
O algoritmo de Kosaraju se dá por duas DFS, sendo que a primeira DFS processa nós em ordem arbitrária no grafo original, e a segunda é feita em Ordem Topológica reversa no grafo transposto (que é o grafo original com arestas invertidas).
Primeiro, se faz uma DFS para cada nó ainda não marcado, e se marca o tempo de saída de cada nó (tout). Depois, vamos ordenar os nós pelo tout em ordem decrescente (usando sort com comparador ou então pair<int, int>). A implementação desse código fica assim:
Essa implementação usa sort com comparador. A função sort tem complexidade $$\mathcal{O}(n\log n)$$. É possível também fazer a implementação simplesmente colocando os nós durante a DFS em um vector<int>, o que torna a complexidade $$\mathcal{O}(n)$$. Implementação:
Agora temos a lista de nós em ordem decrescente de tempos de saída. O algoritmo de Kosaraju diz que deve-se fazer uma DFS no grafo transposto, processando os nós nesta ordem.
Para cada nó, veja se a ele ainda não foi assinalada uma componente fortemente conexa (CFC). Se sim, atribua a ele uma CFC nova, e para todo nó alcançável não visitado em sua árvore de DFS atribua a mesma CFC. Esse passo pode parecer um tanto quanto estranho ou contra-intuitivo.
Por isso, testaremos o algoritmo no seguinte grafo (retirado do livro Competitive Programmer’s Handbook):
Os números à direita são os tempos de saída dos nós. Os números à esquerda são os tempos de entrada, mas não têm utilidade na execução, e ficam apenas para fim didático.
O primeiro nó processado é o nó 3, pois tem maior tempo de saída, e como as arestas serão invertidas, a CFC não “vaza” para o resto do grafo, o que será melhor explicado na seção de prova do algoritmo:
Isso é repetido até a determinação de todas as CFCs.
As CFCs podem ser representadas dessa forma:
Recapitulando o que fizemos e como isso pode ser implementado:
- Montamos um grafo $$G$$ e seu grafo transposto $$G^T$$ (denominado
hno código abaixo) em forma de lista de adjacência. - Realizamos uma DFS e obtemos uma ordem topológica reversa dos nós
- Por fim, realizamos outra DFS na ordem obtida (agora no grafo reverso) e atribuímos componentes fortemente conexas aos nós conforme são visitados.
Uma possível implementação é:
Prova de corretude do algoritmo:
Algumas nomenclaturas que usaremos:
Seja $$G$$ um grafo. Seja $$G^T$$ a transposição de $$G$$, e $$G^{CFC}$$ o grafo em que cada componente fortemente conexa é transformada em um nó, conectando CFCs se existe uma aresta entre quaisquer nós que estão em CFCs diferentes.
Para ilustração, o grafo do exemplo ficaria assim:
A prova se baseia em dois lemas relativamente simples, mas sua demonstração tornaria essa prova nimiamente extensa, e ficam como exercício para o leitor.
Os dois lemas são:
- Teorema do Caminho Branco (Para todos os nós $$\mathcal{u}$$ e $$\mathcal{v}$$ em um grafo, $$\mathcal{v}$$ é ascendente de $$\mathcal{u}$$ na floresta de busca em profundidade de $$G$$ se e somente se quando $$\mathcal{v}$$ for descoberto, existir um caminho branco (com nenhum nó visitado) entre $$\mathcal{v}$$ e $$\mathcal{u}$$).
- Teorema Fundamental das Componentes Fortemente Conexas (Para todo grafo $$G$$, $$G^{CFC}$$ é um DAG).
A ordem decrescente dos tempos de término em $$G$$ induz uma ordenação topológica reversa de $$G^{CFC}$$.
Por isso, processar os nós nessa ordem no grafo transposto é essencial. A ordem decrescente dos tempos de saída garante que a próxima componente escolhida não possua arestas de entrada em $$G$$. Sendo assim, elas se tornam componentes sorvedouro em $$G^T$$, não possuindo arestas de saída.
Seja então $$\mathcal{C}$$ o primeiro nó descoberto em uma CFC. Como o grafo está transposto e em ordem topológica reversa, pode-se inferir que todo nó $$\mathcal{v}$$ que é vizinho de $$\mathcal{C}$$ em $$G$$ e ainda não foi marcado é da mesma CFC que $$\mathcal{C}$$. Isso ocorre porque existem somente duas condições pra $$\mathcal{v}$$:
- $$\mathcal{v}$$ está depois de $$\mathcal{C}$$ na ordenação topológica reversa, e como o grafo é transposto, a aresta $$\mathcal{C} \to \mathcal{v}$$ está invertida, logo $$\mathcal{C}$$ não alcança $$\mathcal{v}$$ em sua DFS.
- Existe uma aresta $$\mathcal{v} \to \mathcal{C}$$, e outra $$\mathcal{C} \to \mathcal{v}$$ o que implica que $$\mathcal{C}$$ e $$\mathcal{v}$$ estão na mesma CFC.
Apesar de ser um tópico consideravelmente grande por si só, não existem muitas questões “puras” de CFC, mas é um tópico de extrema relevância para o famoso problema 2-SAT, e para uma outra matéria chamada Pontes.
Problemas recomendados: