Publicado · en mejora
Algorithm
Union-Find (conjuntos disjuntos) agrupa elementos sin solapamiento y une grupos o comprueba si dos elementos están juntos en tiempo casi constante.
Union-Find, también llamada estructura de conjuntos disjuntos, mantiene una colección de elementos repartida en conjuntos que no se solapan. Ofrece solo dos operaciones: find devuelve el representante del conjunto al que pertenece un elemento y union fusiona los conjuntos de dos elementos. Cada conjunto se guarda como un árbol de punteros al padre, y la raíz del árbol es su representante.
Cuando las conexiones solo se añaden y hay que preguntar una y otra vez si dos elementos están conectados, Union-Find es mucho más rápida que recorrer el grafo cada vez. Con compresión de caminos y unión por rango o tamaño, el coste amortizado por operación baja a la función inversa de Ackermann α(n), que no supera 4 para ninguna entrada realista. Es la herramienta habitual detrás del árbol de expansión mínima de Kruskal, la detección de ciclos, las componentes conexas y problemas de agrupación como fusionar cuentas, y aparece a menudo en entrevistas técnicas.
Empieza implementando find y union sobre un único arreglo parent y sigue a mano cómo un árbol degenera en una cadena sin optimizaciones. Después añade la unión por tamaño y la compresión de caminos de una en una y observa cómo cambia la profundidad del árbol. Por último, resuelve problemas de componentes conexas, detección de ciclos y Kruskal para acostumbrarte a aprovechar el valor que devuelve union.
find sigue los punteros al padre hasta la raíz, el representante, y union cuelga una raíz bajo la otra para fusionar dos conjuntos.
find enlaza directamente con la raíz los nodos que visita y aplana el árbol, de modo que las llamadas siguientes son más rápidas.
Colgar el árbol más pequeño bajo el más grande mantiene la altura de cada árbol en log n como máximo.
Con ambas optimizaciones, m operaciones cuestan O(m α(n)), y la función inversa de Ackermann α(n) vale como mucho 4 en la práctica.
La clase DSU guarda los conjuntos en dos arreglos, parent y size. find sube por los punteros al padre y usa la reducción de caminos a la mitad, enlazando cada nodo con su abuelo, para mantener los árboles planos. union cuelga el conjunto más pequeño bajo el más grande y devuelve False si ambos elementos ya están en el mismo conjunto. El ejemplo une seis elementos en tres grupos y muestra comprobaciones de pertenencia y el 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 te llevan desde la instalación hasta las ideas clave de Union-Find.
Haz preguntas, comparte tu experiencia e intercambia opiniones sobre Union-Find.
Todavía no hay debates. Empieza el primero.
0 comentarios
Iniciar sesión · Inicia sesión para dejar un comentario.
Sé el primero en comentar.