Algoritmos para Grafos | Índice
O conceito de conexão forte em grafos é análogo ao conceito de conexão em grafos não-dirigidos. Também é análogo, num certo sentido, ao conceito de aresta-biconexão em grafos não-dirigidos.
Este capítulo trata do problema de decidir se um dado grafo é fortemente conexo. Esse problema é mais complexo que o problema da conexão em grafos não-dirigidos, mas semelhante ao problema da aresta-biconexão.
Sumário:
Um vértice de um grafo é fortemente ligado a outro se um está ao alcance do outro e vice-versa. Em outras palavras, um vértice s é fortemente ligado a um vértice t se existe um caminho de s a t e também um caminho de t a s. (Os dois caminhos são independentes e portanto podem ter vértices e até arcos em comum.)
Um grafo é fortemente conexo (= strongly connected) se cada um de seus vértices está fortemente ligado a cada um dos demais.
Exemplo A. O grafo que aparece na abertura deste capítulo é fortemente conexo. Já o grafo da figura à direita não é fortemente conexo (por quê?).
ladosé vazio.) Mostre que o grafo do exemplo A não é fortemente conexo.
É útil saber distinguir rapidamente um grafo fortemente conexo de um que não tem a propriedade. Esta é a tarefa algorítmica central do capítulo.
Problema da conexão forte: Decidir se um dado grafo é fortemente conexo.
Observe que um grafo G é fortemente conexo se e somente se cada um de seus vértices é raiz de uma subárvore radicada geradora de G. Portanto, para decidir se um grafo G é fortemente conexo, basta fazer buscas DFS (ou BFS), uma partir de cada vértice de G, e verificar se cada uma dessas buscas atinge todos os vértices. Mas esse algoritmo ingênuo é ineficiente, pois cada busca repete boa parte do trabalho feito pelas buscas anteriores.
Um algoritmo bem mais eficiente depende da reversão do grafo. O reverso de um grafo é o resultado da reversão de todos os seus arcos, ou seja, da troca de cada arco v-w por um arco w-v. Dado um grafo G e um vértice r do grafo, observe que G é fortemente conexo se e somente se (1) G tem uma subárvore radicada geradora com raiz r e (2) o reverso de G tem uma subárvore radicada geradora com a mesma raiz r. Essa observação é a base de um algoritmo que resolve o problema da conexão forte em tempo proporcional ao tamanho do grafo. Diremos que esse é o algoritmo das duas árvores radicadas.
O algoritmo das duas árvores radicadas é bastante eficiente, mas exige a construção do grafo reverso. Podemos dispensar esse grafo auxiliar se usarmos a técnica que Tarjan empregou para procurar pontes em grafos não-dirigidos. O algoritmo resultante é o assunto principal deste capítulo. Antes de apresentar o algoritmo, entretanto, precisamos estudar
0: 1 6 1: 2 5 2: 1 3 3: 4 4: 3 5: 2 6: 7 8 7: 3 6 9 8: 7 9:
0: 1 1: 2 2: 3 5 3: 4 4: 3 5: 1 3
Se uma floresta DFS de um grafo tem mais de uma raiz — ou seja, se a busca DFS tem mais de uma etapa — então o grafo não é fortemente conexo. Mas a recíproca não é verdadeira: mesmo que uma floresta DFS tenha uma só raiz, o grafo pode não ser fortemente conexo. Para decidir, com base nessa floresta, se o grafo é fortemente conexo, usaremos o conceito a seguir.
Dada uma floresta DFS de um grafo, diremos que um arco x-y do grafo abraça um vértice v da floresta se
Note que x pode ser igual a v. Note também que pre[x] > pre[v] e que y é ancestral próprio ou primo esquerdo de v na floresta, donde pre[y] < pre[v]. (Diferentemente do que acontece no estudo de grafos aresta-biconexos, o arco x-y pode ser cruzado em relação à floresta DFS.) O seguinte lema mostra como o conceito de abraço permite caracterizar grafos fortemente conexos.
Lema do abraço: Para qualquer floresta DFS de um grafo fortemente conexo, todo vértice que não seja a única raiz da floresta é abraçado por algum arco. Reciprocamente, se uma floresta DFS de um grafo tem uma única raiz e todo vértice diferente da raiz é abraçado por algum arco, o grafo é fortemente conexo.
Eis um esboço da prova da primeira parte. Suponha que F uma floresta DFS de um grafo fortemente conexo. É claro que F tem uma só raiz, digamos r. Para qualquer vértice v diferente de r, existe um caminho de v até r. Esse caminho tem um arco x-y tal que x é descendente de v mas y não é descendente de v.
Veja agora um esboço da prova da segunda parte do lema. Suponha que uma floresta DFS F de um grafo tem uma só raiz, digamos r, e que todo vértice diferente de r é abraçado por algum arco do grafo. Para qualquer vértice v, é claro que existe um caminho de r a v. Resta mostrar que existe um caminho de v a r. Se pre[v] ≡ 0 então v ≡ r e portanto existe um caminho trivial de v a r. Suponha agora que pre[v] > 0. Então algum arco x-y abraça v e portanto existe um caminho de v a y. Como pre[y] < pre[v] podemos supor, a título de hipótese de indução, que existe um caminho de y a r. Esses dois caminhos garantem a existência de um caminho de v a r.
O lema do abraço fornece um critério para decidir se um grafo é fortemente conexo com base no exame de uma única floresta DFS do grafo. À primeira vista, o critério é computacionalmente pesado: para cada vértice v, todos os arcos do grafo deveriam ser testados. Mas é possível organizar os cálculos de modo a testar cada arco uma única vez no decurso da busca em profundidade. Para fazer isso, precisamos do conceito de número de pré-ordem mínimo, a ser introduzido na próxima seção.
a
|
b
|
c
/ \
d g
/ \
e h
/
f
Exemplo B. Considere o grafo com vértices a..h definido pelas listas de adjacência abaixo. Veja ao lado uma floresta DFS do grafo (você deve imaginar que todos os arcos estão dirigidos de cima para baixo).
a: b b: c c: d g d: e e: f f: b g: a h h: e
Os únicos arcos do grafo que não estão na floresta são f-b, g-a, h-e. O arco f-b abraça os vértices f, e, d, c. O arco g-a abraça g, c, b. O arco h-e abraça h e g. De acordo com o lema do abraço, o grafo é fortemente conexo. Observe, por exemplo, o caminho h-e-f-b-c-g-a que vai de h até a.
Para aplicar o lema do abraço eficientemente, precisamos do seguinte conceito auxiliar. O número de pré-ordem mínimo (= lowest preorder number) ao alcance de um vértice v é o número lo[v] assim definido:
lo[v] = minx-y pre[y]
sendo o mínimo tomado sobre todos os arcos x-y
que abraçam v.
(Muitos livros escrevem low[]
no lugar do meu lo[]
.)
Note que lo[v] < pre[v]
sempre que algum arco abraça v
(veja observação acima).
Se nenhum arco abraça v
então, de acordo com a definição, lo[v] é infinito;
mas é mais conveniente adotar a definição especial lo[v] = pre[v]
nesse caso.
Desse modo, lo[v] ≤ pre[v]
para todo vértice v sem exceção
e v é abraçado por um arco do grafo
se e somente se
lo[v] < pre[v].
0a0
|
1b0
|
2c0
/ \
3d1 6g0
/ \
4e1 7h4
/
5f1
Exemplo C. Considere novamente o grafo do exemplo B. Esse grafo é definido pelas seguintes listas de adjacência:
a: b b: c c: d g d: e e: f f: b g: a h h: e
A figura à direita mostra uma floresta DFS do grafo. Os únicos arcos do grafo que não estão na floresta são f-b, g-a, h-e. Na figura, cada vértice v é precedido pelo número pre[v] e seguido do número lo[v]. Note que o vértice c é abraçado pelos arcos f-b e g-a. Como pre[a] < pre[b], temos lo[c] = pre[a]. Algo análogo acontece com o vértice g.
Cálculo eficiente de lo[ ]. Para calcular lo[] eficientemente durante a busca DFS, observe a seguinte fórmula recursiva, que exprime o valor de lo[] em v em função dos valores que lo[] nos filhos de v. Para cada vértice v, lo[v] é o menor número dentre os seguintes:
O primeiro e o segundo itens da fórmula podem ser vazios. Se ambos forem vazios então lo[v] = pre[v]. O segundo e o terceiro itens da fórmula constituem a base da recursão. A fórmula vale essencialmente porque qualquer arco x-y que abraça um filho w de v também abraça v, a menos que y seja igual a v. A prova cuidadosa da fórmula é um bom exercício.
A fórmula calcula lo[] em pós-ordem: se a permutação dos vértices em pós-ordem é i, j, k, … então a fórmula calcula lo[i], depois lo[j], depois lo[k], e assim por diante. Podemos também usar o inverso da permutação em pré-ordem, uma vez que a fórmula só depende da relação entre pais e filhos na floresta DFS.
A seguinte função usa a fórmula recursiva para calcular lo[]:
static int pre[1000], post[1000]; static vertex pa[1000]; static int lo[1000]; #define min( A, B) (A) < (B) ? (A) : (B)
/* Esta função faz uma busca DFS no grafo G e calcula o lowest preorder number lo[] de cada vértice de G. Também calcula os vetores pre[], post[] e pa[] correspondentes à busca DFS. */
void GRAPHlo( Graph G) { GRAPHdfs( G); // calcula pre[], post[] e pa[] vertex vv[1000]; for (vertex v = 0; v < G->V; ++v) vv[post[v]] = v; // vv[0..V-1] é permutação em pós-ordem for (int i = 0; i < G->V; ++i) { vertex v = vv[i]; lo[v] = pre[v]; for (link a = G->adj[v]; a != NULL; a = a->next) { vertex w = a->w; if (pre[w] < pre[v]) /*A*/ lo[v] = min( lo[v], pre[w]); else /*B*/ if (pa[w] == v) lo[v] = min( lo[v], lo[w]); } } }
No ponto A,
o vértice w é ancestral próprio ou primo esquerdo de v
e portanto v-w abraça v.
No ponto B,
o vértice w é descendente próprio de v
e portanto o valor de lo[w] já está definido,
podendo ser usado
nos cálculos.
A cláusula if (pa[w] == v)
decide se w é filho de v;
em caso afirmativo,
a função aplica o primeiro item da fórmula recursiva.
É um ótimo exercício escrever uma versão recursiva da função GRAPHlo() e fazer o rastreamento da aplicação da função a um exemplo simples.
if (pa[w] == v)depois do ponto B do código de GRAPHlo() é redundante.
de cima para baixona floresta DFS e lo[] é calculado
de baixo para cima.)
a: b b: c a f c: d b d: e c e: f d f: b e
Finalmente, podemos apresentar o algoritmo de Tarjan
(não confunda com Tarzan
![[smile]](../gif/smiley2.jpg){kind=small}
)
para o problema da conexão forte.
Depois de usar a função GRAPHlo()
para calcular os vetores pre[] e lo[],
o algoritmo aplica o teste lo[v] ≡ pre[v]
a todo vértice v
para verificar se o grafo é fortemente conexo.
static int pre[1000], post[1000]; static vertex pa[1000]; static int lo[1000];
/* Esta função decide se o grafo G é fortemente conexo. (A função implementa o algoritmo de Tarjan.) */
bool GRAPHstrongT1( Graph G) { GRAPHlo( G); // calcula pre[], pa[] e lo[] for (vertex v = 0; v < G->V; ++v) { if (lo[v] == pre[v] && pa[v] != v) return false; } int roots = 0; for (vertex v = 0; v < G->V; ++v) { if (pa[v] == v) ++roots; if (roots > 1) return false; } return true; }
O segundo processo iterativo conta o número de raízes da floresta. Se houver mais de uma raiz, a floresta não é geradora e portanto o grafo não pode ser fortemente conexo.
O sufixo T1
do nome da função é uma abreviatura de
Tarjan, versão 1
.
Na próxima seção trataremos da versão 2.
0a0 3d1 | | 1b0 4e1 | 2c0
Exemplo D. Considere o grafo definido pelas listas de adjacência abaixo. A função GRAPHstrongT1(), construirá a floresta DFS indicada à direita. Nessa figura, cada vértice v é precedido pelo número pre[v] e seguido pelo número lo[v].
a: b b: c c: a d: e e: c b
Os únicos arcos do grafo que não estão na floresta são c-a, e-c, e-b. Os dois últimos arcos abraçam o vértice d. Temos low[v] < pre[v] para todo v exceto a. Mas a floresta DFS tem duas raízes, e portanto o grafo não é fortemente conexo.
A função GRAPHstrongT1() examina o grafo todo três vezes: primeiro ao executar GRAPHlo(), depois para comparar lo[v] com pre[v], e finalmente para contar o número de raízes. Embora o consumo total de tempo seja linear, é preferível obter o mesmo efeito examinando o grafo uma única vez. Para fazer isso, é preciso detectar a condição lo[v] ≡ pre[v] durante a busca em profundidade e interromper a busca assim que a condição for encontrada. Diremos que essa é uma implementação on-the-fly do algoritmo de Tarjan.
static int pre[1000], lo[1000]; static vertex pa[1000]; static int cnt; #define min( A, B) (A) < (B) ? (A) : (B)
/* Esta função decide se o grafo G é fortemente conexo. (A função é uma implementação on-the-fly do algoritmo de Tarjan.) */
bool GRAPHstrongT2( Graph G) { for (vertex v = 0; v < G->V; ++v) pre[v] = -1; cnt = 0; if (!dfsRstrong( G, 0)) return false; for (vertex v = 0; v < G->V; ++v) if (pre[v] == -1) return false; return true; }
/* Faz uma busca em profundidade a partir do vértice v e decide se a parte do grafo atingida pela busca é fortemente conexa. Também calcula lo[v]. */
static bool dfsRstrong( Graph G, vertex v) { pre[v] = cnt++; lo[v] = pre[v]; for (link a = G->adj[v]; a != NULL; a = a->next) { vertex w = a->w; if (pre[w] == -1) { if (!dfsRstrong( G, w)) // calcula lo[w] return false; // A lo[v] = min( lo[v], lo[w]); // B } else if (pre[w] < pre[v]) lo[v] = min( lo[v], pre[w]); // C } if (lo[v] == pre[v] && pa[v] != v) return false; // D return true; // E }
Desempenho. Como acontece com muitos algoritmos baseados em busca em profundidade, a função GRAPHstrongT2() consome apenas V + A unidades de tempo quando aplicada a um grafo com V vértices e A arcos. Podemos dizer, portanto, que a função é linear. A variante de GRAPHstrongT2() para matrizes de adjacência consome tempo proporcional a V2; esse desempenho é linear no caso de grafos densos.
0a0
|
1b0
|
2c0
/ \
3d1 6g0
/ \
4e1 7h4
/
5f1
Exemplo E. Considere novamente o grafo do exemplo C, definido pelas listas de adjacência abaixo. Submeta o grafo à função GRAPHstrongT2(), que construirá a floresta DFS indicada à direita, com cada vértice v precedido pelo número pre[v] e seguido do número lo[v].
a: b b: c c: d g d: e e: f f: b g: a h h: e
Veja a seguir o rastreamento da execução da função. (Antes de examinar esse rastreamento, é instrutivo fazer o rastreamento da versão recursiva de GRAPHlo().)
a dfsRstrong(G,a)
a-b dfsRstrong(G,b)
b-c dfsRstrong(G,c)
c-d dfsRstrong(G,d)
d-e dfsRstrong(G,e)
e-f dfsRstrong(G,f)
f-b (lo[f]=1) (linha C)
f (return true, lo[e]=1) (linhas E e B)
e (return true, lo[d]=1) (linhas E e B)
d (return true, lo[c]=1) (linha E e B)
c-g dfsRstrong(G,g)
g-a (lo[g]=0) (linha C)
g-h dfsRstrong(G,h)
h-e (lo[h]=4) (linha C)
h (return true, lo[g]=0) (linhas E e B)
g (return true, lo[c]=0) (linhas E e B)
c (return true, lo[b]=0) (linhas E e B)
b (return true, lo[a]=0) (linhas E e B)
a (return true) (linha E)
A encarnação dfsRstrong(G,f) de dfsRstrong() processa o arco f-b e faz lo[f] = pre[b] na linha C da função. Como não tem mais arcos para processar, a encarnação devolve true na linha E e morre.
A encarnação dfsRstrong(G,e) processa o arco e-f e faz lo[e] = lo[f] na linha B. Como não tem mais arcos para processar, a encarnação devolve true na linha E e morre.
A encarnação dfsRstrong(G,c) processa o arco c-d e faz lo[c] = lo[d] na linha B. Em seguida, processa o arco c-g e faz lo[c] = lo[g] na linha B. Como não tem mais arcos para processar, a encarnação devolve true na linha E e morre.
A encarnação dfsRstrong(G,a) devolve true na linha E e assim decide que G é fortemente conexo. Veja o estado final dos vetores pre[] e lo[]:
v a b c d e f g h
pre[v] 0 1 2 3 4 5 6 7
lo[v] 0 0 0 1 1 1 0 4
0a0
/ \
1b0 2c2
\
3d2
Exemplo F. Considere o grafo definido pelas listas de adjacência abaixo. Submeta o grafo à função GRAPHstrongT2(), que construirá a floresta DFS indicada à direita, com cada vértice v precedido pelo número pre[v] e seguido do número lo[v].
a: b c b: a c: d d: c
Veja a seguir o rastreamento da execução da função:
a dfsRstrong(G,a) a-b dfsRstrong(G,b) b-a (lo[b]=0) (linha C) b (return true, lo[a]=0) (linhas E e B) a-c dfsRstrong(G,c) c-d dfsRstrong(G,d) d-c (lo[d]=2) (linha C) d (return true, lo[c]=2) (linhas E e B) c (return false) (linha D) a (return false) (linha A)
A função devolve false na linha A e assim decide que G não é fortemente conexo. Veja o estado final dos vetores pre[] e lo[]:
v a b c d
pre[v] 0 1 2 3
lo[v] 0 0 2 2
grafo-ciclo0-1-2-3-4-5-6-7-8-9-0. Explique o que acontece em cada linha do código da função.