Lançado · em melhoria
Algorithm
Union-Find (conjuntos disjuntos) mantém elementos em grupos sem sobreposição e une grupos ou verifica se dois elementos estão juntos em tempo quase constante.
Union-Find, também chamada de estrutura de conjuntos disjuntos, mantém uma coleção de elementos dividida em conjuntos que não se sobrepõem. Ela oferece só duas operações: find retorna o representante do conjunto ao qual um elemento pertence, e union junta os conjuntos de dois elementos. Cada conjunto é guardado como uma árvore de ponteiros para o pai, e a raiz da árvore é o representante.
Quando as conexões só aumentam e é preciso perguntar várias vezes se dois elementos estão conectados, Union-Find é muito mais rápida do que percorrer o grafo a cada pergunta. Com compressão de caminho e união por posto ou tamanho, o custo amortizado por operação cai para a função inversa de Ackermann α(n), que não passa de 4 para nenhuma entrada realista. É a ferramenta padrão por trás da árvore geradora mínima de Kruskal, da detecção de ciclos, das componentes conexas e de problemas de agrupamento como a mesclagem de contas, e aparece com frequência em entrevistas de programação.
Comece implementando find e union sobre um único array parent e acompanhe à mão como uma árvore vira uma corrente sem otimizações. Depois adicione a união por tamanho e a compressão de caminho, uma de cada vez, observando como a profundidade das árvores muda. Por fim, resolva problemas de componentes conexas, detecção de ciclos e Kruskal para se acostumar a usar o valor de retorno de union.
find segue os ponteiros para o pai até a raiz, o representante, e union pendura uma raiz sob a outra para juntar dois conjuntos.
find liga diretamente à raiz os nós visitados e achata a árvore, deixando as chamadas seguintes mais rápidas.
Pendurar a árvore menor sob a maior mantém a altura de cada árvore em no máximo log n.
Com as duas otimizações, m operações custam O(m α(n)), e a função inversa de Ackermann α(n) vale no máximo 4 na prática.
A classe DSU guarda os conjuntos em dois arrays, parent e size. find sobe pelos ponteiros e usa a divisão do caminho pela metade, ligando cada nó ao avô, para manter as árvores rasas. union pendura o conjunto menor sob o maior e retorna False quando os dois elementos já estão no mesmo conjunto. O exemplo junta seis elementos em três grupos e imprime verificações de pertencimento e o número de conjuntos.
union_find.py
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path halving
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
dsu = DSU(6)
for a, b in [(0, 1), (1, 2), (3, 4)]:
dsu.union(a, b)
print(dsu.find(2) == dsu.find(0)) # True
print(dsu.find(4) == dsu.find(5)) # False
print(len({dsu.find(x) for x in range(6)})) # 3
python union_find.pySeis capítulos que levam você da instalação aos conceitos essenciais de Union-Find.
Tire dúvidas, compartilhe experiências e troque opiniões sobre Union-Find.
Ainda não há discussões. Comece a primeira.
0 comentários
Fazer login · Faça login para deixar um comentário.
Seja o primeiro a comentar.