¿Qué operaciones se pueden realizar en conjuntos disjuntos?

Question

Acabo de estudiar la estructura de datos set disjuntos y sé que también se llama "union-find data structures", la unión y find son dos operaciones principales de esta estructura de datos. Podemos realizar la unión en conjuntos disjuntos, del mismo modo podemos realizar operaciones de búsqueda; Quiero saber qué otras operaciones podemos realizar en conjuntos disjuntos excepto union y find.

Answer 1

La estructura de conjuntos disjuntos también se denomina "estructura union-find". Por lo tanto, las operaciones union, find y MakeSet deben ser compatibles de todos modos. Otras operaciones no son de lo que se trata esta estructura, y si son compatibles depende de la implementación y los objetivos que tenga. A veces tendrá que elegir una implementación particular específicamente para adaptarse a las necesidades de su proyecto de opertaciones adicionales.

Aparte de eso, sería bueno si admitiéramos las otras operaciones básicas relacionadas con el conjunto. Vamos a enumerarlos:

• intersección de dos conjuntos. Como los conjuntos son disjuntos, siempre están vacíos a menos que estos dos conjuntos coincidan.
• unión de dos juegos - compatible con la caja.
• obtener un elemento del conjunto - compatible, es muy probable el resultado de find.
• eliminar un elemento del conjunto - depende de la implementación. Cuando los conjuntos se implementan como bosques, es complicado y requiere operaciones adicionales más lentas. Cuando los conjuntos se implementan como listas vinculadas, es simple.
• enumere el conjunto, es decir, itere cada elemento en el conjunto dado. Depende de la implementación de nuevo: para las listas vinculadas es simple, para la implementación de tipo bosque requiere estructuras adicionales para soportar.

Answer 2

Con la estructura de datos vainilla union-find, no puede enumerar el conjunto real, por lo que muchas de las operaciones establecidas no están disponibles. Esto se debe a que en la versión estándar solo tienes punteros en una dirección --- en la imagen siguiente, cada línea diagonal corresponde a una flecha hacia arriba, y las raíces (línea superior) son los objetos raíz para los conjuntos:

 o [set1]   o [Set2] 
    /\    \ 
    o o    o 
/
o 

Así que no hay forma de encontrar todos los objetos de, digamos, el conjunto 1; por ejemplo, no puede rastrear rutas desde el nodo raíz. También podría tener punteros hacia abajo, pero esto complica la estructura de datos significativamente porque un objeto puede tener un número arbitrario de padres en la estructura de datos.

Así que es realmente todo para las siguientes operaciones:

• respuesta a: ¿Mis objetos A y B pertenecen al mismo conjunto o no?
• Combinar establece S1 y S2 de manera que todos los objetos en los juegos de ahora se consideran que pertenecen a la misma serie

Elaborar esto, la estructura de datos de la Unión-set tiene tiempo complejidad muy baja para las operaciones que apoya ; tanto la combinación de conjuntos como la respuesta del mismo conjunto toman tiempo constante amortizado (O (1)); debido a esta misma complejidad de tiempo, no puede admitir todas las operaciones establecidas.Por ejemplo, una representación de conjunto estándar es por un árbol de búsqueda [binario], donde la mayoría de las operaciones tienen complejidades O (log n) al menos.

Answer 3

El objetivo de la estructura de conjuntos disjuntos union-find no se trata tanto de realizar operaciones de conjuntos elementales, como su pregunta y otros encuestados parecen sugerir. En cambio, se trata de ser una implementación altamente eficiente de la estructura que necesitan ciertos algoritmos. En particular, la búsqueda de componentes conectados y árboles de expansión mínima crea sus implementaciones más eficientes además de los conjuntos disjuntos de unión.