Union-Find

Categoría: Graphs

El problema

"¿Estas dos cosas están conectadas, directa o transitivamente, dado todo lo que he enlazado hasta ahora?" surge todo el tiempo — y surge de forma incremental, un nuevo enlace descubierto a la vez, no como un grafo completo entregado de una sola vez. Volver a ejecutar un recorrido completo del grafo (BFS/DFS) desde cero en cada nuevo enlace para responder una sola pregunta de conectividad es correcto, pero derrochador: la mayor parte del grafo no ha cambiado entre un enlace y el siguiente.

La solución

Rastrea conjuntos disjuntos en lugar de un grafo completo. Cada conjunto es un árbol; cada elemento apunta a un padre, y la raíz de un árbol es el representante canónico de ese conjunto. find sube hasta la raíz; union fusiona dos conjuntos haciendo que una raíz apunte a la otra; connected es simplemente "¿estos dos elementos tienen la misma raíz?". Nada de esto necesita almacenar aristas — solo punteros al padre — que es lo que hace que union y connected sean tan baratos comparados con mantener y volver a recorrer un grafo explícito.

Esa versión simple tiene una debilidad real: nada impide que un árbol crezca en altura. Una secuencia de uniones que siempre adjunta el elemento más nuevo a la misma cadena creciente — union(0,1), union(1,2), union(2,3), ... — produce una línea recta, y find en el extremo lejano tiene que recorrer cada salto. Dos correcciones independientes y combinables cierran esa brecha:

• Compresión de caminos — mientras find sube hasta la raíz, redirige cada nodo por el que pasa directamente a esa raíz. La siguiente búsqueda de cualquiera de esos nodos es entonces un único salto.
• Unión por rango — union siempre adjunta el árbol más bajo bajo la raíz del árbol más alto, en lugar de adjuntar arbitrariamente, lo que evita que los árboles crezcan en altura desde el principio.

Combinadas, el costo amortizado por operación está acotado por la función de Ackermann inversa — efectivamente una constante pequeña para cualquier tamaño de entrada que pudiera existir en la práctica.

flowchart TB
    subgraph Naive["naive: sequential unions, no fixes"]
        direction TB
        n0["0"] --> n1["1"] --> n2["2"] --> n3["3"] --> n4["4"]
    end
    subgraph Optimized["optimized: same unions, path compression + union by rank"]
        direction TB
        r["0 (root)"]
        r --> o1["1"]
        r --> o2["2"]
        r --> o3["3"]
        r --> o4["4"]
    end

Ejemplo clásico

classic/NaiveUnionFind es la estructura de libro de texto sin ninguna de las dos optimizaciones: union siempre adjunta la raíz del primer argumento directamente bajo la del segundo, sin considerar la altura del árbol. classic/UnionFind añade tanto compresión de caminos (en find) como unión por rango (en union) sobre exactamente la misma API. NaiveUnionFindTest y UnionFindTest ejercitan ambas una cadena de uniones secuenciales — el peor caso de la versión ingenua —, con la prueba optimizada recorriendo además cada rama de la unión por rango (rango menor se adjunta bajo rango mayor, rangos iguales eligen una raíz y la incrementan, un par ya unido es una operación sin efecto) y la compresión de caminos de find en un árbol de múltiples saltos.

Ejemplo aplicado: detección de clústeres de fraude

applied/FraudRingDetector une incrementalmente cuentas y las señales identificadoras con las que han sido observadas — una huella digital de dispositivo, un número de teléfono — a medida que esos enlaces se descubren en tiempo real, sin necesidad de recomputación por lotes. Responder "¿estas dos cuentas forman parte del mismo anillo de fraude?" es entonces una única verificación connected, incluso cuando las dos cuentas nunca compartieron una señal directamente y solo están enlazadas transitivamente a través de varias cuentas/dispositivos intermedios. FraudRingDetectorTest cubre enlace directo y transitivo, dos clústeres genuinamente separados, un identificador desconocido en cualquiera de los lados de la verificación, y el exceso de la capacidad de entidades configurada del detector.

Benchmark

./gradlew :graphs:union-find:jmh

Ejecución real (JMH 1.37, JDK 26.0.2, 2 iteraciones de calentamiento + 3 iteraciones de medición, 1 fork). Ambas estructuras se someten exactamente a la misma secuencia de uniones de peor caso — union(0,1), union(1,2), union(2,3), ... — y luego se mide find sobre el mismo elemento del medio:

El costo de la versión ingenua aumenta con el tamaño — aproximadamente el crecimiento que predice un recorrido de cadena O(n), cerca de 58x más lenta en tamaño=10,000 que en tamaño=100. La versión optimizada apenas se mueve a lo largo de ese mismo incremento de tamaño de 100x (2.47ns a 2.79ns, ~13% — dentro del ruido de medición/JIT): el find de un único elemento en este benchmark alcanza su peor punto (un camino de 2-3 saltos) ya en la primera llamada y se mantiene efectivamente estable después de eso, ya que la unión por rango por sí sola mantuvo poco profundo el árbol en esta exacta secuencia adversarial de uniones, y la compresión de caminos aplana cualquier profundidad restante. En tamaño=10,000 la estructura ingenua es más de 3,000x más lenta que la optimizada para la operación idéntica, en la misma secuencia de entrada idéntica — esa brecha es la razón por la que existen ambas optimizaciones clásicas de union-find.

Cuándo no usarlo

• ¿Necesitas enumerar qué elementos hay en un conjunto, o iterar sobre los miembros de un conjunto? Union-find solo responde "¿mismo conjunto o no?" — no tiene noción del contenido ni del tamaño de un conjunto más allá de eso, por diseño.
• ¿Necesitas deshacer una unión (dividir un conjunto de vuelta)? La compresión de caminos y la unión por rango hacen que la estructura del árbol pierda información sobre el orden original de las uniones — esta estructura está construida para fusión en una sola dirección, no para eliminación o rollback.
• ¿Tienes el grafo completo de antemano y necesitas caminos más cortos reales u orden de recorrido, no solo conectividad? Un recorrido de grafo real (BFS/DFS, o el módulo Dijkstra de este repositorio) es la herramienta correcta — union-find descarta deliberadamente la información de aristas para mantenerse tan barato.

Cobertura de pruebas

100% de cobertura de instrucciones, 100% de cobertura de ramas (JaCoCo). Reprodúcelo tú mismo:

./gradlew :graphs:union-find:jacocoTestReport

Informe en graphs/union-find/build/reports/jacoco/test/html/index.html.

Pruebas unitarias

package com.datastructures.graphs.unionfind.classic;

import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;

class NaiveUnionFindTest {

    @Test
    void everyElementStartsInItsOwnSet() {
        NaiveUnionFind uf = new NaiveUnionFind(4);

        for (int i = 0; i < 4; i++) {
            assertThat(uf.find(i)).isEqualTo(i);
        }
        assertThat(uf.connected(0, 1)).isFalse();
        assertThat(uf.size()).isEqualTo(4);
    }

    @Test
    void unionMergesTwoSets() {
        NaiveUnionFind uf = new NaiveUnionFind(3);

        uf.union(0, 1);

        assertThat(uf.connected(0, 1)).isTrue();
        assertThat(uf.connected(0, 2)).isFalse();
    }

    @Test
    void unioningTwoElementsAlreadyInTheSameSetIsANoOp() {
        NaiveUnionFind uf = new NaiveUnionFind(2);
        uf.union(0, 1);

        uf.union(0, 1);

        assertThat(uf.connected(0, 1)).isTrue();
    }

    /**
     * Sequential unions (0-1, 1-2, 2-3, 3-4) build the naive structure's worst case: a straight
     * chain with no path compression to flatten it. find(0) has to walk every hop to the root.
     */
    @Test
    void findWalksTheFullChainAfterASequenceOfUnions() {
        NaiveUnionFind uf = new NaiveUnionFind(5);
        uf.union(0, 1);
        uf.union(1, 2);
        uf.union(2, 3);
        uf.union(3, 4);

        assertThat(uf.find(0)).isEqualTo(uf.find(4));
        assertThat(uf.connected(0, 4)).isTrue();
    }
}

package com.datastructures.graphs.unionfind.classic;

import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;

class UnionFindTest {

    @Test
    void everyElementStartsInItsOwnSet() {
        UnionFind uf = new UnionFind(4);

        for (int i = 0; i < 4; i++) {
            assertThat(uf.find(i)).isEqualTo(i);
        }
        assertThat(uf.connected(0, 1)).isFalse();
        assertThat(uf.size()).isEqualTo(4);
    }

    /**
     * Exercises all three branches of union-by-rank in sequence:
     * <ol>
     *   <li>union(0,1), union(2,3): equal ranks (0 vs 0), so the second argument's root wins
     *       arbitrarily and its rank increments.</li>
     *   <li>union(4,0): rank[4]=0 &lt; rank[0]=1, so the lower-rank root (4) attaches under 0.</li>
     *   <li>union(0,2): rank[0]=1 == rank[2]=1, equal-rank case again, rank[0] becomes 2.</li>
     *   <li>union(0,5): rank[0]=2 &gt; rank[5]=0, so the lower-rank root (5) attaches under 0.</li>
     *   <li>union(1,3): 1 and 3 are already in the same set by this point (both under root 0),
     *       so this is the no-op branch.</li>
     * </ol>
     */
    @Test
    void unionByRankAttachesTheLowerRankTreeUnderTheHigherRankRootInEveryCase() {
        UnionFind uf = new UnionFind(7);

        uf.union(0, 1); // equal ranks (0,0) -> parent[1]=0, rank[0]=1
        uf.union(2, 3); // equal ranks (0,0) -> parent[3]=2, rank[2]=1
        uf.union(4, 0); // rank[4]=0 < rank[0]=1 -> parent[4]=0
        uf.union(0, 2); // rank[0]=1 == rank[2]=1 -> parent[2]=0, rank[0]=2
        uf.union(0, 5); // rank[0]=2 > rank[5]=0 -> parent[5]=0
        uf.union(1, 3); // 1 and 3 already share root 0 -> no-op

        assertThat(uf.connected(4, 5)).isTrue();
        assertThat(uf.connected(1, 3)).isTrue();
        assertThat(uf.connected(0, 6)).isFalse();
    }

    /**
     * Builds a tree three levels deep (3 -> 2 -> 0) so find(3) has to both walk a multi-hop
     * path to the root and then compress it, while find(0) (already the root) exercises the
     * zero-iteration path for both of find's internal loops.
     */
    @Test
    void findCompressesAMultiHopPathAndLeavesAnAlreadyDirectPathUntouched() {
        UnionFind uf = new UnionFind(4);
        uf.union(0, 1); // parent[1]=0, rank[0]=1
        uf.union(2, 3); // parent[3]=2, rank[2]=1
        uf.union(0, 2); // equal ranks -> parent[2]=0, rank[0]=2; now 3 -> 2 -> 0 (depth 2)

        assertThat(uf.find(3)).isEqualTo(0);
        assertThat(uf.find(0)).isEqualTo(0);
        assertThat(uf.connected(1, 3)).isTrue();
    }
}

package com.datastructures.graphs.unionfind.applied;

import org.junit.jupiter.api.Test;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class FraudRingDetectorTest {

    @Test
    void entitiesLinkedDirectlyOrTransitivelyLandInTheSameCluster() {
        FraudRingDetector detector = new FraudRingDetector(10);
        detector.linkObservedTogether("account-1", "device-A");
        detector.linkObservedTogether("device-A", "account-2");
        // account-2 was already assigned an index above: reuses it (existing-entity branch).
        detector.linkObservedTogether("account-2", "phone-555");

        assertThat(detector.sameFraudCluster("account-1", "account-2")).isTrue();
        assertThat(detector.sameFraudCluster("account-1", "phone-555")).isTrue();
    }

    @Test
    void entitiesInDifferentClustersAreNotTreatedAsLinked() {
        FraudRingDetector detector = new FraudRingDetector(10);
        detector.linkObservedTogether("account-1", "device-A");
        detector.linkObservedTogether("account-2", "device-B");

        assertThat(detector.sameFraudCluster("account-1", "account-2")).isFalse();
    }

    @Test
    void anUnknownIdentifierOnEitherSideCanNeverShareACluster() {
        FraudRingDetector detector = new FraudRingDetector(10);
        detector.linkObservedTogether("account-1", "device-A");

        assertThat(detector.sameFraudCluster("ghost", "account-1")).isFalse();
        assertThat(detector.sameFraudCluster("account-1", "ghost")).isFalse();
    }

    @Test
    void exceedingTheConfiguredEntityCapacityThrows() {
        FraudRingDetector detector = new FraudRingDetector(2);
        detector.linkObservedTogether("account-1", "device-A"); // uses both available slots

        assertThatThrownBy(() -> detector.linkObservedTogether("account-2", "device-B"))
                .isInstanceOf(IllegalStateException.class)
                .hasMessageContaining("capacity");
    }
}

Ver informe completo de cobertura JaCoCo →