Dificuldade ★★☆
3 minutos de Leitura 🕒
Um Conjunto Disjunto (Disjoint Set ou Union-Find) é uma estrutura de dados que mantém uma coleção elementos, que por sua vez estão organizados em vários conjuntos não sobrepostos. Essa estrutura de dados possibilita que elementos sejam agrupados de maneira eficiente.
Algoritmo de Kruskal - Um Conjunto Disjunto é usado no algoritmo de Kruskal para manter controle dos componentes conexos do grafo e garantir que, a cada iteração do algoritmo, as propriedades da árvore geradora mínima em construção não são violadas.
Segmentação de Imagens - Conjuntos Disjuntos podem ser usados em alguns algoritmos de segmentação de imagens, permitindo que pixels sejam agrupados em regiões com propriedades similares.
Aprendizado de Máquina - Conjuntos Disjuntos podem ser usados na etapa de treinamento de alguns algoritmos de aprendizado de máquina, para agrupar dados com base em características similares.
busca (ou find) determina a qual conjunto um determinado elemento pertence.união (ou union) combina dois conjuntos em um único conjunto.Um Conjunto Disjunto pode ser implementado de forma eficiente usando uma coleção de árvores (floresta), onde cada árvore representa um conjunto disjunto.
Função busca(conjunto, elemento):
// Assumir que o elemento é seu próprio representante.
representanteEncontrado = elemento
// Seguir os ponteiros dos nós ancestrais na árvore até chegar à raiz.
Enquanto conjunto[representanteEncontrado] != NULO:
representanteEncontrado = conjunto[representanteEncontrado]
// Retornar a raiz encontrada como resultado da busca.
Retornar representanteEncontrado
Função uniao(conjunto, elemento1, elemento2):
// Buscar o representante para cada elemento.
representante1 = busca(conjunto, elemento1)
representante2 = busca(conjunto, elemento2)
// Verificar se os representantes são diferentes.
Se representante1 != representante2:
// Fazer um representante apontar para o outro.
conjunto[representante1] = representante2
Heurística de União por Tamanho (Union-by-Size ou Weighted-Union). Você pode manter informações sobre o tamanho de cada conjunto. Assim, durante a operação de união, una sempre o conjunto de menor tamanho ao de maior tamanho. Isso ajuda a evitar um desbalanceamento de entre conjuntos e a operação de busca seja mais rápida.
Compressão de Caminho (Path Compression). Durante a operação de busca, atualize o pai de cada nó visitado para apontar diretamente para o representante do conjunto. Isso ajuda a reduzir o número de comparações necessárias para determinar o representante de um conjunto em operações futuras de busca.
Uma implementação de Conjunto Disjunto usando uma coleção de árvores, heurística de união por tamanho e compressão de caminho possui complexidade de tempo sub-logarítmico para as operações de busca e união, em função do número n de elementos na estrutura de dados:
O(log* n)O(log* n)Veja o código completo no GitHub.