Union-Find: unión rápida

Para un conjunto de datos, Union-Find soporta principalmente dos operaciones:

  • union(p,q) - Conectar los elementos p y q.

  • find(p)- Consultar en qué conjunto se encuentra el elemento p.

  • isConnected(p,q)- Verificar si los elementos p y q están conectados entre sí.

En la sección anterior, usamosiduna forma de arreglo para representar Union-Find; en la operación real, la complejidad temporal de la búsqueda esO(1), pero la eficiencia de la unión no es alta.

En esta sección, implementaremos Union-Find de otra manera. Cada elemento se considera un nodo que apunta a su nodo padre, y el nodo raíz se apunta a sí mismo. Como se muestra en la figura, el nodo 3 apunta al nodo 2, lo que significa que 3 y 2 están conectados; el nodo 2 es el nodo raíz, por lo que se apunta a sí mismo.

También usamos un arreglo para representar Union-Find, pero el siguiente grupo de elementos utilizaparentpara representar el nodo padre al que apunta el elemento actual. Cada elemento se apunta a sí mismo, todos son independientes.

Si en este momento se realiza la operaciónunion(4,3), apuntar el elemento 4 al elemento 3:

El arreglo también cambia en consecuencia:

Para determinar si dos elementos están conectados, solo hay que verificar si sus nodos raíz son iguales.

Como se muestra en la figura, los nodos raíz de los nodos 4 y 9 son ambos 8, por lo que están conectados.

Para conectar dos elementos, solo hay que encontrar sus nodos raíz correspondientes y hacer que los nodos raíz se conecten; así serán nodos conectados.

Supongamos que queremos conectar 6 y 4 en la figura anterior; solo necesitamos hacer que el nodo raíz 5 de 6 apunte al nodo raíz 8 de 4.

Para construir esta estructura de árbol que apunta al padre, se usa un arreglo para construir un árbol que apunta al padre; parent[i] representa el nodo padre al que apunta el elemento i.

...
private int[] parent;
private int count;  // Número de elementos
...

Proceso de búsqueda: para encontrar el número de conjunto correspondiente al elemento p, se consulta repetidamente su nodo padre hasta llegar al nodo raíz. La característica del nodo raíz es parent[p] == p. Complejidad O(h), donde h es la altura del árbol.

...
private int find(int p){
    assert( p >= 0 && p < count );
    while( p != parent[p] )
        p = parent[p];
    return p;
}
...

Para fusionar los conjuntos a los que pertenecen los elementos p y q, se consultan los nodos raíz de ambos elementos y se hace que uno de los nodos raíz apunte al otro; así los dos conjuntos se fusionan. Esta operación tiene una complejidad temporal de O(h), donde h es la altura del árbol.

public void unionElements(int p, int q){
    int pRoot = find(p);
    int qRoot = find(q);
    if( pRoot == qRoot )
        return;
    parent[pRoot] = qRoot;
}

Código de ejemplo en Java

Descargar paquete de código fuente:Download

Código del archivo UnionFind2.java:

package ejemplo.union;
/**
* Segunda versión de UnionFind
 */
public class UnionFind2 {
    // Nuestra segunda versión de Union-Find: usa un arreglo para construir un árbol que apunta al padre
    // parent[i] representa el nodo padre al que apunta el primer elemento
    private int[] parent;
    private int count;  // Número de elementos
    // Constructor
    public UnionFind2(int count){
        parent = new int[count];
        this.count = count;
        // Inicialización: cada parent[i] se apunta a sí mismo, lo que indica que cada elemento forma su propio conjunto
        for( int i = 0 ; i < count ; i ++ )
            parent[i] = i;
    }
    // Proceso de búsqueda: obtiene el número de conjunto correspondiente al elemento p
    // Complejidad O(h), h es la altura del árbol
    private int find(int p){
        assert( p >= 0 && p < count );
        // Consulta repetidamente su nodo padre hasta llegar al nodo raíz
        // Característica del nodo raíz: parent[p] == p
        while( p != parent[p] )
            p = parent[p];
        return p;
    }
    // Verifica si los elementos p y q pertenecen al mismo conjunto
    // Complejidad O(h), h es la altura del árbol
    public boolean isConnected( int p , int q ){
        return find(p) == find(q);
    }
    // Fusiona los conjuntos de los elementos p y q
    // Complejidad O(h), h es la altura del árbol
    public void unionElements(int p, int q){
        int pRoot = find(p);
        int qRoot = find(q);
        if( pRoot == qRoot )
            return;
        parent[pRoot] = qRoot;
    }
}
Otras extensiones