União-busca
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.
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 | |||||||||||||||||
|
História
editarAs 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
editarUma 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.
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
editarO algoritmo união-busca (Union-Find) executa três operações na estrutura de dados:
Construção
editarA 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
editarA 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
editarA 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
editarA redução de caminho faz com que todos os demais nós no caminho apontem para seu avô.
Divisão de caminho
editarA divisão do caminho faz com que cada nó no caminho aponte para seu avô.
Pseudo-código
editarCompressã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
editarUniã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
editarUniã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
editarUnião por tamanho sempre anexa a árvore com menos elementos à raiz da árvore que possui mais elementos.
Pseudo-código
editarUniã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
- ↑ 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
- ↑ 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.
- ↑ Hopcroft, J. E.; Ullman, J. D. (1973). «Set Merging Algorithms». SIAM Journal on Computing. 2 (4): 294–303. doi:10.1137/0202024
- ↑ 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
- ↑ 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
- ↑ 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.
- ↑ «Worst-case analysis of set union algorithms». Journal of the ACM. 31. doi:10.1145/62.2160