Union-Find

Código en:JavaC#PythonJavaScript

En resumen: Union-Find (conjuntos disjuntos) guarda grupos de elementos y dice si dos elementos están en el mismo grupo; con compresión de caminos y unión por tamaño cada operación cuesta casi O(1).

Problema

Un cliente, tres perfiles

La tienda tiene 200 000 perfiles de cliente. La misma clienta se registró tres veces: una con el teléfono, otra con el correo del trabajo y otra desde la app. Recibe tres boletines, sus puntos de fidelidad están repartidos en tres, y el informe dice que tienes más clientes de los que tienes.

La regla es sencilla: dos perfiles con el mismo correo o el mismo teléfono son un solo cliente. Pero es contagiosa. Si el perfil a comparte un teléfono con b, y b comparte un correo con c, entonces a, b y c son un cliente, aunque a y c no tengan nada en común.

¿Cómo encuentras todos los grupos sin comparar cada perfil con todos los demás?

La idea

La primera idea: una etiqueta de grupo

Cada perfil lleva una etiqueta: el número de su grupo. Al principio cada perfil es su propio grupo. Cuando resulta que dos perfiles están vinculados, todo el grupo del segundo recibe la etiqueta del primero.

class Relabel:
    def __init__(self, n):
        self._label = list(range(n))
        self.count = n

    def find(self, x):
        return self._label[x]

    def union(self, a, b):
        old, new = self._label[b], self._label[a]
        if old == new:
            return False
        for i, group in enumerate(self._label):
            if group == old:
                self._label[i] = new
        self.count -= 1
        return True

El programa recorre los perfiles y recuerda, para cada contacto, qué perfil lo tuvo primero. Cuando vuelve a ver el contacto, fusiona los dos perfiles:

profiles = [
    ["marta@correo.es", "600 100 200"],
    ["600 100 200", "m.vega@empresa.es"],
    ["pedro@correo.es"],
    ["m.vega@empresa.es"],
    ["611 300 400", "pedro@correo.es"],
    ["nico@correo.es"],
    ["611 300 400"],
    ["nico@correo.es", "622 500 600"],
    ["marta@correo.es", "611 300 400"],
]
accounts = Relabel(len(profiles))
owner = {}
for p, contacts in enumerate(profiles):
    for contact in contacts:
        if contact in owner:
            accounts.union(owner[contact], p)
        else:
            owner[contact] = p
print("Grupos:", accounts.count)
print("Principal:", *(accounts.find(p) for p in range(len(profiles))))

Salida

Grupos: 2
Principal: 2 2 2 2 2 5 2 5 2

Funciona, pero cada fusión recorre todos los perfiles para encontrar cuáles hay que renombrar. Con n perfiles y unas n fusiones son unas n² miradas: decenas de miles de millones para 200 000 perfiles.

La idea

Un bosque de padres

En vez de que cada perfil lleve la etiqueta del grupo, cada perfil apunta a un padre: otro perfil del grupo. El grupo es un árbol, y el perfil que apunta a sí mismo es la raíz: el perfil principal del grupo.

• find(x) sube por los padres hasta llegar a una raíz. Dos perfiles están en un grupo si find da la misma raíz para ambos.
• union(a, b) encuentra las raíces de los dos y cuelga una debajo de la otra. Toca una celda del arreglo, por grande que sea el grupo.

Por sí solo, el bosque puede convertirse en una cadena larga, y entonces find es lento. Por eso hay dos mejoras, y juntas son Union-Find:

1. Unión por tamaño. Cada raíz sabe cuántos perfiles tiene su árbol. El árbol más pequeño va debajo del más grande, así la profundidad crece despacio.
2. Compresión de caminos. Cuando find llega a la raíz, recorre el camino otra vez y cuelga cada perfil de él directamente de la raíz. El siguiente find para ellos es un paso.

Míralo

Una fusión por dentro

class UnionFind:
    def __init__(self, n):
        self._parent = list(range(n))
        self._size = [1] * n
        self.count = n

    def find(self, x):
        root = x
        while self._parent[root] != root:
            root = self._parent[root]
        while self._parent[x] != root:
            above = self._parent[x]
            self._parent[x] = root
            x = above
        return root

    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]
        self.count -= 1
        return True

union devuelve False si los perfiles ya están en un grupo: entonces no cambia nada y count se queda igual.

El mismo programa que arriba, con UnionFind en vez de Relabel:

profiles = [
    ["marta@correo.es", "600 100 200"],
    ["600 100 200", "m.vega@empresa.es"],
    ["pedro@correo.es"],
    ["m.vega@empresa.es"],
    ["611 300 400", "pedro@correo.es"],
    ["nico@correo.es"],
    ["611 300 400"],
    ["nico@correo.es", "622 500 600"],
    ["marta@correo.es", "611 300 400"],
]
accounts = UnionFind(len(profiles))
owner = {}
for p, contacts in enumerate(profiles):
    for contact in contacts:
        if contact in owner:
            accounts.union(owner[contact], p)
        else:
            owner[contact] = p
print("Grupos:", accounts.count)
print("Principal:", *(accounts.find(p) for p in range(len(profiles))))

Salida

Grupos: 2
Principal: 0 0 0 0 0 5 0 5 0

class UnionFind:
    def __init__(self, n):
        self._parent = list(range(n))
        self._size = [1] * n
        self.count = n

    def find(self, x):
        root = x
        while self._parent[root] != root:
            root = self._parent[root]
        while self._parent[x] != root:
            above = self._parent[x]
            self._parent[x] = root
            x = above
        return root

    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]
        self.count -= 1
        return True

Paso a paso, en palabras

1. Nueve perfiles de cliente, cada uno es su propio grupo: _parent[i] = i, cada perfil es una raíz. Grupos: 9.
2. El perfil 1 tiene el teléfono de 0: union(0, 1). Las raíces son distintas, así que 1 se cuelga de 0. Luego 3 tiene el correo de 1: find(1) sube hasta 0, y 3 también va debajo de 0.
3. Igual con los demás: 4 debajo de 2 (correo compartido), 6 debajo de 2 (teléfono compartido), 7 debajo de 5. Una unión cambia una celda del arreglo: el padre de una raíz.
4. El perfil 8 tiene el correo de 0: 8 va debajo de 0. El grupo de 0 ya tiene cuatro perfiles.
5. 8 también tiene el teléfono de 4. find(4) llega a 2, find(8) llega a 0. El árbol de 2 es más pequeño (3 contra 4), por eso su raíz va debajo de 0: cambia una celda, tres perfiles cambian de grupo.
6. Al final el programa llama a find para cada perfil. find(4) sube 4 → 2 → 0 y luego cuelga 4 directamente de 0: compresión de caminos. Igual con 6.
7. Dos grupos, los perfiles principales son 0 y 5. El árbol es plano: el siguiente find(4) es un paso.

Los dos grupos son los mismos que con etiquetas, solo cambian los números: aquí el perfil principal es la raíz, con etiquetas es la etiqueta que sobrevivió.

Pruébalo

Predice la salida

Seis perfiles y seis vínculos. Después de cada unión el programa anota el número de grupos:

uf = UnionFind(6)
links = [[0, 1], [1, 2], [0, 2], [3, 4], [4, 5], [2, 3]]
counts = []
for a, b in links:
    uf.union(a, b)
    counts.append(uf.count)
print(counts)

Respuesta

[5, 4, 4, 3, 2, 1]

[1, 1, 1, 1, 1, 1]

[5, 4, 3, 2, 1, 0]

Comprobar

La idea

El find recursivo

La compresión suele escribirse con recursión: find sobre el padre da la raíz, y el perfil se cuelga de ella. Cada perfil del camino hace lo mismo al volver.

def find(self, x):
    if self._parent[x] != x:
        self._parent[x] = self.find(self._parent[x])
    return self._parent[x]

Pruébalo tú:

def find(self, x):
    if self._parent[x] != x:
        self._parent[x] = 
    return self._parent[x]

Comprobar

Con la unión por tamaño los árboles son bajos: como mucho 17 niveles para 200 000 perfiles (log₂ 200 000 ≈ 17,6). Así que la recursión es segura.

Más precisamente, para curiosos

Sin la unión por tamaño un árbol puede convertirse en una cadena de n perfiles, y el find recursivo hace n llamadas anidadas, apiladas una sobre otra, como en la lección «Recursión». Python se detiene por defecto en 1000 llamadas anidadas y lanza RecursionError. El bucle de la lección no tiene este problema con ninguna forma de árbol.

La idea

Cuánto cuesta

Ejecuta las tres maneras. Hay n perfiles y n vínculos al azar «estos dos comparten un contacto». Se cuenta:

• con etiquetas: cada mirada a la etiqueta de un perfil al renombrar;
• con el bosque simple y con Union-Find: cada paso de find, incluida la mirada a la propia raíz.

• Reetiquetar todo el grupo O(n²)
• Bosque de padres, sin mejoras O(n²)
• Union-find: compresión y tamaño O(n)

Algoritmo	n = 10	n = 1000	n = 10.000	n = 100.000
Reetiquetar todo el grupo	90	843.000	≈ 84.300.000	≈ 8.430.000.000
Bosque de padres, sin mejoras	30	25.641	2.102.613	≈ 210.261.300
Union-find: compresión y tamaño	30	3295	33.355	334.195

El código se ejecuta en tu navegador, en JavaScript. La cantidad de operaciones es la misma en todos los lenguajes, porque el algoritmo es el mismo. El tiempo depende de la máquina, así que solo sirve para comparar. «≈» es una estimación a partir de la curva: un n tan grande no lo ejecutamos, para que la página no se congele.

class UnionFind:
    def __init__(self, n):
        self._parent = list(range(n))
        self._size = [1] * n
        self.count = n

    def find(self, x):
        root = x
        while self._parent[root] != root:
            root = self._parent[root]
        while self._parent[x] != root:
            above = self._parent[x]
            self._parent[x] = root
            x = above
        return root

    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]
        self.count -= 1
        return True

Con 1000 perfiles las etiquetas necesitan 843 000 miradas, el bosque simple 25 641 pasos y Union-Find 3295. Con 10 000 el bosque simple ya necesita 2 102 613 pasos: sus árboles se vuelven cadenas largas. Union-Find necesita 33 355, unos 3,3 pasos por vínculo, y con 100 000 perfiles 334 195: lo mismo por vínculo.

Es un coste amortizado (mira la complejidad amortizada): un find puede ser largo, pero después el camino queda plano y los siguientes son cortos. En conjunto cada operación cuesta casi O(1).

Más precisamente, para curiosos

Con más precisión: con unión por tamaño (o por rango, mira abajo) y compresión de caminos, m operaciones sobre n elementos cuestan O(m · α(n)). α es la inversa de la función de Ackermann. Crece tan despacio que para cualquier n que quepa en el universo vale 4 como mucho. Por eso en la práctica se dice «casi constante». La demostración es de Tarjan (1975) y no es corta.

En vez del tamaño puedes llevar un rango: una cota superior de la altura del árbol. La raíz con el rango menor va debajo de la otra, y un rango solo crece cuando los rangos son iguales. El coste es el mismo. El tamaño es más cómodo porque también responde a «cuántos perfiles hay en el grupo».

Pruébalo

Encuentra el error

Un compañero escribió la unión. El número de grupos sale 2, pero hay tres perfiles principales distintos:

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[b] = ra
    self._size[ra] += self._size[rb]
    self.count -= 1
    return True

profiles = [
    ["marta@correo.es", "600 100 200"],
    ["600 100 200", "m.vega@empresa.es"],
    ["pedro@correo.es"],
    ["m.vega@empresa.es"],
    ["611 300 400", "pedro@correo.es"],
    ["nico@correo.es"],
    ["611 300 400"],
    ["nico@correo.es", "622 500 600"],
    ["marta@correo.es", "611 300 400"],
]
accounts = UnionFind(len(profiles))
owner = {}
for p, contacts in enumerate(profiles):
    for contact in contacts:
        if contact in owner:
            accounts.union(owner[contact], p)
        else:
            owner[contact] = p
print("Grupos:", accounts.count)
print("Principal:", *(accounts.find(p) for p in range(len(profiles))))

Salida

Grupos: 2
Principal: 0 0 2 0 2 5 2 5 0

¿En qué línea está el error?

Elige la línea con el error.

1def union(self, a, b):2 ra, rb = self.find(a), self.find(b)3 if ra == rb:4 return False5 if self._size[ra] < self._size[rb]:6 ra, rb = rb, ra7 self._parent[b] = ra8 self._size[ra] += self._size[rb]9 self.count -= 110 return True

Comprobar

La idea

Dónde más

Union-Find responde a una pregunta: ¿están estos dos en un grupo?, cuando los grupos solo crecen. Lo mismo vale para:

• zonas de reparto: almacenes y calles entre ellos. Dos almacenes están en una zona si hay una ruta, quizá pasando por otros almacenes;
• una red de computadoras: qué máquinas se alcanzan entre sí después de cada cable nuevo;
• el algoritmo de Kruskal para la red de calles más barata, que verás en el módulo Grafos (algo-graphs). Allí Union-Find dice si una calle nueva cierra un ciclo.

Un límite: Union-Find no separa. Si un teléfono compartido resulta ser de oficina y ha fusionado a dos clientes distintos, la unión no se puede deshacer. Por eso los vínculos se guardan aparte, y los grupos se reconstruyen cuando se quita un vínculo. Por eso también un teléfono que aparece en cientos de perfiles normalmente no se usa para fusionar.

Ejercicio

Zonas de reparto

Resuélvelo en tu editor.

Zonas. Hay 10 almacenes (0 … 9) y calles entre ellos: 0-1, 1-2, 3-4, 5-6, 6-7, 7-5, 8-9. Añade dos métodos a la clase: connected(a, b), que dice si dos almacenes están en una zona, y size_of(x), que devuelve cuántos almacenes hay en la zona de x. Imprime el número de zonas, si 0 y 2 y si 2 y 3 están en una zona, y cuántos almacenes hay en la zona de 5. Luego abre una calle nueva 2-3 e imprime otra vez el número de zonas y si 0 y 4 están en una zona:

Salida

Zonas: 4
0 y 2: sí
2 y 3: no
Zona de 5: 3 almacenes
Nueva calle 2-3. Zonas: 3
0 y 4: sí

Más tareas

• Grupos por nombre. Imprime cada grupo de perfiles como una lista: el perfil principal y todos los perfiles debajo de él.
• El grupo más grande. Lleva el tamaño del grupo más grande mientras fusionas, sin recorrer todas las raíces al final.
• Unión por rango. Cambia el tamaño por el rango y compara el número de pasos de find con los de Bench.

Test

Ponte a prueba

1. Los perfiles a y b comparten un correo, b y c comparten un teléfono, y d no comparte nada con nadie. ¿Cuántos clientes son?

3: a y c no comparten ningún contacto4: cada perfil es distinto2: a, b y c son un cliente, d es otro

2. ¿Qué hace union cuando los dos perfiles ya están en un grupo?

Nada: find da la misma raíz y el número de grupos se queda igualBaja el número de grupos en unoCuelga la raíz de sí misma

3. ¿Por qué la raíz del árbol más pequeño va debajo de la raíz del más grande y no al revés?

Da igual, solo queda más bonitoPara que el perfil más antiguo siga siendo el principalPara que la profundidad solo crezca cuando los tamaños son iguales y nunca pase de log₂ n

4. Dos perfiles se fusionaron por un teléfono compartido, y resulta que es un teléfono de oficina. ¿Cómo los separas?

Vuelves a construir los grupos a partir de los vínculos, sin el equivocadoQuitas el móvil del arreglo de padresCon una unión inversa

Comprobar

Empezar la lección de nuevo

Lecciones relacionadas

• Se basa en: Lambdas · Complejidad en tiempo: contar pasos · Big-O: cómo crece el trabajo · Complejidad amortizada
• Continúa en: Árbol de expansión mínima · Algoritmos voraces y cuándo funcionan
• Ejercicios sobre el tema: Estructuras de datos