Esta página discute o tipo abstrato de dados (= abstract data type = ADT) conhecido como union-find. O conceito é introduzido no contexto de um algoritmo para calcular o número de componentes de um grafo. O union-find é usado por implementações eficientes de vários algoritmos interessantes, como o de Kruskal (para o problema da MST) e o de Karger (para cortes mínimos).
Esta página é inspirada em partes do capítulo 21 do livro de CLRS.
Como calcular o número de componentes de um grafo? Como determinar, eficientemente, se dois dados vértices do grafo estão na mesma componente?
Para começar, convém que
cada componente do grafo tenha um nome
que permita distinguir uma componente da outra.
Para isso, usaremos a seguinte ideia.
Imagine que cada componente é uma empresa
e os vértices da componente são os funcionários
da empresa.
Um dos funcionários é o diretor da empresa.
Assim, o diretor servirá para identificar a empresa.
Usaremos o tipo abstrato de dados union-find para contar as componentes do grafo. Esse tipo de dados dispõe de duas operações:
Dado um grafo G com n vértices, as operações do union-find podem ser usadas como segue para calcular o número de componentes:
| Componentes (G, n) |
| 1 . c := n |
| 2 . Initialize ( ) |
| 3 . para cada aresta uv de G |
| 4 .ooo r := Find (u) |
| 5 .ooo s := Find (v) |
| 6 .ooo se r ≠ s |
| 7 .oooooo Union (r, s) |
| 8 .oooooo c := c − 1 |
| 9 . devolva c |
A implementação das operações Find e Union pode precisar de alguma estrutura de dados auxiliar; essa estrutura é prepara e inicializada pela operação Initialize.
As seções seguintes mostrarão diversas implementações das operações Union e Find. O desafio é obter uma implementação em que ambas as operações consumam tempo constante, ou seja, tempo independente de n.
Nossa primeira implementação do tipo abstrato de dados union-find é muito simples. Os diretores das componentes ficam armazenados num vetor dir indexado pelos vértices do grafo: para cada vértice v, dir[v] é o diretor da componente que contém v. A implementação de Find é óbvia:
| Find-1 (v) |
| 1 . devolve dir[v] |
Um vértice v é o diretor de alguma componente se e somente se dir[v] = v. No início dos trabalhos, cada componente tem um só vértice, que é também o diretor da componente:
| Initialize-1 ( ) |
| 1 . para cada vértice v |
| 2 .ooo dir[v] := v |
A operação Union recebe dois diretores e faz a fusão de suas componentes. Para isso, basta informar todos os vértices de uma das componentes que eles têm um novo diretor:
| Union-1 (r, s) ▷ r ≠ s |
| 1 . para cada vértice v |
| 2 .ooo se dir[v] = r |
| 3 .ooooooo dir[v] := s |
A operação Find-1 é muito rápida. Já a operação Union-1 é muito lenta: ela que consome Ω(n) unidades de tempo no pior caso, sendo n o número de vértices do grafo.
Para tornar o operação Union mais rápida,
vamos introduzir a ideia de superior imediato
, ou chefe
,
na hierarquia corporativa.
Imagine que cada vértice de uma componente tem um chefe,
que é um outro vértice da mesma componente.
Cada chefe, por sua vez, tem um chefe,
e assim por diante, até chegar a um vértice que é chefe dele mesmo.
Essa ideia precisa ser implementada de tal modo que
um único vértice de cada componente seja chefe dele mesmo;
esse vértice faz o papel de diretor da componente.
Os chefes ficam armazenados num vetor chefe de modo que chefe[v] é o chefe do vértice v. O vetor dir da implementação anterior desaparece, e um vértice v é considerado diretor se e somente se chefe[v] = v. A inicialização do vetor chefe é simples:
| Initialize-2 ( ) |
| 1 . para cada vértice v |
| 2 .ooo chefe[v] := v |
Para implementar a operação Find, basta seguir a sequência de chefes até chegar ao diretor:
| Find-2 (v) |
| 1 . enquanto chefe[v] ≠ v |
| 2 .ooo v := chefe[v] |
| 3 . devolva v |
Uma folha é qualquer vértice que não é chefe de ninguém. Um caminho é qualquer sequência de vértices da forma (u, chefe[u], chefe[chefe[u]], … ). A altura de um vértice v é comprimento do mais longo caminho que começa numa folha e termina em v. A profundidade de um vértice v é o comprimento do único caminho que começa em v e termina num diretor.
O consumo de tempo de Find-2 é proporcional à profundidade de v e portanto, no pior caso, proporcional ao máximo das alturas dos diretores. Infelizmente, a altura de um diretor pode chegar a n − 1. Portanto, o algoritmo Find-2 é lento.
Em compensação, a implementação de Union é muito rápida:
| Union-2 (r, s) ▷ r ≠ s |
| 1 . chefe[r] := s |
Para fugir do mau desempenho de Find-2, é preciso limitar a altura dos diretores. Um truque simples garante esse efeito: a operação Union deve fazer com que o diretor da maior das duas componentes passe a ser o diretor da fusão das duas componentes. Essa heurística é conhecida como union-by-rank.
Para implementar a heurística, é preciso manter na estrutura de dados a informação sobre a altura de cada vértice. As alturas dos vértice serão mantidas em um vetor alt de modo que alt[v] seja a altura do vértice v.
| Union-3 (r, s) ▷ union-by-rank; r ≠ s |
| 1 . se alt[r] > alt[s] |
| 2 .oooo chefe[s] := r |
| 3 . senão chefe[r] := s |
| 4 .senão se alt[r] = alt[s] |
| 5 .senão oooo alt[s] := alt[r] + 1 |
No início do processo, antes que a primeira aresta seja inserida, o altura de cada vértice é 0:
| Initialize-3 ( ) |
| 1 . para cada vértice v |
| 2 .ooo chefe[v] := v |
| 3 .ooo alt[v] := 0 |
A implementação Find-3 é idêntica à Find-2.
Exemplo A. Vamos executar o algoritmo Componentes para calcular o número de componentes do grafo da figura. Usaremos as implementações Find-3 e Union-3 de Find e Union. As arestas serão examinadas uma a uma na ordem indicada a seguir.
53 71 76 20 07 01 34 54 74 06 46 05
Veja o estado dos vetores chefe e alt no início de cada execução da linha 4 do algoritmo.
chefe[] alt[]
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0
53 0 1 2 3 4 3 6 7 0 0 0 1 0 0 0 0
71 0 1 2 3 4 3 6 1 0 1 0 1 0 0 0 0
76 0 1 2 3 4 3 1 1 0 1 0 1 0 0 0 0
20 0 1 0 3 4 3 1 1 1 1 0 1 0 0 0 0
07 1 1 0 3 4 3 1 1 1 2 0 1 0 0 0 0
34 1 1 0 3 3 3 1 1 1 2 0 1 0 0 0 0
74 1 1 0 1 3 3 1 1 1 2 0 1 0 0 0 0
Veja a evolução da estrutura
union-find à medida que arestas são examinadas no grafo.
O chefe de cada vértice é indicado por uma traço
que sobe
do vértice ao seu chefe:
1
3 7 6 0
2
5 4
53
1
3 7 6 0 3 é o chefe de 5
_|
| 2
5 4
71
1
__|
|
3 7 6 0
_|
| 2
5 4
76
1 1 é o chefe de 7 e 6
__|
| |
3 7 6 0
_|
| 2
5 4
20
1
__|
| |
3 7 6 0
_| |
| 2
5 4
07
1 1 é o diretor de 7,6,0,2
__|__
| | |
3 7 6 0
_| |
| 2
5 4
01
34
1
__|__
| | |
3 7 6 0
_|_ |
| | 2
5 4
54
74
1
__ __|__
| | | |
3 7 6 0
_|_ |
| | 2
5 4
06
46
05
Ao final do processo, temos uma só componente e o diretor da componente é 1.
Depois de cada execução de Union-3, para todo vértice v, alt[v] é a altura de v. Segue daí que, depois de cada operação Union-3, para cada vértice v, temos
| alt[v] ≤ lg n(v), | (A) |
sendo n(v) o número de vértices
na subestrutura pendurada
em v,
ou seja, o número de vértices que precisam passar por
v
para chegar ao diretor da componente.
Veja a prova da desigualdade (A): É claro que a desigualdade vale antes da primeira execução da operação Union-3. Suponha agora que a desigualdade vale antes de alguma execução Union-3. Vamos mostrar que a desigualdade continua valendo depois da execução.
A execução da operação não diminui alt[v] nem n(v) para nenhum vértice v. Portanto, a única situação que pode ameaçar a validade de (A) é aquela em que o valor de alt[v] aumenta. Mas isso só acontece se v = s e alt[r] = alt[s] (veja a linha 4 de Union-3). Suponha então que estamos nessa situação e adote as abreviaturas k = alt[r] = alt[s], M = n(r) e N = n(s) no início da operação. Por hipótese de indução, k ≤ lg M e k ≤ lg N, ou seja, M ≥ 2k e N ≥ 2k. Depois da operação, teremos
| alt[s] | = | k+1 |
| = | lg 2k+1 | |
| = | lg (2k + 2k) | |
| ≤ | lg (M + N) | |
| = | lg n(s) |
pois M + N é o valor de n(s) depois da operação (veja a linha 3 de Union-3). Isso termina a prova de (A).
A desigualdade (A) tem a seguinte consequência imediata: no início de cada repetição do bloco de linhas 4-8 de Componentes, a altura de todo vértice é no máximo lg n, sendo n o número de vértices de G. Em particular, a altura de qualquer diretor é no máximo lg n. Como o consumo de tempo de Find-3 é, no pior caso, proporcional à altura de um diretor, podemos dizer que toda execução de Find-3 consome
Ο(lg n)
unidades de tempo. Quanto a Union-3, é claro que essa operação consome Ο(1) unidades de tempo. Assim, essa terceira implementação do tipo union-find é bem melhor que as anteriores.
a———b———f———e | | | | c———d———h———g
| Union-3A (r, s) |
| 1 . se alt[r] = alt[s] |
| 2 .oooo chefe[r] := s |
| 3 .oooo alt[r] := alt[r] + 1 |
| 4 . senão se alt[r] > alt[s] |
| 5 .senão ooo chefe[r] := s |
| 6 .senão senão chefe[s] := r |
Podemos melhorar o desempenho da terceira implementação da estrutura union-find se usarmos o truque conhecido como path compression: a cada execução da operação Find, plante atalhos no caminho que leva ao diretor da componentes. Mais precisamente, para cada vértice visitado v, adote o diretor da componente de v como novo chefe de v.
| Find-4 (v) ▷ path-compression |
| 1 . se v ≠ chefe[v] |
| 2 .ooo chefe[v] := Find-4 (chefe[v]) |
| 3 . devolva chefe[v] |
Os códigos de Union-4 e Initialize-4 são idênticos aos de Union-3 e Initialize-3 respectivamente.
O consumo de tempo amortizado dessa implementação do union-find é de Ο(log* n) unidades de tempo por operação. Tudo se passa (no sentido amortizado) como se o comprimento de todo caminho na estrutura fosse no máximo log* n. (Como sempre, n é o número de vértices do grafo.) A função log* n cresce muuuuito devagar com n. Portanto, do ponto de vista prático, o desempenho desta implementação é essencialmente igual a Ο(1).
A prova da cota Ο(log* n) é deveras complexa. (Veja o livro CLRS.)