Esta página introduz o conceito de digrafo fortemente conexo e discute um algoritmo que determina os componentes fortes de um digrafo. O algoritmo usa busca em profundidade.
A página é inspirada na seção 22.5 do CLRS. Veja também o verbete Strongly connected component na Wikipedia.
Um digrafo é fortemente conexo se, para cada par u,v de seus vértices, existe um passeio de u a v e um passeio de v a u. Em outras palavras, um digrafo é fortemente conexo se e somente se qualquer vértice é acessível a partir de qualquer outro.
Problema da conexão forte: Decidir se um dado digrafo é fortemente conexo.
É fácil resolver o problema: basta verificar que o território de todo vértice é o conjunto de todos os vértices do digrafo. Um tal algoritmo usa repetidamente o algoritmo Território e portanto consome tempo
sendo n o número de vértices e m o número de arcos do digrafo. Essa estimativa é justa: para alguns digrafos o algoritmo consumirá tempo proporcional a n(n+m). Para muitas aplicações, esse tempo é excessivamente longo. De toda maneira, o algoritmo não é eficiente: existem algoritmos bem mais rápidos, como veremos adiante.
Um digrafo H é subdigrafo de um digrafo D se todo vértice de H é vértice de D e todo arco de H é arco de D. O subdigrafo de D induzido por um conjunto X de vértices é o digrafo (X,B) em que B é o conjunto de todos os arcos de D que têm ambas as pontas em X.
Diremos que um conjunto X de vértices de um digrafo é forte se, para todo par u,v de vértices em X, existe um passeio de u a v e um passeio de v a u. Um conjunto forte X é maximal se, para todo vértice y fora de X, o conjunto X ∪ {y} não é forte.
Um componente forte de um digrafo é um conjunto forte maximal. É fácil verificar que o subdigrafo induzido por um componente forte é um digrafo fortemente conexo.
Problema dos componentes fortes: Encontrar os componentes fortes de um digrafo.
É fácil verificar que cada vértice do digrafo pertence a um e um só componente forte. Assim, os componentes fortes determinam uma partição do conjunto de vértices do digrafo.
A determinação dos componentes fortes de um digrafo é importante porque muitos algoritmos (para diferentes problemas) são aplicados, em separado, a cada componente forte do digrafo.
Num digrafo acíclico, cada componente forte tem um só vértice. Reciprocamente, se cada componente forte de um digrafo tem um só vértice então o digrafo é acíclico. Essa observação sugere a introdução do conceito de digrafo dos componentes fortes.
O digrafo dos componentes fortes de um digrafo D, digamos F(D), é definido assim: os vértices de F(D) são os componentes fortes de D e há um arco XY em F(D) se existe um arco em D com ponta inicial em X e ponta final em Y. Vamos supor que X ≠ Y para todo arco XY, de modo que F(D) não tenha laços. É fácil verificar que
o digrafo F(D) é acíclico, ou seja, um dag.
Portanto, todo digrafo é um conjunto de digrafos fortemente conexos mutuamente disjuntos "interligados" por um dag.
Como se sabe, todo dag admite uma enumeração topológica (= ordenação topológica). Ademais, uma tal enumeração topológica pode ser revelada por um busca em profundidade. Essas observações serão exploradas nas próximas seções para construir um algoritmo que calcula os componentes fortes de um digrafo.
Seja (v1,…,vn) uma enumeração dos vértices de um digrafo. Para cada componente forte X, seja
min(X)
o menor índice i tal que vi está em X. (Podemos dizer, informalmente, que min(X) indica o primeiro vértice de X "descoberto" pela enumeração.)
Com essa notação, podemos introduzir uma generalização do conceito de enumeração topológica. Uma enumeração (v1,…,vn) dos vértices de um digrafo é quase topológica se
min(X) < min(Y)
para cada par (X,Y) de componentes fortes distintos tal que existe arco com ponta inicial em X e ponta final em Y. A condição pode ser reformulada assim: min(X) < min(Y) para todo arco XY do dag dos components fortes do digrafo.
Poderíamos dizer, de maneira vaga e informal, que uma enumeração dos vértices é quase topológica se "descobre os componentes fortes do digrafo em ordem topológica".
Exemplo: Num digrafo acíclico, toda enumeração topológica é quase topológica e toda enumeração quase topológica é uma enumeração topológica.
A seguinte observação pode ser útil: o primeiro vértice de qualquer enumeração quase topológica pertence a uma fonte do dag dos componentes fortes. Analogamente, o último vértice de qualquer enumeração quase topológica pertence a um sorvedouro do dag dos componentes fortes.
Como veremos adiante, qualquer busca em profundidade revela, naturalmente, uma enumeração quase topológica.
Para tirar proveito de uma enumeração quase topológica, é preciso introduzir mais um conceito. O trans-território (ou território transposto ou território inverso) de um vértice r num digrafo é o conjunto de todos os vértices a partir dos quais r é acessível. Portanto, um vértice v está no trans-território de um vértice r se e somente se existe um passeio de v a r.
Seja X um componente forte do digrafo e r um vértice em X. É claro que o trans-território de r contém X. (O território de r também contém X.) Ademais, se X é uma fonte do dag dos componentes fortes então o trans-território de r não contém nada mais além de X. (Mas não se pode dizer o mesmo do território de r!) Esta observação é o ponto de partida do algoritmo que estudaremos adiante.
O algoritmo de S. Rao Kosaraju, discutido abaixo, determina os componentes fortes de qualquer digrafo.
Nossa versão do algoritmo de Kosaraju atribui um rótulo inteiro positivo rótulo[v] a cada vértice v de tal modo que rótulo[u] = rótulo[v] se e somente se u e v estão no mesmo componente forte.
A rotulação dos componentes é consistente com uma enumeração topológica do dag dos componentes fortes: se x e y pertencem a componentes fortes X e Y respectivamente e se XY é um arco no dag dos componentes fortes então rótulo[x] < rótulo[y].
O algoritmo de Kosaraju tem duas fases. A primeira fase faz uma busca em profundidade para calcular uma enumeração quase topológica dos vértices digrafo. A segunda fase extrai da enumeração quase topológica os componentes fortes do digrafo.
| Kosaraju (n, Adj) |
| 11 o para u ← 1 até n faça |
| 12 oooo cor[u] ← branco |
| 14 o T ← Cria-Pilha-Vazia ( ) |
| 15 o para r ← 1 até n faça |
| 16 oooo se cor[r] = branco |
| 17 ooooooo então Enumeração-Quase-Topológica (r, T) |
| 18 o para u ← 1 até n faça |
| 19 oooo rótulo[u] ← 0 |
| 10 o AdjTr ← Transposto (Adj) |
| 11 o c ← 0 |
| 12 o enquanto T não estiver vazia faça |
| 13 oooo r ← Tira-Topo-da-Pilha (T) |
| 14 oooo se rótulo[r] = 0 |
| 15 ooooooo então c ← c+1 |
| 16 ooooooo então Rotula-Território (n, AdjTr, r, c) |
| 17 o devolva rótulo[1..n] |
As rotinas Cria-Pilha-Vazia, e Tira-Topo-da-Pilha têm o comportamento que seu nome sugere. A fase 1 do algoritmo, que corresponde ao bloco de linhas 1-7, armazena na pilha T, em ordem inversa, uma enumeração quase topológica dos vértices digrafo. (Compare com o algoritmo Ciclo-ou-Enum-Topológica.)
| Enumeração-Quase-Topológica (u, T) |
| 1 o cor[u] ← cinza |
| 2 o para cada v em Adj[u] faça |
| 3 oooo se cor[v] = branco |
| 4 ooooooo então Enumeração-Quase-Topológica (v, T) |
| 5 o cor[u] ← preto |
| 6 o Coloca-na-Pilha (u, T) |
A fase 2 do algoritmo Kosaraju, que corresponde ao bloco de linhas 8-17, usa a pilha T para atribuir rótulos aos vértices de modo a identificar os componentes fortes.
A rotina Transposto recebe as listas de adjacência de um digrafo e devolve as listas de adjacência do digrafo transposto. O transposto de um digrafo é o digrafo que se obtém quando todos os seus arcos são invertidos, ou seja, cada arco uv é trocado por um arco vu. É claro que, para qualquer vértice r, o trans-território de r no digrafo original é idêntico ao território de r no digrafo transposto.
| Rotula-Território (n, AdjTr, r, c) |
| 1 o rótulo[r] ← c |
| 2 o L ← Cria-Lista(r) |
| 3 o enquanto L não estiver vazia faça |
| 4 oooo u ← Sai-da-Lista(L) |
| 5 oooo para cada v em AdjTr[u] faça |
| 6 ooooooo se rótulo[v] = 0 |
| 7 oooooooooo então rótulo[v] ← c |
| 8 oooooooooo então Entra-na-Lista(v, L) |
A rotina Rotula-Território é uma variante do algoritmo Território (veja também o exercício 4). Ele recebe um digrafo com vértices 1, … , n e arcos definidos pelas listas de adjacência AdjTr[1..n]. Recebe também um vetor rótulo[1..n] que atribui rótulos aos vértices e um vértice r cujo rótulo é 0. A rotina atribui rótulo c a cada vértice no território de r que tenha rótulo 0. (A variável c e o vetor rótulo são tratados como variáveis globais.)
Uma análise semelhante à que fizemos nas páginas Ciclos e digrafos acíclicos e Digrafos acíclicos e enumeração topológica revela que o algoritmo Kosaraju consome tempo
Ο(n+m),
sendo n o número de vértices e m o número de arcos do digrafo.