Sistema de conjuntos disjuntos

El sistema de conjunto disjunto ( eng.  disjoint-set , o estructura de datos union-find ) es una estructura de datos que le permite administrar un conjunto de elementos, divididos en subconjuntos disjuntos. En este caso, a cada subconjunto se le asigna su representante, un elemento de este subconjunto. Una estructura de datos abstracta se define mediante un conjunto de tres operaciones: .

Se utiliza para almacenar componentes conectados en gráficos , en particular, el algoritmo de Kruskal necesita una estructura de datos similar para una implementación eficiente.

Definición

Sea un conjunto finito dividido en subconjuntos ( clases ) que no se intersecan :

A cada subconjunto se le asigna un representante . El correspondiente sistema de conjuntos disjuntos soporta las siguientes operaciones:

• : crea un nuevo subconjunto para el elemento. Designa el mismo elemento como representante del subconjunto creado.
• : combina ambos subconjuntos pertenecientes a representantes y , y designa al representante del nuevo subconjunto.
• : Especifica para el subconjunto al que pertenece el elemento y devuelve su representante.

Implementación algorítmica

Una implementación trivial almacena la propiedad de los elementos de y los representantes en una matriz de índice . En la práctica, se utilizan con mayor frecuencia conjuntos de árboles . Esto puede reducir significativamente el tiempo requerido para la operación de búsqueda . En este caso, el representante se escribe en la raíz del árbol y los elementos restantes de la clase se escriben en los nodos debajo de él.

• : cuelga la raíz de un árbol más bajo debajo de la raíz de un árbol más alto. Si esto se convierte en un elemento secundario de , ambos nodos se intercambian.
• : toma el camino desde la raíz del árbol y lo devuelve (la raíz en este caso es un representante).

Heurística

Las heurísticas Union-By-Size , Union-By-Height , Random-Union y la compresión de rutas se pueden utilizar para acelerar las operaciones de unión y búsqueda .

En la heurística Union-By-Size , durante la operación, la raíz del árbol más pequeño se cuelga debajo de la raíz del árbol más grande. Este enfoque preserva el equilibrio del árbol. La profundidad de cada subárbol no puede exceder . Con esta heurística, el tiempo de operación de búsqueda en el peor de los casos aumenta de a . Para una implementación eficiente, se propone almacenar el número de nodos del árbol en la raíz.

La heurística Union-By-Height es similar a Union-By-Size , pero usa la altura del árbol en lugar del tamaño.

La heurística Random-Union utiliza el hecho de que es posible no gastar memoria adicional para guardar la cantidad de nodos en el árbol: es suficiente elegir la raíz aleatoriamente; esta solución brinda una velocidad en las consultas aleatorias que es bastante comparable a otras implementaciones. Sin embargo, si hay muchas consultas como "combinar un conjunto grande con uno pequeño", esta heurística mejora el valor esperado (es decir, el tiempo de ejecución promedio) solo por un factor de dos, por lo que no se recomienda usarla sin la heurística de compresión de caminos.

La heurística de compresión de ruta se utiliza para acelerar la operación . Con cada nueva búsqueda, todos los elementos que están en el camino desde la raíz hasta el elemento deseado se cuelgan debajo de la raíz del árbol. En este caso, la operación de búsqueda funcionará en promedio , donde  es la función inversa de la función de Ackerman . Esto le permite acelerar significativamente el trabajo, ya que para todos los valores utilizados en la práctica, toma un valor inferior a 5.

Ejemplo de implementación

Implementación en C++: