Algoritmo Quick Union

Algoritmo Quick Union
Al igual que Quick Find. El algoritmo Quick Union permite conectar nodos de un Árbol entre sí, la diferencia es que en Quick Find las referencias son con el nodo raíz, y Quick Union mantiene una referencia al nodo padre.

Quick Union
El algoritmo se basa en 3 funciones principales, una para encontrar el nodo raíz, otra para unir 2 nodos y una función para verificar si existe conexión entre 2 nodos. Toda la información sobre las conexiones entre nodos se almacenan en un arreglo.

Encontrar el nodo raíz
Para encontrar el nodo raíz basta con recorrer el arreglo dentro de un ciclo hasta que el valor del arreglo[i] sea igual al índice, lo cual quiere decir que alcanzamos la raíz, el algoritmo es de complejidad O(n) donde n = longitud necesaria para alcanzar la raíz, en pseudocódigo:

def find_root(int []array, int node):
    i = node
    while(array[i] != i):
        i = array[i]
    return i

Unir 2 nodos
Para unir 2 nodos "a y b" hay que establecer el nodo raíz de "b" en "a", es decir, hacer algo como:

def union(int []array, int node1, int node2):
    array[find_root(node1)] = find_root(node2)

Saber si 2 nodos están conectados
Sería verificar si los nodos tienen la misma raíz, la complejidad es O(n) al igual que la unión:

def connected(int []array, int node1, int node2):
    find_root(a) == find_root(b)

Imagen tomada del video del curso en Coursera, el copyright es de sus respectivos autores.

En la imagen de arriba todos los nodos están conectados entre sí porque tienen el mismo nodo raíz (Nodo 8). Como ejemplo tenemos a los nodos 2 y 9 podemos verificar su conexión siguiendo el camino hasta el nodo raíz, de la siguiente forma:
id[2] == 1 (Nodo padre del 2)
id[1] == 8 (Nodo padre del 1)
entonces la raíz del nodo 2 es 8.
En cuanto el nodo 9:
id[9] == 8 (Padre y raíz del nodo 9). Como ambos nodos comparten la misma raíz, están conectados. De igual forma se puede apreciar como las flechas indican el recorrido para obtener el nodo raíz.

Mejorando, Quick Union con Peso (Weighted Quick Union)
Se puede optimizar el algoritmo Quick Union añadiendo un arreglo extra que contenga el “peso” de cada nodo (los nodos conectados a él) y al momento de realizar la unión, basta con añadir el nodo con el menor peso al nodo de mayor peso. Lo que se busca es mantener los nodos lo más cercano a la raíz, de manera tal que podamos alcanzarla en el menor número de pasos posibles.

Imagen tomada del video del curso en Coursera, el copyright es de sus respectivos autores.

En la imagen podemos ver la diferencia entre Quick Union y Weighted Quick Union, en el segundo caso podemos alcanzar el nodo raíz en un menor número de pasos que en el primero, lo cual optimiza en gran medida el algoritmo.

¿Mejorando aún más?

En el curso muestran una forma de volver a mejorar el algoritmo con apenas una línea de código!. La idea es que al buscar el nodo raíz, en el ciclo, hacer que cada nodo apunte a su nodo “abuelo”.  De esta manera mantendremos cada nodo mucho más cerca del nodo raíz, por lo que encontrar dicho nodo es mucho más rápido. En el código de find_root sería añadir lo siguiente:

def find_root(int []array, int node):
    i = node
    while(array[i] != i):
        array[i] = array[array[i]] #Nuevo: El nodo apunta a su nodo abuelo
        index = array[i]
    return i

Al final la mejora es tremenda de O(n) a O(log n) y todo con apenas unas líneas de código, de verdad muy interesante. Dejo mi implementación del algoritmo Weighted Quick Union con compresión en Github, que como mi anterior intento es muy parecido a la versión Java del curso, pero que imprime el arreglo y el índice para ver mejor el resultado.

Referencias:
Algorithms, Part I
https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf