A estrutura union-find

Esta página discute o tipo abstrato de dados (= abstract data typeADT) 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.

Cálculo das componentes

figs/Sedgewick-Wayne/tinyG-x.png

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 rs
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.

Exercícios 1

  1. Como usar o algoritmo Componentes para decidir se um grafo é conexo?

Primeira implementação

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)  rs
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.

Exercícios 2

  1. Mostre um exemplo completo em que Union-1 consome tempo proporcional a n.

Segunda implementação

figs/mine/example-UF-tree.png

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)  rs
1 . chefe[r] := s

Exercícios 3

  1. ★ Suponha que next é um vetor que leva cada vértice do grafo num outro vértice da mesma componente. Esse vetor pode ser um vetor de chefes?
  2. Mostre um exemplo completo em que a operação Find-2 consome tempo proporcional a n.
  3. ★ Escreva uma versão recursiva da operação Find-2.

Terceira implementação: union-by-rank

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; rs
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.

Sedgewick-part5-java/kruskal-fig-20-13-a.png

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.

Exercícios 4

  1. a———b———f———e
    |   |   |   |
    c———d———h———g
    
    Considere o algoritmo Componentes com as implementações Initialize-3, Find-3 e Union-3 de Initialize, Find e Union respectivamente. Submeta o grafo da figura ao algoritmo tomando as arestas na ordem  ba dc db fe hg hf hd ac eg bf. (Execute o código de Union-3 exatamente.) Dê o estado dos vetores chefe e alt no fim da execução do algoritmo.
  2. É verdade que depois de cada execução da operação Union-3, para cada vértice v, alt[v] é a profundidade do vértice v?
  3. ★ Prove que depois de cada execução da operação Union-3, para cada vértice v, alt[v] é a altura do vértice v.
  4. ★ Complete os detalhes da prova da desigualdade (A).
  5. A seguinte variante de Union-3 está correta?
    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
  6. Mostre que cada execução de Find-3 consome Ο(lg n) unidades de tempo.
  7. Quanto tempo o algoritmo Componentes consome para calcular o número de componentes de um grafo com n vértices e m arestas? Suponha que o algoritmo usa as implementações Initialize-3, Find-3 e Union-3 de Initialize, Find e Union respectivamente. Mostre que Componentes consome Ο(n + m lg n) unidades de tempo.

Quarta implementação: path compression

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 vchefe[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.)

Exercícios 5

  1. Refaça o exemplo A depois de acrescentar a aresta 24 ao grafo. Processe a nova aresta depois de 54 mas antes de 74.
  2. Mostre que cada execução de Find-4 consome Ο(lg n) unidades de tempo.
  3. ★ Adote as implementações Initialize-4, Find-4 e Union-4 da estrutura union-find. É verdade que alt[v] ≤ 1 para todo vértice v?