Estructura de datos de conjuntos disjuntos

En informática , una estructura de datos de conjuntos disjuntos , también llamada estructura de datos de unión-búsqueda o conjunto de fusió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 disjuntos . 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 saber de manera eficiente si dos elementos cualesquiera están en conjuntos iguales o diferentes.

Si bien existen 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 . Se trata de un tipo especializado de bosque que realiza uniones y 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 conjunto disjunto 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 individuales de unión y búsqueda pueden tardar más que un tiempo constante multiplicado por $α(n)$ , pero cada operación hace que el bosque de conjuntos disjuntos se ajuste 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 desempeñan 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ínima 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 en el cálculo simbólico, así como en compiladores, especialmente para problemas de asignación de registros .

Historia

Los bosques de conjuntos disjuntos fueron descritos por primera vez por Bernard A. Galler y Michael J. Fischer en 1964. ^{[2] En 1973,}Hopcroft y Ullman limitaron su complejidad temporal a , el logaritmo iterado de . ^[3] En 1975, Robert Tarjan fue el primero en demostrar el límite superior ( función de Ackermann inversa ) de la complejidad temporal del algoritmo. ^[4] También demostró que era ajustado. En 1979, demostró que este era el límite inferior para una determinada clase de algoritmos, que incluyen la estructura de Galler-Fischer. ^[5] En 1989, Fredman y Saks demostraron que cualquier estructura de datos de conjunto disjunto debe acceder a palabras (amortizadas) de bits por operación, ^[6] demostrando así la optimización de la estructura de datos en este modelo. $O(\log ^{*}(n))$ $n$ $O(m\alpha (n))$ $\Omega (\alpha (n))$ $O(\log n)$

En 1991, Galil e Italiano publicaron un estudio sobre estructuras de datos para conjuntos disjuntos. ^[7]

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 semipersistente de la estructura de datos forestales de conjuntos disjuntos y formalizaron su corrección utilizando el asistente de prueba Coq . ^[9] "Semipersistente" significa que las versiones anteriores de la estructura se conservan de manera eficiente, pero el acceso a las versiones anteriores de la estructura de datos invalida las posteriores. Su implementación más rápida logra un rendimiento casi tan eficiente como el algoritmo no persistente. No realizan un análisis de complejidad.

También se han considerado variantes de estructuras de datos de conjuntos disjuntos con mejor rendimiento en una clase restringida de problemas. Gabow y Tarjan demostraron que si las uniones posibles se restringen de ciertas maneras, entonces es posible un algoritmo de tiempo verdaderamente lineal. ^[10]

Representación

Cada nodo en un bosque de conjunto disjunto consta de un puntero y cierta información auxiliar, ya sea un tamaño o un rango (pero no ambos). Los punteros se utilizan para crear árboles de punteros principales , donde cada nodo que no es la raíz de un árbol apunta a su padre. Para distinguir los nodos raíz de otros, sus punteros principales tienen valores no válidos, como una referencia circular al nodo o un valor centinela. Cada árbol representa un conjunto almacenado en el bosque, siendo los miembros del conjunto los nodos del árbol. Los nodos raíz proporcionan representantes de conjuntos: dos nodos están en el mismo conjunto si y sólo si las raíces de los árboles que contienen los nodos son iguales.

Los nodos del bosque se pueden almacenar de cualquier forma que convenga a la aplicación, pero una técnica común es almacenarlos en una matriz. En este caso, los padres pueden indicarse mediante su índice de matriz. Cada entrada de la matriz requiere $Θ(log n)$ bits de almacenamiento para el puntero principal. Se requiere una cantidad de almacenamiento comparable o menor para el resto de la entrada, por lo que la cantidad de bits necesarios para almacenar el bosque es $Θ(n log n)$ . Si una implementación utiliza nodos de tamaño fijo (lo que limita el tamaño máximo del bosque que se puede almacenar), entonces el almacenamiento necesario es lineal en $n$ .

Operaciones

Las estructuras de datos de conjuntos disjuntos admiten tres operaciones: crear un nuevo conjunto que contenga un nuevo elemento; Encontrar el representante del conjunto que contiene un elemento determinado; y Fusionar dos conjuntos.

haciendo nuevos conjuntos

La MakeSetoperación agrega un nuevo elemento a un nuevo conjunto que contiene solo el nuevo elemento y el nuevo conjunto se agrega a la estructura de datos. Si, en cambio, la estructura de datos se ve como una partición de un conjunto, entonces la MakeSetoperación amplía el conjunto agregando el nuevo elemento y extiende la partición existente colocando el nuevo elemento en un nuevo subconjunto que contiene solo el nuevo elemento.

En un bosque de conjunto disjunto, MakeSetinicializa el puntero principal del nodo y el tamaño o rango del nodo. Si una raíz está representada por un nodo que apunta a sí mismo, entonces la adición de un elemento se puede describir utilizando el siguiente pseudocódigo:

La función MakeSet( x ) es  si  x aún no está en el bosque, entonces  x .parent := x  x .size := 1 // si los nodos almacenan el tamaño  x .rank := 0 // si los nodos almacenan el rango  final si finaliza la función

Esta operación tiene una complejidad de tiempo constante. En particular, inicializar un bosque de conjunto disjunto con $n$ nodos requiere $O (n)$ tiempo.

La falta de un padre asignado al nodo implica que el nodo no está presente en el bosque.

En la práctica, MakeSetdebe ir precedido de una operación que asigne memoria para contener $x$ . Siempre que la asignación de memoria sea una operación amortizada de tiempo constante, como lo es para una buena implementación de matriz dinámica , no cambia el rendimiento asintótico del bosque de conjunto aleatorio.

Encontrar representantes de conjuntos

La Findoperación sigue la cadena de punteros principales desde un nodo de consulta especificado $x$ hasta que llega a un elemento raíz. Este elemento raíz representa el conjunto al que pertenece $x$ y puede ser el propio $x$ . Finddevuelve el elemento raíz que alcanza.

Realizar una Findoperación presenta una oportunidad importante para mejorar el bosque. El tiempo de una Findoperación se dedica a perseguir los punteros principales, por lo que un árbol más plano conduce a Findoperaciones más rápidas. Cuando Findse ejecuta a, no hay forma más rápida de llegar a la raíz que siguiendo cada puntero principal en sucesión. Sin embargo, los punteros principales visitados durante esta búsqueda se pueden actualizar para que apunten más cerca de la raíz. Debido a que cada elemento visitado en el camino hacia una raíz es parte del mismo conjunto, esto no cambia los conjuntos almacenados en el bosque. Pero hace que Findlas operaciones futuras sean más rápidas, no sólo para los nodos entre el nodo de consulta y la raíz, sino también para sus descendientes. Esta actualización es una parte importante de la garantía de desempeño amortizado del bosque de conjunto disjunto.

Existen varios algoritmos para Findlograr la complejidad temporal asintóticamente óptima. Una familia de algoritmos, conocida como compresión de ruta , hace que cada nodo entre el nodo de consulta y la raíz apunte a la raíz. La compresión de rutas se puede implementar mediante una recursividad simple de la siguiente manera:

la función Buscar ( x ) es  si  x .parent ≠ x  entonces  x .parent: = Buscar ( x .parent) devolver  x .parent en caso contrario  devolver  x  final si finaliza la función

Esta implementación realiza dos pasadas, una hacia arriba del árbol y otra hacia abajo. Requiere suficiente memoria temporal para almacenar la ruta desde el nodo de consulta hasta la raíz (en el pseudocódigo anterior, la ruta se representa implícitamente mediante la pila de llamadas). Esto se puede reducir a una cantidad constante de memoria realizando ambos pases en la misma dirección. La implementación de memoria constante camina desde el nodo de consulta hasta la raíz dos veces, una para encontrar la raíz y otra para actualizar los punteros:

la función Buscar ( x ) es  raíz  : = x  mientras que  raíz .parent ≠ raíz  hacer  raíz  : = raíz .parent terminar mientras mientras  x .parent ≠ raíz  hacer  padre  := x .parent x .parent := raíz  x  := padre  terminar mientras  función final de retorno de raíz

Tarjan y Van Leeuwen también desarrollaron algoritmos de un solo paso Findque conservan la misma complejidad en el peor de los casos pero son más eficientes en la práctica. ^[4] Estos se denominan división de ruta y reducción a la mitad de ruta. Ambos actualizan los punteros principales de los nodos en la ruta entre el nodo de consulta y la raíz. La división de ruta reemplaza cada puntero principal en esa ruta por un puntero al abuelo del nodo:

la función Buscar ( x ) es  mientras  x .parent ≠ x  hacer ( x , x .parent): = ( x .parent, x .parent.parent) finaliza mientras  regresa  x finaliza la función

La reducción a la mitad de la ruta funciona de manera similar, pero solo reemplaza todos los demás punteros principales:

la función Buscar ( x ) es  mientras  x .parent ≠ x  hacer  x .parent := x .parent.parent x  := x .parent terminar mientras  regresar  x finalizar la función

Fusionando dos conjuntos

MakeSetcrea 8 singletons.

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

La operación reemplaza el conjunto que contiene $x$ y el conjunto que contiene $y$ con su unión. primeros usos para determinar las raíces de los árboles que contienen $x$ e $y$ . Si las raíces son iguales, no hay nada más que hacer. De lo contrario, los dos árboles deberán fusionarse. Esto se hace estableciendo el puntero principal de la raíz de $x en$ $y$ , o estableciendo el puntero principal de la raíz de $y en$ $x$ .Union(x, y)UnionFind

La elección de qué nodo se convierte en padre tiene consecuencias para la complejidad de futuras operaciones en el árbol. Si se hace sin cuidado, los árboles pueden llegar a ser excesivamente altos. Por ejemplo, supongamos que eso Unionsiempre convierte al árbol que contiene $x$ en un subárbol del árbol que contiene $y$ . Comience con un bosque que acaba de inicializarse con elementos y ejecute , , ..., . El bosque resultante contiene un único árbol cuya raíz es $n$ y el camino de 1 a $n$ pasa por todos los nodos del árbol. Para este bosque, el tiempo de ejecución es $O$ $($ $n$ $)$ . $1,2,3,\ldots,n,$ $Union(1, 2)$ $Union(2, 3)$ $Union(n - 1, n)$ Find(1)

En una implementación eficiente, la altura del árbol se controla mediante unión por tamaño o unión por rango . Ambos requieren un nodo para almacenar información además de su puntero principal. Esta información se utiliza para decidir qué raíz se convierte en el nuevo padre. Ambas estrategias aseguran que los árboles no crezcan demasiado.

Unión por tamaño

En el caso de la unión por tamaño, un nodo almacena su tamaño, que es simplemente su número de descendientes (incluido el propio nodo). Cuando los árboles con raíces xey $se$ $fusionan$ , el nodo con más descendientes se convierte en el padre. Si los dos nodos tienen el mismo número de descendientes, cualquiera de ellos puede convertirse en padre. En ambos casos, el tamaño del nuevo nodo padre se establece en su nuevo número total de descendientes.

función Unión( x , y ) es  // Reemplazar nodos por raíces  x  := Buscar( x ) y  := Buscar( y ) si  x = y  entonces  regresa  // x e y ya están en el mismo conjunto  final si // Si es necesario, intercambie variables para garantizar que  // x tenga al menos tantos descendientes como y  si  x .size < y .size entonces ( x , y ) := ( y , x ) end if // Hacer de x la nueva raíz  y .parent := x  // Actualizar el tamaño de x  x .size := x .size + y .size función final

La cantidad de bits necesarios para almacenar el tamaño es claramente la cantidad de bits necesarios para almacenar $n$ . Esto añade un factor constante al almacenamiento requerido por el bosque.

Unión por rango

Para la unión por rango, un nodo almacena su rango , que es un límite superior para su altura. Cuando se inicializa un nodo, su rango se establece en cero. Para fusionar árboles con raíces $x$ e $y$ , primero compare sus clasificaciones. Si los rangos son diferentes, entonces el árbol de rangos más grande se convierte en el padre y los rangos de xey $no$ cambian $.$ Si los rangos son los mismos, cualquiera de los dos puede convertirse en padre, pero el rango del nuevo padre se incrementa en uno. Si bien el rango de un nodo está claramente relacionado con su altura, almacenar rangos es más eficiente que almacenar alturas. La altura de un nodo puede cambiar durante una Findoperación, por lo que almacenar rangos evita el esfuerzo adicional de mantener la altura correcta. En pseudocódigo, la unión por rango es:

función Unión( x , y ) es  // Reemplazar nodos por raíces  x  := Buscar( x ) y  := Buscar( y ) si  x = y  entonces  regresa  // x e y ya están en el mismo conjunto  final si // Si es necesario, cambie el nombre de las variables para garantizar que  // x tenga un rango al menos tan grande como el de y  if  x .rank < y .rank entonces ( x , y ) := ( y , x ) end if // Hacer de x la nueva raíz  y .parent := x  // Si es necesario, incrementar el rango de x  si  x .rank = y .rank entonces  x .rank := x .rank + 1 fin si finaliza la función

Se puede demostrar que cada nodo tiene rango o menos. ^[11] En consecuencia, cada rango se puede almacenar en $O$ $(log log$ $n$ $)$ bits y todos los rangos se pueden almacenar en $O$ $($ $n$ $log log$ $n$ $)$ bits. Esto hace que las filas sean una porción asintóticamente insignificante del tamaño del bosque. $\lfloor \log n\rfloor$

De las implementaciones anteriores se desprende claramente que el tamaño y el rango de un nodo no importan a menos que un nodo sea la raíz de un árbol. Una vez que un nodo se convierte en hijo, nunca más se accede a su tamaño y rango.

Complejidad del tiempo

Una implementación de bosque de conjunto disjunto en la que Findno actualiza los punteros principales y en la que Unionno intenta controlar las alturas de los árboles puede tener árboles con altura $O (n)$ . En tal situación, las operaciones Findy Unionrequieren tiempo $O (n)$ .

Si una implementación usa solo compresión de ruta, entonces una secuencia de $n$ MakeSet operaciones, seguida de hasta $n - 1$ Union operaciones yf $operaciones$ Find , tiene un tiempo de ejecución en el peor de los casos de . ^[11] $\Theta (n+f\cdot \left(1+\log _{2+f/n}n\right))$

El uso de la unión por rango, pero sin actualizar los punteros principales durante Find, proporciona un tiempo de ejecución de m $operaciones$ de cualquier tipo, hasta $n$ de las cuales son operaciones. ^[11] $\Theta (m\log n)$ MakeSet

La combinación de compresión, división o reducción a la mitad de ruta, con unión por tamaño o por rango, reduce el tiempo de ejecución de $m$ operaciones de cualquier tipo, hasta $n$ de las cuales son MakeSetoperaciones, a . ^[4]^[5] Esto amortiza el tiempo de ejecución de cada operación . Esto es asintóticamente óptimo, lo que significa que cada estructura de datos de conjunto disjunto debe utilizar tiempo amortizado por operación. ^[6] Aquí, la función es la función de Ackermann inversa . La función inversa de Ackermann crece extraordinariamente lentamente, por lo que este factor es $4$ o menos para cualquier $n$ que realmente pueda escribirse en el universo físico. Esto hace que las operaciones de conjuntos disjuntos se amorticen prácticamente en tiempo constante. $\Theta (m\alpha (n))$ $\Theta (\alpha (n))$ $\Omega (\alpha (n))$ $\alpha (n)$

Prueba de complejidad temporal O (m log * n) de Union-Find

El análisis preciso del desempeño de un bosque disjunto es algo complejo. Sin embargo, existe un análisis mucho más simple que demuestra que el tiempo amortizado para cualquier $mo$ operaciones en un bosque de conjunto disjunto que contiene $n$ $objetos$ es $O$ $($ $m$ Find log $*$ $n$ $)$ , donde $log$ $*$ denota el logaritmo iterado . ^[12]^[13]^[14]^[15]Union

Lema 1: A medida que la función de búsqueda sigue el camino hasta la raíz, el rango del nodo que encuentra aumenta.

Prueba

Afirman que a medida que se aplican las operaciones de búsqueda y unión al conjunto de datos, este hecho sigue siendo cierto con el tiempo. Inicialmente, cuando cada nodo es la raíz de su propio árbol, es trivialmente cierto. El único caso en el que se puede cambiar el rango de un nodo es cuando se aplica la operación Unión por rango. En este caso, un árbol con un rango menor se adjuntará a un árbol con un rango mayor, y no al revés. Y durante la operación de búsqueda, todos los nodos visitados a lo largo de la ruta se adjuntarán a la raíz, que tiene un rango mayor que sus hijos, por lo que esta operación tampoco cambiará este hecho.

Lema 2: Un nodo $u$ que es raíz de un subárbol con rango $r$ tiene al menos nodos. $2^{r}$

Prueba

Inicialmente, cuando cada nodo es la raíz de su propio árbol, es trivialmente cierto. Supongamos que un nodo $u$ con rango $r$ tiene al menos $2 r$ nodos. Luego, cuando dos árboles con rango $r$ se fusionan mediante la operación Unión por rango, se obtiene un árbol con rango $r + 1$ , cuya raíz tiene al menos nodos. $2^{r}+2^{r}=2^{r+1}$

Lema 3: El número máximo de nodos de rango $r$ es como máximo ${\frac {n}{2^{r}}}.$

Prueba

Del lema 2, sabemos que un nodo $u$ que es raíz de un subárbol con rango $r$ tiene al menos nodos. Obtendremos el número máximo de nodos de rango $r$ cuando cada nodo con rango $r$ sea la raíz de un árbol que tenga exactamente nodos. En este caso, el número de nodos de rango $r$ es $2^{r}$ $2^{r}$ ${\frac {n}{2^{r}}}.$

Por conveniencia, aquí definimos "depósito": un depósito es un conjunto que contiene vértices con rangos particulares.

Creamos algunos depósitos y colocamos vértices en los depósitos según sus rangos de forma inductiva. Es decir, los vértices con rango 0 van al grupo cero, los vértices con rango 1 van al primer grupo, los vértices con rangos 2 y 3 van al segundo grupo. Si el $B$ -ésimo depósito contiene vértices con rangos del intervalo, entonces el (B+1)st depósito contendrá vértices con rangos del intervalo $\left[r,2^{r}-1\right]=[r,R-1]$ $\left[R,2^{R}-1\right].$

Prueba de hallazgo de unión

O(\log ^{*}n)

Podemos hacer dos observaciones sobre los cubos.

El número total de depósitos es como máximo $log * n$
Prueba: Cuando pasamos de un cubo al siguiente, sumamos dos más a la potencia, es decir, el siguiente cubo será $\left[B,2^{B}-1\right]$ $\left[2^{B},2^{2^{B}}-1\right]$
El número máximo de elementos en el depósito es como máximo $\left[B,2^{B}-1\right]$ ${\frac {2n}{2^{B}}}$
Prueba: el número máximo de elementos en el depósito es como máximo $\left[B,2^{B}-1\right]$ ${\frac {n}{2^{B}}}+{\frac {n}{2^{B+1}}}+{\frac {n}{2^{B+2}} }+\cdots +{\frac {n}{2^{2^{B}-1}}}\leq {\frac {2n}{2^{B}}}.$

Sea $F$ la lista de operaciones de "búsqueda" realizadas y sea

T_{1}=\sum _{F}{\text{(enlace a la raíz)}}

T_{2}=\sum _{F}{\text{(número de enlaces atravesados ​​donde los depósitos son diferentes)}}

T_{3}=\sum _{F}{\text{(número de enlaces atravesados ​​donde los depósitos son iguales).}}

Entonces el costo total de $m$ hallazgos es $T=T_{1}+T_{2}+T_{3}.$

Dado que cada operación de búsqueda realiza exactamente un recorrido que conduce a una raíz, tenemos $T 1 = O (m)$ .

Además, del límite anterior sobre el número de cubos, tenemos $T 2 = O (m log * n)$ .

Para $T 3$ , supongamos que estamos atravesando una arista de $u$ a $v$ , donde $u$ y $v$ tienen rango en el cubo $[B, 2 B - 1]$ y $v$ no es la raíz (en el momento de este recorrido, de lo contrario el recorrido sería contabilizarse en $T 1$ ). Fije $u$ y considere la secuencia que asume el papel de $v$ en diferentes operaciones de búsqueda. Debido a la compresión de la ruta y al no tener en cuenta el borde de una raíz, esta secuencia contiene solo nodos diferentes y debido al Lema 1 sabemos que los rangos de los nodos en esta secuencia son estrictamente crecientes. Al estar ambos nodos en el depósito, podemos concluir que la longitud $k$ de la secuencia (el número de veces que el nodo $u$ se adjunta a una raíz diferente en el mismo depósito) es como máximo el número de rangos en los depósitos $B$ , que es, como máximo $v_{1},v_{2},\ldots ,v_{k}$ $2^{B}-1-B<2^{B}.$

Por lo tanto, $T_{3}\leq \sum _{[B,2^{B}-1]}\sum _{u}2^{B}.$

De las Observaciones 1 y 2, podemos concluir que ${\textstyle T_{3}\leq \sum _{B}2^{B}{\frac {2n}{2^{B}}}\leq 2n\log ^{*}n.}$

Por lo tanto, $T=T_{1}+T_{2}+T_{3}=O(m\log ^{*}n).$

Otras estructuras

Mejor tiempo por operación en el peor de los casos

El peor momento de la Findoperación en árboles con Unión por rango o Unión por peso es (es decir, es y este límite es estricto). En 1985, N. Blum dio una implementación de operaciones que no utiliza la compresión de rutas, sino que comprime los árboles durante . Su implementación se ejecuta en el tiempo por operación, ^[16] y, por lo tanto, en comparación con la estructura de Galler y Fischer, tiene un mejor tiempo por operación en el peor de los casos, pero un tiempo amortizado inferior. En 1999, Alstrup et al. dio una estructura que tiene el tiempo óptimo en el peor de los casos junto con el tiempo amortizado de Ackermann inverso. ^[17] $\Theta (\log n)$ $O(\log n)$ $union$ $O(\log n/\log \log n)$ $O(\log n/\log \log n)$

Supresión

La implementación regular como bosques disjuntos no reacciona favorablemente a la eliminación de elementos, en el sentido de que el tiempo Findno mejorará como resultado de la disminución en el número de elementos. Sin embargo, existen implementaciones modernas que permiten la eliminación en tiempo constante y donde el tiempo límite Finddepende del número actual de elementos ^[18]^[19]

Aplicaciones

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

Las estructuras de datos de conjuntos disjuntos modelan la partición de un conjunto , por ejemplo, para realizar un seguimiento de los componentes conectados de un gráfico no dirigido . Luego, este modelo se puede utilizar para determinar si dos vértices pertenecen al mismo componente o si agregar una arista entre ellos daría como resultado un ciclo. El algoritmo Union-Find se utiliza en implementaciones de unificación de alto rendimiento . ^[20]

La biblioteca Boost Graph utiliza esta estructura de datos para implementar su funcionalidad de componentes conectados incrementales. También es un componente clave en la implementación del algoritmo de Kruskal para encontrar el árbol de expansión mínimo de un gráfico.

El algoritmo de Hoshen-Kopelman utiliza Union-Find en el algoritmo.

Ver también

Refinamiento de particiones , una estructura de datos diferente para mantener conjuntos separados, con actualizaciones que dividen los conjuntos en lugar de fusionarlos.
Conectividad dinámica

Referencias

^ abcdef Tarjan, Robert Endre (1975). "Eficiencia de un algoritmo de unión de conjuntos bueno pero no lineal". Revista de la ACM . 22 (2): 215–225. doi :10.1145/321879.321884. hdl : 1813/5942 . S2CID 11105749.
^ Galler, Bernard A .; Fischer, Michael J. (mayo de 1964). "Un algoritmo de equivalencia mejorado". Comunicaciones de la ACM . 7 (5): 301–303. doi : 10.1145/364099.364331 . S2CID 9034016.. El papel que origina los bosques de conjuntos disjuntos.
^ Hopcroft, JE ; Ullman, JD (1973). "Establecer algoritmos de fusión". Revista SIAM de Computación . 2 (4): 294–303. doi :10.1137/0202024.
^ a b C Tarjan, Robert E .; van Leeuwen, enero (1984). "Análisis del peor de los casos de algoritmos de unión de conjuntos". Revista de la ACM . 31 (2): 245–281. doi : 10.1145/62.2160 . S2CID 5363073.
^ ab Tarjan, Robert Endre (1979). "Una clase de algoritmos que requieren tiempo no lineal para mantener conjuntos disjuntos". Revista de Ciencias de la Computación y de Sistemas . 18 (2): 110-127. doi : 10.1016/0022-0000(79)90042-4 .
^ ab Fredman, M .; Saks, M. (mayo de 1989). "La complejidad de la sonda celular de las estructuras de datos dinámicas". Actas del vigésimo primer simposio anual de ACM sobre teoría de la informática - STOC '89 . págs. 345–354. doi : 10.1145/73007.73040 . ISBN 0897913078. S2CID 13470414. Teorema 5: Cualquier implementación CPROBE(log n ) del problema de unión de conjuntos requiere Ω( m α( m , n )) tiempo para ejecutar m Find y n −1 Union, comenzando con n conjuntos singleton.
^ Galil, Z.; Italiano, G. (1991). "Estructuras de datos y algoritmos para problemas de unión de conjuntos disjuntos". Encuestas de Computación ACM . 23 (3): 319–344. doi :10.1145/116873.116878. S2CID 207160759.
^ Anderson, Richard J.; Woll, Heather (1994). "Algoritmos paralelos sin espera para el problema de búsqueda de unión" . XXIII Simposio ACM sobre Teoría de la Computación. págs. 370–380.
^ Conchón, Sylvain; Filliâtre, Jean-Christophe (octubre de 2007). "Una estructura de datos persistente de búsqueda de sindicatos". Taller ACM SIGPLAN sobre ML. Friburgo, Alemania.
^ Harold N. Gabow, Robert Endre Tarjan, "Un algoritmo de tiempo lineal para un caso especial de unión de conjuntos disjuntos", Journal of Computer and System Sciences, volumen 30, número 2, 1985, págs. 209-221, ISSN 0022- 0000, https://doi.org/10.1016/0022-0000(85)90014-5
^ a b C Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009). "Capítulo 21: Estructuras de datos para conjuntos disjuntos". Introducción a los algoritmos (Tercera ed.). Prensa del MIT. págs. 571–572. ISBN 978-0-262-03384-8.
^ Raimund Seidel , Micha Sharir. "Análisis de arriba hacia abajo de la compresión de rutas", SIAM J. Comput. 34(3):515–525, 2005
^ Tarjan, Robert Endre (1975). "Eficiencia de un algoritmo de unión de conjuntos bueno pero no lineal". Revista de la ACM . 22 (2): 215–225. doi :10.1145/321879.321884. hdl : 1813/5942 . S2CID 11105749.
^ Hopcroft, JE; Ullman, JD (1973). "Establecer algoritmos de fusión". Revista SIAM de Computación . 2 (4): 294–303. doi :10.1137/0202024.
^ Robert E. Tarjan y Jan van Leeuwen . Análisis del peor de los casos de algoritmos de unión de conjuntos. Revista de la ACM, 31(2):245–281, 1984.
^ Blum, Norberto (1985). "Sobre la complejidad del tiempo del peor de los casos de operación única del problema de la unión de conjuntos disjuntos". 2do Sim. Sobre los aspectos teóricos de la informática : 32–38.
^ Alstrup, Stephen; Ben-Amram, Amir M.; Rauhe, Theis (1999). "Peor de los casos y optimidad amortizada en unión-find (resumen ampliado)". Actas del trigésimo primer simposio anual de ACM sobre Teoría de la Computación . págs. 499–506. doi :10.1145/301250.301383. ISBN 1581130678. S2CID 100111.
^ Alstrup, Stephen; Thorup, Mikkel; Gortz, Inge Li; Rauhe, Theis; Zwick, Uri (2014). "Union-Find con eliminaciones de tiempo constante". Transacciones ACM sobre algoritmos . 11 (1): 6:1–6:28. doi :10.1145/2636922. S2CID 12767012.
^ Ben-Amram, Amir M.; Yoffe, Simón (2011). "Un algoritmo Unión-Buscar-Eliminar simple y eficiente". Informática Teórica . 412 (4–5): 487–492. doi : 10.1016/j.tcs.2010.11.005.
^ Caballero, Kevin (1989). «Unificación: Una encuesta multidisciplinar» (PDF) . Encuestas de Computación ACM . 21 : 93-124. doi :10.1145/62029.62030. S2CID 14619034.

enlaces externos

Implementación de C++, parte de las bibliotecas de Boost C++
Implementación de Java, parte de la biblioteca JGraphT
implementación de javascript
Implementación de Python