Union-find y conjuntos disjuntos

Qué cubre este capítulo

Union-Find es un árbol que sirve para algo que ningún otro árbol hace: rastrear grupos. Dada una colección de elementos, mantiene una partición en conjuntos disjuntos y responde dos preguntas a una velocidad increíble: "junta los grupos a los que pertenecen estos dos elementos" y "¿estos dos están en el mismo grupo?" No hay búsqueda, no hay orden, no hay rangos; solo agrupación y pertenencia. Su genialidad está en dos optimizaciones diminutas que, juntas, bajan ambas operaciones a tiempo prácticamente constante — tan cerca de O(1) que la cota exacta involucra una función, la inversa de Ackermann, que nunca pasa de 4 para ninguna entrada que puedas almacenar físicamente. Este capítulo lo construye, observa cómo los grupos se fusionan y los caminos se comprimen, y cierra el bloque de árboles con una estructura que demuestra que un árbol puede ser una herramienta de conectividad, no solo de búsqueda.

Un poco de historia

Union-Find fue presentado por Bernard Galler y Michael Fischer en 1964, como una forma de manejar clases de equivalencia — conjuntos de cosas declaradas como "iguales" — que aparecían en compiladores al procesar declaraciones EQUIVALENCE de Fortran. La estructura básica era simple; lo que la volvió legendaria fue su análisis. A finales de los sesenta y durante los setenta se agregaron las dos optimizaciones (union por rango y compresión de caminos), y en 1975 Robert Tarjan demostró el resultado asombroso: con ambas, una secuencia de m operaciones sobre n elementos corre en tiempo O(m·α(n)), donde α es la inversa de la función de Ackermann — una función que crece tan inimaginablemente lento que α(n) es a lo mucho 4 para cualquier n hasta el número de átomos del universo. Tarjan después demostró que esa cota es óptima — ninguna estructura basada en apuntadores puede hacerlo mejor. Así que union-find es esa cosa rara: una estructura con un tiempo de ejecución demostrablemente casi constante y demostrablemente óptimo, descubierta para un problema mundano de compiladores y hoy esencial para los algoritmos de grafos.

La intuición

Representa cada grupo como un árbol, donde cada elemento apunta a un padre y la raíz del árbol es el nombre del grupo (su "representante"). Al inicio, cada elemento es su propia raíz — n grupos de uno. Para saber si dos elementos están en el mismo grupo, sube cada uno hasta su raíz y checa si las raíces coinciden: misma raíz, mismo grupo. Para fusionar dos grupos, encuentra sus dos raíces y haz que una apunte a la otra — un solo cambio de apuntador une dos árboles completos.

Hecho de forma ingenua, esos árboles pueden convertirse en cadenas larguísimas, y subir hasta la raíz se vuelve O(n). Dos arreglos los mantienen planos. Union por rango: al fusionar, siempre cuelga el árbol más bajo debajo del más alto, nunca al revés, para que la altura casi no crezca. Compresión de caminos: cada vez que subes de un nodo hasta la raíz, reapunta ese nodo — y cada nodo del camino — directamente a la raíz, para que el siguiente find sea instantáneo. Union por rango evita que los árboles crezcan a lo alto; la compresión de caminos aplana la altura que quede como efecto secundario de simplemente usar la estructura. Juntas dejan los árboles tan planos que el costo amortizado por operación es la inversa de Ackermann — una constante para todo fin práctico.

Complejidad: cómo escala

Con ambas optimizaciones, union, find y connected son $O(\alpha(n))$ amortizado — inversa de Ackermann, que es a lo mucho 4 para cualquier n concebible, así que trátalo como constante. Crear n singletons es $O(n)$, y el espacio es $O(n)$ (un array de padres y un array de rangos). La gráfica contrasta el union-find real contra la versión ingenua, cuyo union reetiqueta un conjunto entero en O(n) y por eso construirlo es O(n²):

Con 16000 elementos, el union-find optimizado hizo n uniones más n consultas de conectividad en unos 6.6 ms; la versión ingenua tardó 3754 ms — 566 veces más lento, porque cada una de sus uniones barría el array completo. La línea optimizada es prácticamente plana (casi lineal en total, casi constante por operación) mientras que la ingenua sube de forma cuadrática. Esa brecha es todo el valor de las dos optimizaciones: convierten una estructura inservible a escala en uno de los algoritmos más rápidos que se conocen.

En qué es bueno y en qué no

Union-Find es la herramienta perfecta y esencialmente la única para conectividad incremental: sigues fusionando grupos y preguntando si dos cosas están conectadas, y quieres que ambas cosas sean gratis. Es el motor del árbol de expansión mínima de Kruskal (agrega la arista más barata que no forme un ciclo — "que no forme un ciclo" es una consulta de union-find), de encontrar componentes conexas en un grafo, de detectar ciclos mientras construyes uno, y de cualquier pregunta del tipo "¿estas dos cosas están en el mismo cluster/red/clase de equivalencia?". Siempre que la agrupación sea dinámica y nunca necesites ver dentro de un grupo en orden, union-find es imbatible.

Su limitación es la otra cara de su velocidad: solo puede fusionar, nunca separar. No existe un "des-union" eficiente — una vez que dos grupos se juntan, la estructura no tiene forma barata de separarlos, porque la compresión de caminos ya revolvió la forma original del árbol. Tampoco enumera los miembros de un grupo, ni los mantiene ordenados, ni soporta nada más que "¿mismo grupo?" — es un oráculo de conectividad, no un contenedor. Si necesitas quitar conexiones (conectividad dinámica con eliminaciones), ese es un problema mucho más difícil que requiere estructuras completamente distintas. Union-Find responde exactamente un tipo de pregunta, y la responde tan rápido como es posible.

Los datos, o las entradas

El duelo hace n uniones aleatorias y n consultas de conectividad en tamaños crecientes, exponiendo el costo O(n) por union de la versión ingenua frente al casi constante de la optimizada. La animación usa ocho elementos: los fusiona en un solo grupo paso a paso, mostrando cómo el union por rango mantiene los árboles bajitos, y luego corre un find que comprime el camino de un nodo directo a la raíz.

Constrúyelo, una función a la vez

Find sube hasta la raíz y comprime el camino de paso — la operación sobre la que descansa todo:

def find(self, x, probe=None):
    """O(α(n)) amortized: follow parent pointers to the root — the representative of
    x's set. PATH COMPRESSION: on the way back, repoint every node on the path
    directly at the root, so the tree flattens and future finds are nearly instant."""
    root = x
    while self._parent[root] != root:
        root = self._parent[root]
    while self._parent[x] != root:      # compress the path
        self._parent[x], x = root, self._parent[x]
    if probe is not None:
        probe.append(root)
    return root

Union encuentra ambas raíces y cuelga el árbol más bajo debajo del más alto según el rango:

def union(self, a, b):
    """Merge the sets of a and b. UNION BY RANK: attach the shorter tree under the
    taller one so the result stays shallow — never let a tall tree hang off a short
    one. Returns False if they were already in the same set."""
    ra, rb = self.find(a), self.find(b)
    if ra == rb:
        return False
    if self._rank[ra] < self._rank[rb]:
        ra, rb = rb, ra
    self._parent[rb] = ra
    if self._rank[ra] == self._rank[rb]:
        self._rank[ra] += 1
    self._count -= 1
    return True

Míralo funcionar

Aquí hay ocho elementos, cada uno empezando como su propio grupo. El naranja marca los elementos que se están tocando; el azul marca una raíz (el representante de un grupo). Ve paso a paso: las uniones fusionan pares, luego fusionan los pares en grupos de cuatro, colgando el árbol más bajo debajo del más alto para que nada crezca a lo alto. Luego observa el final — un find sobre el elemento 7 sube hasta la raíz, y la compresión de caminos lo reapunta (a él y a su camino) directamente a la raíz, aplanando el árbol para que el siguiente find sea un solo salto. Ese aplanamiento, que ocurre automáticamente en cada find, es la razón de que el costo amortizado sea casi constante: la estructura se cura sola conforme la usas:

El código completo

Las dos versiones en un solo lugar — cambia entre ellas. La pestaña desde cero es el union-find optimizado. La pestaña de librería es la versión ingenua — cada elemento cargando un id de conjunto, con el union reetiquetando el conjunto entero — la dejamos para que veas que toda la diferencia de 566× viene de representar los conjuntos como árboles y aplicar dos pequeñas optimizaciones. (Python no trae union-find integrado; SciPy provee uno para trabajo con grafos.)

"""Union-Find (the disjoint-set union, or DSU) — a tree used not for searching but for
GROUPING. It tracks a partition of elements into disjoint sets and answers two questions
blazingly fast: "merge the groups containing these two elements" (union) and "are these
two in the same group?" (find/connected).

Each set is a tree whose root names the group; two elements are in the same set exactly
when they share a root. Two optimizations — union by rank (attach the shorter tree under
the taller) and path compression (on every find, point nodes straight at the root) — make
both operations effectively constant time: O(α(n)), where α is the inverse Ackermann
function, which is at most 4 for any n you could ever store. It's the structure behind
Kruskal's minimum spanning tree, connected components, and network connectivity.
"""


class UnionFind:
    def __init__(self, n):
        self._parent = list(range(n))       # each element starts as its own root
        self._rank = [0] * n                # upper bound on a tree's height
        self._count = n                     # number of disjoint sets

    # region: find
    def find(self, x, probe=None):
        """O(α(n)) amortized: follow parent pointers to the root — the representative of
        x's set. PATH COMPRESSION: on the way back, repoint every node on the path
        directly at the root, so the tree flattens and future finds are nearly instant."""
        root = x
        while self._parent[root] != root:
            root = self._parent[root]
        while self._parent[x] != root:      # compress the path
            self._parent[x], x = root, self._parent[x]
        if probe is not None:
            probe.append(root)
        return root
    # endregion

    # region: union
    def union(self, a, b):
        """Merge the sets of a and b. UNION BY RANK: attach the shorter tree under the
        taller one so the result stays shallow — never let a tall tree hang off a short
        one. Returns False if they were already in the same set."""
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self._rank[ra] < self._rank[rb]:
            ra, rb = rb, ra
        self._parent[rb] = ra
        if self._rank[ra] == self._rank[rb]:
            self._rank[ra] += 1
        self._count -= 1
        return True
    # endregion

    def connected(self, a, b):
        """Same group? Just compare roots — O(α(n))."""
        return self.find(a) == self.find(b)

    def count(self):
        return self._count

"""There's no union-find in the Python standard library (SciPy has one for graph
connectivity). The instructive counterpart is the NAIVE version — the one before the
optimizations — where each element just carries a set id and a union relabels an entire
set. That's O(n) per union, O(n²) to build up, which is exactly what union by rank and path
compression collapse to near-constant. The face-off shows that gap.
"""


# region: naive
class NaiveUnionFind:
    """Each element stores its set id; union relabels every member of one set — O(n) per
    union. Simple and correct, but quadratic to build, which is why the real union-find
    uses trees with path compression instead."""

    def __init__(self, n):
        self._id = list(range(n))
        self._count = n

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

    def union(self, a, b):
        ia, ib = self._id[a], self._id[b]
        if ia == ib:
            return False
        for i in range(len(self._id)):      # O(n): relabel the whole set
            if self._id[i] == ib:
                self._id[i] = ia
        self._count -= 1
        return True

    def connected(self, a, b):
        return self._id[a] == self._id[b]
# endregion

Desde cero vs librería

La aceleración de 566× es toda la historia, y es una historia puramente de algoritmos — mismo lenguaje, mismo problema, dos ideas. La versión ingenua no está mal escrita; simplemente es fundamentalmente O(n) por union, y O(n) por operación sobre n operaciones es O(n²), que pierde contra lo casi lineal exactamente por el margen que predecirías. Lo que hace notable a union-find es lo poco que separa la versión rápida de la lenta: union por rango es una comparación de dos líneas, la compresión de caminos es un ciclo de dos líneas, y juntas llevan una estructura O(n²) a O(n·α(n)) — lo mejor que puede lograr cualquier estructura de su tipo. Es la demostración más clara del libro de que las mejoras algorítmicas, no el hardware más rápido ni el código de más bajo nivel, son donde viven los órdenes de magnitud: unas cuantas líneas bien elegidas le ganan a un speedup de hardware de 566× que jamás vas a conseguir.

Dónde te lo vas a encontrar de verdad

Union-Find está en todos lados donde la conectividad es dinámica. El algoritmo de árbol de expansión mínima de Kruskal (un capítulo de grafos más adelante) está construido sobre él — agrega aristas de la más barata a la más cara, usando una consulta de union-find para saltarse cualquier arista que formaría un ciclo. Encontrar las componentes conexas de un grafo, o el número de grupos distintos en una red, es un barrido de uniones. El procesamiento de imágenes lo usa para etiquetar regiones conexas de pixeles. La inferencia de tipos y la unificación en compiladores lo usan para clases de equivalencia (su propósito original). Las simulaciones de física lo usan para percolación y clustering. La generación de laberintos estilo Kruskal lo usa. Y cualquier pregunta de "¿estas dos cuentas / servidores / amigos están en el mismo grupo conectado?" a escala es una consulta de union-find. Es una estructura pequeña con una huella enorme en los algoritmos reales.

Puntos clave

Union-Find representa conjuntos disjuntos como árboles nombrados por sus raíces, y con union por rango y compresión de caminos fusiona grupos y prueba pertenencia en tiempo $O(\alpha(n))$ amortizado — prácticamente constante, y demostrablemente óptimo. Es la herramienta para conectividad incremental y agrupación: rápida para fusionar y para "¿mismo grupo?", pero incapaz de separar grupos o de ver dentro de ellos. Dos optimizaciones diminutas la llevan de O(n²) a casi lineal, la lección más filosa del libro de que las grandes ganancias son algorítmicas.

Con eso se completa el bloque de árboles — desde los recorridos y los árboles de búsqueda, pasando por los árboles balanceados y los heaps, hasta los tries especializados, los árboles de consultas por rango, los B-trees orientados a disco y esta estructura de agrupación. El siguiente bloque cambia por completo la forma del problema. Los grafos generalizan a los árboles al soltar la regla de "un solo padre, sin ciclos": cualquier nodo puede conectarse con cualquier otro, formando redes — carreteras, vínculos sociales, dependencias, la web. Casi todo lo que has construido reaparece ahí como maquinaria (las colas mueven la búsqueda en anchura, los heaps mueven Dijkstra, union-find mueve Kruskal), pero las preguntas se vuelven más ricas: caminos más cortos, alcanzabilidad, ordenamiento, árboles de expansión. Empieza por cómo representas un grafo, de entrada.