União-busca

União-busca/Disjoint-set
Tipo Árvore
Ano 1964
Inventado por Bernard Galler e Michael John Fischer
Complexidade de Tempo em Notação big O
Algoritimo Caso Médio Pior Caso
Espaço O(n)[1] O(n)[1]
Busca O(α(n))[1] O(α(n))[1]
Merge O(α(n))[1] O(α(n))[1]

Em ciência da computação, uma estrutura de dados união-busca também chamado de estrutura de dados disjoint-set é uma estrutura de dados que mantém o controle de um conjunto de elementos particionados em subconjuntos disjuntos (não sobreposicionados). Ele fornece operações com tempo quase constante (delimitadas pela inversa função de Ackermann) para adicionar novos conjuntos, para mesclar conjuntos existentes e para determinar se os elementos estão no mesmo conjunto. Além de muitos outros usos, os disjoint-sets desempenham um papel fundamental no algoritmo de Kruskal para encontrar a árvore de extensão mínima em um grafo.


História

As estruturas de dados união-busca foram descritos pela primeira vez por Bernard A. Galler e Michael J. Fischer no ano de 1964.[2] Em 1973, a complexidade do algoritmo foi definida como , a função Logaritmo iterado de .[3] Mas em 1975, Robert Tarjan foi o primeiro a provar (Função Inversa de Ackermann)[4] como novo limitante superior para o algoritmo, e, em 1979, mostrou que a mesma função era limitante inferior para um caso específico.[5]

Em 1989, Fredman e Saks mostraram que elementos são acessados por qualquer estrutura de dados união-busca para cada operação executada (custo amortizado).[6]

Implementação

Uma estrutura de dados união-busca consiste de uma lista de conjuntos disjuntos identificados por um elemento representante. Para implementar essa estrutura, cada elemento armazena um id (número de identificação), um ponteiro para o pai, e, em algoritmos eficientes, o tamanho do conjunto ou um valor de classificação. Inicialmente, cada elemento representa um subconjunto.

Estado inicial da busca-união.

Os ponteiros para pai são arranjados de forma a constituir uma ou mais árvores, cada uma representando um conjunto. Se um elemento não possui um ponteiro para outro elemento, então ele é a raiz da árvore e, logo, o representante do conjunto. Caso contrário, se um elemento aponta para outro, então ele pertence ao conjunto representado pelo elemento que é a raiz da árvore.

Operações

O algoritmo união-busca (Union-Find) executa três operações na estrutura de dados:

Construção

A operação de Construção cria um novo conjunto iniciando cada elemento com um id exclusivo, um ranque de 0 e um ponteiro para ele mesmo. O ponteiro pai para si mesmo indica que o elemento é o membro representativo de seu próprio conjunto.

A operação Construção tem complexidade de tempo.

Busca

A operação de busca determina em qual subconjunto um elemento em particular está. Busca (x) segue a cadeia de ponteiros pai de x da árvore até atingir um elemento raiz, cujo pai é ele mesmo. Esse elemento raiz é o membro representativo do conjunto ao qual x pertence e pode ser x.

Para melhorar a eficiência da busca geralmente são aplicados métodos que diminuem a profundidade das árvores formadas pelos subconjuntos:

Compactação de caminho

A compactação de caminho nivela a estrutura da árvore fazendo com que cada nó aponte para a raiz sempre que Busca for usado nele. Isso é válido, pois cada elemento visitado no caminho para uma raiz faz parte do mesmo conjunto. A árvore resultante acelera as operações futuras não apenas nesses elementos, mas também naqueles que os referenciam.

Tarjan e Van Leeuwen também desenvolveram algoritmos Busca de uma passagem que são mais eficientes na prática, mantendo a mesma complexidade de pior caso: divisão de caminho e redução de caminho.[7]

Redução de caminho

A redução de caminho faz com que todos os demais nós no caminho apontem para seu avô.

Divisão de caminho

A divisão do caminho faz com que cada nó no caminho aponte para seu avô.

Pseudo-código

Pseudo-código
Compressão de caminho Caminho, metade, Divisão de caminho 
 função Busca(x)
   se x.pai != x
     x.pai := Busca (x.pai)
   return x.pai

 função Busca(x)
   enquanto x.pai != x
     x.pai := x.pai.pai
     x := x.pai
   return x

 função Busca(x)
   enquanto x.pai != x
     x, x.pai := x.pai, x.pai.pai
   return x


União

União (x, y) usa Busca para determinar as raízes das árvores a que x e y pertencem. Se as raízes são distintas, as árvores são combinadas ligando a raiz de uma à raiz da outra. Se isso for feito ingenuamente, como fazendo x um filho de y toda vez que União for chamada, a altura das árvores pode crescer proporcionalmente a n. Para evitar isto, as operações união por classificação ou união por tamanho são usadas.

União por classificação

União por classificação sempre atribui a árvore mais compacta (com menor classificação) à raiz da árvore mais alta. Assim, a árvore resultante não é mais alta que as originais, a menos que tenham a mesma altura, caso em que a árvore resultante é mais alta em um nó.

Para implementar união por classificação , cada elemento é associado a uma classificação. Inicialmente, um conjunto tem um elemento e uma classificação de zero. Se dois conjuntos forem unidos e tiverem a mesma classificação, a classificação do conjunto resultante será maior; caso contrário, se dois conjuntos forem unidos e tiverem classificações diferentes, a classificação do conjunto resultante será a maior dos dois. As classificações são usadas em vez de altura ou profundidade, porque a compressão do caminho mudará a altura das árvores com o tempo.

União por tamanho

União por tamanho sempre anexa a árvore com menos elementos à raiz da árvore que possui mais elementos.

Pseudo-código

Pseudo-código
União por classificação União por tamanho 
 função União (x, y)
   xRoot   : = Busca (x)
   yRoot   : = Busca (y)

   // x e y já estão no mesmo conjunto
   se xRoot == yRoot
       Retorna

   // x e y não estão no mesmo conjunto, então nós mesclamos
   if xRoot.rank <yRoot.rank
     xRoot, yRoot   : = yRoot, xRoot // troca xRoot e yRoot

   // fundir o yRoot no xRoot
   yRoot.pai   : = xRoot
   if xRoot.rank == yRoot.rank:
     xRoot.rank   : = xRoot.rank + 1

 função União (x, y)
   xRoot   : = Busca (x)
   yRoot   : = Busca (y)

   // x e y já estão no mesmo conjunto
   se xRoot == yRoot
       Retorna

   // x e y não estão no mesmo conjunto, então nós mesclamos
   if xRoot.size <yRoot.size
     xRoot, yRoot   : = yRoot, xRoot // troca xRoot e yRoot

   // fundir o yRoot no xRoot
   yRoot.pai   : = xRoot
   xRoot.size   : = xRoot.size + yRoot.size


Referências

  1. ↑ a b c d e f Tarjan, Robert Endre (1975). «Efficiency of a Good But Not Linear Set Union Algorithm». Journal of the ACM. 22 (2): 215–225. doi:10.1145/321879.321884 
  2. ↑ Galler, Bernard A.; Fischer, Michael J. (maio de 1964). An improved equivalence algorithm. Communications of the ACM. 7. [S.l.: s.n.] pp. 301–303. doi:10.1145/364099.364331 . The paper originating disjoint-set forests.
  3. ↑ Hopcroft, J. E.; Ullman, J. D. (1973). «Set Merging Algorithms». SIAM Journal on Computing. 2 (4): 294–303. doi:10.1137/0202024 
  4. ↑ Tarjan, Robert E.; van Leeuwen, Jan (1984). «Worst-case analysis of set union algorithms». Journal of the ACM. 31 (2): 245–281. doi:10.1145/62.2160 
  5. ↑ Tarjan, Robert Endre (1979). «A class of algorithms which require non-linear time to maintain disjoint sets». Journal of Computer and System Sciences. 18: 110–127. doi:10.1016/0022-0000(79)90042-4 
  6. ↑ Fredman, M.; Saks, M. (maio de 1989). «The cell probe complexity of dynamic data structures». Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing: 345–354. Theorem 5: Any CPROBE(log n) implementation of the set union problem requires Ω(m α(m, n)) time to execute m Find's and n−1 Union's, beginning with n singleton sets. 
  7. ↑ «Worst-case analysis of set union algorithms». Journal of the ACM. 31. doi:10.1145/62.2160 
Ícone de esboço Este artigo sobre estrutura de dados é um esboço. Você pode ajudar a Wikipédia expandindo-o.