Union-Find

El algoritmo de Kruskal para encontrar el árbol cobertor mínimo de un grafo crea una cola de prioridad con todas las aristas y parte con un bosque $T=\emptyset$ (visto como conjunto de aristas). Luego va tomando cada arista, y si no forma ciclo en el bosque, la agrega a $T$, terminando cuando $|T|=n-1$ y el bosque se ha convertido en un árbol. En un grafo conexo de $n$ nodos y $n-1 \le e \le n^2$ aristas, el algoritmo tiene un peor caso de $O(e\log e)=O(e\log n)$ para manejar la cola de prioridad. Sin embargo, en esta formulación no queda claro cómo determinar si una arista forma ciclo o no.

Si pensamos los árboles de $T$ como clases de equivalencia formadas por nodos, una arista $(u,v)$ forma ciclo sii $u$ y $v$ son nodos del mismo árbol, es decir, están en la misma clase de equivalencia. Cuando no lo están, agregar la arista $(u,v)$ tiene el efecto de unir los dos árboles, es decir, las dos clases de equivalencia. Podemos entonces reexpresar las operaciones que necesitamos como operaciones que manejan clases de equivalencia:

• Partimos con cada uno de los $n$ elementos formando su propia clase.
• Podemos preguntar si dos elementos pertenecen a la misma clase.
• Podemos unir dos clases.

La interfaz que veremos define un elemento de cada clase, en forma arbitraria pero consistente, como su representante. Tenemos entonces las dos operaciones siguientes:

• $Find(v)$ entrega el representante de la clase de equivalencia de $v$.
• $Union(x,y)$ une las clases de equivalencia representadas por $x$ y por $y$.

--> imagen

Dos elementos $u$ y $v$ pertenecen entonces a una misma clase sii $Find(u) = Find(v)$, y para unir las clases de dos elementos cualquiera (no necesariamente representantes de clase) $u$ y $v$ realizamos $Union(Find(u),Find(v))$. Con esta interfaz, el algoritmo de Kruskal realiza $O(e)$ operaciones $Find$ y $O(n)$ operaciones $Union$. Veremos primero una solución de tiempo $O(\log n)$ para estas operaciones y luego una mucho mejor, que requiere análisis amortizado. Con estas soluciones, el costo del algoritmo de Kruskal es $O(e\log n)$, dominado por las operaciones en la cola de prioridad.

📄️ Solución de tiempo $O(\log n)$

Obviando las soluciones muy elementales, que requieren tiempo $O(n)$ para

📄️ Solución de tiempo amortizado $O(\log^* n)$

Cuando se realiza una operación $Find(v)$, se visitan todos los ancestros de