Estructura de datos de conjuntos disjuntos

En informática , una estructura de datos de conjuntos disjuntos , también denominada estructura de datos de unión-búsqueda o conjunto de combinación-búsqueda , es una estructura de datos que almacena una colección de conjuntos disjuntos (no superpuestos). De manera equivalente, almacena una partición de un conjunto en subconjuntos separados. Proporciona operaciones para agregar nuevos conjuntos, fusionar conjuntos (reemplazarlos por su unión ) y encontrar un miembro representativo de un conjunto. La última operación permite averiguar de manera eficiente si dos elementos están en el mismo conjunto o en conjuntos diferentes.

Si bien hay varias formas de implementar estructuras de datos de conjuntos disjuntos, en la práctica a menudo se identifican con una implementación particular llamada bosque de conjuntos disjuntos . Este es un tipo de bosque especializado que realiza uniones y se encuentra en un tiempo amortizado casi constante. Para realizar una secuencia de m operaciones de suma, unión o búsqueda en un bosque de conjuntos disjuntos con n nodos se requiere un tiempo total O ( m α ( n )) , donde α ( n ) es la función de Ackermann inversa de crecimiento extremadamente lento. Los bosques de conjuntos disjuntos no garantizan este rendimiento por operación. Las operaciones de búsqueda y unión individuales pueden tardar más que una constante por tiempo α ( n ) , pero cada operación hace que el bosque de conjuntos disjuntos se ajuste a sí mismo para que las operaciones sucesivas sean más rápidas. Los bosques de conjuntos disjuntos son asintóticamente óptimos y prácticamente eficientes.

Las estructuras de datos de conjuntos disjuntos juegan un papel clave en el algoritmo de Kruskal para encontrar el árbol de expansión mínimo de un gráfico. La importancia de los árboles de expansión mínimos significa que las estructuras de datos de conjuntos disjuntos subyacen a una amplia variedad de algoritmos. Además, las estructuras de datos de conjuntos disjuntos también tienen aplicaciones para el cálculo simbólico, así como en compiladores, especialmente para problemas de asignación de registros .

Bosques disjuntos-set fueron descritos por primera vez por Bernard A. Galler y Michael J. Fischer en 1964. ^[2] En 1973, su complejidad tiempo estaba limitado a , el logaritmo iterado de , por Hopcroft y Ullman . ^[3] En 1975, Robert Tarjan fue el primero en probar el límite superior ( función de Ackermann inversa ) en la complejidad temporal del algoritmo, ^[4] y, en 1979, mostró que este era el límite inferior para un caso restringido. ^[5] En 1989, Fredman y Saks demostraron que${\ Displaystyle O (\ log ^ {*} (n))}$${\ Displaystyle n}$${\ Displaystyle O (m \ alpha (n))}$${\ Displaystyle \ Omega (\ alpha (n))}$Las palabras (amortizadas) deben ser accedidas por cualquier estructura de datos de conjuntos disjuntos por operación, ^[6] probando así la optimalidad de la estructura de datos.

En 1994, Richard J. Anderson y Heather Woll describieron una versión paralelizada de Union – Find que nunca necesita bloquearse. ^[8]

En 2007, Sylvain Conchon y Jean-Christophe Filliâtre desarrollaron una versión persistente de la estructura de datos del bosque disjunto, lo que permitió retener de manera eficiente versiones anteriores de la estructura y formalizaron su corrección utilizando el asistente de pruebas Coq . ^[9] Sin embargo, la implementación solo es asintótica si se usa de manera efímera o si la misma versión de la estructura se usa repetidamente con un retroceso limitado.

MakeSet crea 8 singletons.

Después de algunas operaciones de Union, algunos conjuntos se agrupan.

Prueba de hallazgo de unión${\ Displaystyle O (\ log ^ {*} n)}$

Una demostración de Union-Find cuando se usa el algoritmo de Kruskal para encontrar el árbol de expansión mínimo.