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 (que no se superponen) . De forma equivalente, almacena una partición de un conjunto en subconjuntos disjuntos . Proporciona operaciones para agregar nuevos conjuntos, fusionar conjuntos (reemplazándolos por su unión ) y encontrar un miembro representativo de un conjunto. Esta última operación permite determinar de forma eficiente si dos elementos pertenecen al mismo conjunto o a conjuntos diferentes.

Aunque existen varias formas de implementar estructuras de datos de conjuntos disjuntos, en la práctica suelen identificarse con una implementación particular conocida como bosque de conjuntos disjuntos . Este tipo especializado de bosque realiza operaciones de unión y búsqueda en un tiempo amortizado casi constante . Para una secuencia de $m$ operaciones de suma, unión o búsqueda en un bosque de conjuntos disjuntos con $n$ nodos, el tiempo total requerido es $O (m α(n))$ , donde $α(n) es la$ función de Ackermann inversa de crecimiento extremadamente lento . Si bien los bosques de conjuntos disjuntos no garantizan este tiempo por operación, cada operación reequilibra la estructura (mediante compresión de árbol) de modo que las operaciones subsiguientes se vuelven más rápidas. Como resultado, los bosques de conjuntos disjuntos son tanto asintóticamente óptimos como prácticamente eficientes.

Las estructuras de datos de conjuntos disjuntos desempeñan un papel fundamental en el algoritmo de Kruskal para encontrar el árbol de expansión mínima de un grafo. La importancia de los árboles de expansión mínima implica que las estructuras de datos de conjuntos disjuntos son compatibles con una amplia variedad de algoritmos. Además, estas estructuras de datos encuentran aplicaciones en la computación simbólica y en compiladores, especialmente en 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, su complejidad temporal fue limitada a $O(\log ^{*}(n))$ , el logaritmo iterado de $n$ , por Hopcroft y Ullman . ^{[ 3 ]} En 1975, Robert Tarjan fue el primero en demostrar la $O(m\alpha (n))$ ( función de Ackermann inversa ) cota superior de la complejidad temporal del algoritmo. ^{[ 4 ]} También demostró que era ajustada. En 1979, demostró que esta era la cota inferior para una cierta clase de algoritmos, los algoritmos de punteros , que incluyen la estructura de Galler-Fischer. ^{[ 5 ]} En 1989, Fredman y Saks demostraron que $\Omega (\alpha (n))$ (amortizadas) palabras de $O(\log n)$ Los bits deben ser accedidos por cualquier estructura de datos de conjunto disjunto por operación, ^{[ 6 ]} demostrando así la optimalidad de la estructura de datos en este modelo.

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 paralela 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 de bosque de conjuntos disjuntos y formalizaron su corrección utilizando el asistente de prueba Rocq (entonces: Coq ). ^{[ 9 ]} "Semipersistente" significa que las versiones anteriores de la estructura se conservan de manera eficiente, pero el acceso a 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 ]} En particular, el tiempo lineal es alcanzable si se da a priori un "árbol de unión". Este es un árbol que incluye todos los elementos de los conjuntos. Sea p[ v ] el padre en el árbol, entonces la suposición es que las operaciones de unión deben tener la forma unión ( v ,p[ v ]) para algún v .

Representación

En esta sección y la siguiente describimos la implementación más común de la estructura de datos de conjuntos disjuntos, como un bosque de árboles de punteros a padres . Esta representación se conoce como árboles de Galler-Fischer .

Cada nodo en un bosque de conjuntos disjuntos 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 a padres , donde cada nodo que no es la raíz de un árbol apunta a su padre. Para distinguir los nodos raíz de los demás, sus punteros a padres tienen valores inválidos, como una referencia circular al nodo o un valor centinela . Cada árbol representa un conjunto almacenado en el bosque, cuyos miembros son los nodos del árbol. Los nodos raíz proporcionan representantes de conjuntos: dos nodos están en el mismo conjunto si y solo si las raíces de los árboles que contienen los nodos son iguales.

Los nodos del bosque se pueden almacenar de cualquier forma que resulte conveniente para la aplicación, pero una técnica común es almacenarlos en un array. En este caso, los padres se pueden indicar mediante su índice en el array. Cada entrada del array requiere $Θ(log n)$ bits de almacenamiento para el puntero al padre. Se requiere una cantidad de almacenamiento comparable o menor para el resto de la entrada, por lo que el número de bits necesarios para almacenar el bosque es $Θ(n log n)$ . Si una implementación utiliza nodos de tamaño fijo (limitando así 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 dado; y fusionar dos conjuntos.

Fabricación de nuevos conjuntos

La MakeSetoperación añade un nuevo elemento a un nuevo conjunto que contiene únicamente dicho elemento, y este nuevo conjunto se añade a la estructura de datos. Si, en cambio, la estructura de datos se considera una partición de un conjunto, la MakeSetoperación amplía el conjunto añadiendo el nuevo elemento y extiende la partición existente colocando el nuevo elemento en un nuevo subconjunto que contiene únicamente dicho elemento.

En un bosque de conjuntos disjuntos, MakeSetse inicializa el puntero padre 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 :

función MakeSet( x ) es si x no está ya en el bosque entonces x .parent := x x .size := 1 // si los nodos almacenan tamaño x .rank := 0 // si los nodos almacenan rango fin si fin función

Esta operación tiene una complejidad temporal lineal. En particular, inicializar un bosque de conjuntos disjuntos con $n$ nodos requiere un tiempo de $O (n)$ .

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

En la práctica, MakeSetdebe ir precedida de una operación que asigne memoria para almacenar $x$ . Siempre que la asignación de memoria sea una operación amortizada de tiempo constante, como ocurre en una buena implementación de arreglos dinámicos , no cambia el rendimiento asintótico del bosque de conjuntos aleatorios.

Encontrar representantes de conjuntos

La Findoperación sigue la cadena de punteros padre desde un nodo de consulta especificado $x$ hasta que alcanza 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 ofrece una importante oportunidad para mejorar el bosque. El tiempo Findque se tarda en una operación se invierte en seguir los punteros de los padres, por lo que un árbol más plano permite Findoperaciones más rápidas. Al Findejecutar una operación, no hay forma más rápida de llegar a la raíz que siguiendo sucesivamente cada puntero de padre. Sin embargo, los punteros de padre visitados durante esta búsqueda pueden actualizarse para que apunten más cerca de la raíz. Dado que cada elemento visitado en el camino hacia la raíz forma parte del mismo conjunto, esto no modifica los conjuntos almacenados en el bosque. Pero sí Findacelera las operaciones futuras, no solo 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 rendimiento amortizado del bosque de conjuntos disjuntos.

Existen varios algoritmos que Findlogran una complejidad temporal asintóticamente óptima. Una familia de algoritmos, conocida como compresión de rutas , 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 recursión simple como la siguiente:

La función Find( x ) es: si x.parent ≠ x, entonces x.parent := Find( x.parent ) devuelve x.parent ; de lo contrario, devuelve x. Fin de la función.

Esta implementación realiza dos pasadas, una hacia arriba en el á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 ambas pasadas en la misma dirección. La implementación con memoria constante recorre el árbol desde el nodo de consulta hasta la raíz dos veces: una para encontrar la raíz y otra para actualizar los punteros.

función Find( x ) es raíz := x mientras raíz .parent ≠ raíz hacer raíz := raíz .parent fin mientrasmientras x.parent ≠ root hacer padre := x.parent x.parent := root x : = padre fin mientrasfunción final de retorno raíz

Tarjan y Van Leeuwen también desarrollaron Findalgoritmos de una sola pasada que mantienen 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 padre de los nodos en la ruta entre el nodo de consulta y la raíz. La división de ruta reemplaza cada puntero padre en esa ruta por un puntero al abuelo del nodo:

función Find( x ) es mientras x .parent ≠ x hacer ( x , x .parent) := ( x .parent, x .parent.parent) fin mientras devolver x fin función

La reducción a la mitad de la ruta funciona de manera similar, pero reemplaza solo uno de cada dos punteros padres:

función Find( x ) es mientras x .parent ≠ x hacer x .parent := x .parent.parent x := x .parent fin mientras devolver x fin función

Combinar dos conjuntos

MakeSetcrea 8 instancias únicas.

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$ por su unión. Primero se utilizan 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 deben fusionarse. Esto se hace estableciendo el puntero padre de la raíz de $x$ a la raíz $de y$ , o estableciendo el puntero padre de la raíz de $y a la raíz de$ $x$ .Union(x, y)UnionFind

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

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

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 se fusionan los árboles con raíces $x$ e $y$ , el nodo con más descendientes se convierte en el nodo padre. Si ambos nodos tienen el mismo número de descendientes, cualquiera de ellos puede convertirse en el nodo padre. En ambos casos, el tamaño del nuevo nodo padre se establece según su nuevo número total de descendientes.

La función Unión( x , y ) es // Reemplazar nodos por raíces x := Find( x ) y := Find( y ) Si x = y, entonces regresa // x e y ya están en el mismo conjunto. Fin de la condición.// Si es necesario, intercambia las variables para asegurar que // x tenga al menos tantos descendientes como y. Si x.size < y.size entonces ( x , y ) := ( y , x ) fin si // Hacer que x sea la nueva raíz y.parent := x // Actualizar el tamaño de x x.size := x.size + y.size fin de la función

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 se comparan sus rangos. Si los rangos son diferentes, el árbol con el rango mayor se convierte en el padre, y los rangos de $x$ $e$ y no cambian. Si los rangos son iguales, cualquiera de ellos puede convertirse en el 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:

La función Unión( x , y ) es // Reemplazar nodos por raíces x := Find( x ) y := Find( y ) Si x = y, entonces regresa // x e y ya están en el mismo conjunto. Fin de la condición.// Si es necesario, renombra las variables para asegurar que // x tenga un rango al menos tan grande como el de y. Si x.rank < y.rank , entonces ( x , y ) := ( y , x ). Fin si// Establecer x como la nueva raíz y.parent : = x // Si es necesario, incrementar el rango de x if x.rank = y.rank then x.rank := x.rank + 1 end if end function

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

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

Existe una variante de la Unionoperación en la que el usuario determina el representante del conjunto formado. No es difícil añadir esta funcionalidad a los algoritmos anteriores sin perder eficiencia.

complejidad temporal

Una implementación de bosque de conjuntos disjuntos en la que Findno se actualizan los punteros de los padres y en la que Unionno se intenta controlar las alturas de los árboles, puede tener árboles con altura $O (n)$ . En tal situación, las operaciones Findy requieren un tiempo $O$ $($ $n$ $)$ .Union

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

Utilizando la unión por rango, pero sin actualizar los punteros del padre durante Find, se obtiene un tiempo de ejecución de $\Theta (m\log n)$ para $m$ operaciones de cualquier tipo, hasta $n$ de las cuales son MakeSetoperaciones. ^{[ 11 ]}

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

Demostración de la complejidad temporal O(m log* n) de Union-Find

El análisis preciso del rendimiento de un bosque de conjuntos disjuntos es algo complejo. Sin embargo, existe un análisis mucho más simple que demuestra que el tiempo amortizado para cualquier operación $m$ Find o Unionen un bosque de conjuntos disjuntos que contiene $n$ objetos es $O (m log * n)$ , donde $log *$ denota el logaritmo iterado . ^{[ 12 ]}^{[ 13 ]}^{[ 14 ]}^{[ 15 ]}

Lema 1: A medida que la función find sigue el camino hacia la raíz, el rango del nodo que encuentra va aumentando.

Prueba

Afirmamos que, al aplicar las operaciones Find y Union al conjunto de datos, este hecho se mantiene constante. Inicialmente, cuando cada nodo es la raíz de su propio árbol, esto es trivialmente cierto. El único caso en que el rango de un nodo podría cambiar es al aplicar la operación Union by Rank . En este caso, un árbol con menor rango se unirá a un árbol con mayor rango, y no al revés. Además, durante la operación Find, todos los nodos visitados a lo largo de la ruta se unirán a la raíz, que tiene mayor rango que sus hijos, por lo que esta operación tampoco modificará este hecho.

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

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. Entonces, cuando dos árboles con rango $r$ se fusionan usando la operación Unión por Rango , resulta un árbol con rango $r + 1$ , cuya raíz tiene al menos $2^{r}+2^{r}=2^{r+1}$ nodos.

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 $2^{r}$ 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 $2^{r}$ nodos. En este caso, el número de nodos de rango $r$ es ${\frac {n}{2^{r}}}.$

En cualquier punto particular de la ejecución, podemos agrupar los vértices del grafo en "cubos", según su rango. Definimos los rangos de los cubos inductivamente, de la siguiente manera: El cubo 0 contiene vértices de rango 0. El cubo 1 contiene vértices de rango 1. El cubo 2 contiene vértices de rangos 2 y 3. En general, si el cubo $B$ contiene vértices con rangos del intervalo $\left[r,2^{r}-1\right]=[r,R-1]$ , entonces el (B+1)-ésimo cubo contendrá vértices con rangos del intervalo $\left[R,2^{R}-1\right].$

Para $B\in \mathbb {N}$ , dejar ${\text{torre}}(B)=\underbrace {2^{2^{\cdots ^{2}}}} _{B{\text{ veces}}}$ . Luego cubo $B$ tendrá vértices con rangos en el intervalo $[{\text{torre}}(B-1),{\text{torre}}(B)-1]$ .

Prueba de $O(\log ^{*}n)$ Hallazgo de la Unión

{\displaystyle O(\log ^{*}n)} — Prueba de $O(\log ^{*}n)$ Hallazgo de la Unión

Podemos hacer dos observaciones sobre el tamaño de los cubos.

El número total de cubetas es como máximo $log * n$ .
Prueba: Dado que ningún vértice puede tener un rango mayor que $n$ , solo el primero $\log ^{*}(n)$ Los cubos pueden tener vértices, donde $\log ^{*}$ denota el inverso de la ${\text{torre}}$ función definida anteriormente.
El número máximo de elementos en el cubo $\left[B,2^{B}-1\right]$ es como máximo ${\frac {2n}{2^{B}}}$ .
Prueba: El número máximo de elementos en el cubo $\left[B,2^{B}-1\right]$ es como máximo ${\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 recorridos donde los cubos son diferentes)}}$ $T_{3}=\sum _{F}{\text{(número de enlaces recorridos donde los cubos son iguales).}}$

Entonces, el costo total de $m$ encuentra 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, a partir del límite anterior en el número de cubetas, tenemos $T 2 = O (m log * n)$ .

Para $T 3$ , supongamos que estamos recorriendo 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 se tendría en cuenta en $T 1$ ). Fijemos $u$ y consideremos la secuencia $v_{1},v_{2},\ldots,v_{k}$ que toman el rol de $v$ en diferentes operaciones de búsqueda. Debido a la compresión de ruta y a que no se tiene en cuenta la arista a 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 cubo, podemos concluir que la longitud $k$ de la secuencia (el número de veces que el nodo $u$ está conectado a una raíz diferente en el mismo cubo) es como máximo el número de rangos en los cubos $B$ , es decir, como máximo $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 en el peor de los casos por operación

El peor escenario posible de la Findoperación en árboles con unión por rango o unión por peso es $\Theta (\log n)$ (es decir, es $O(\log n)$ y este límite es ajustado). En 1985, N. Blum dio una implementación de las operaciones que no utiliza compresión de ruta, pero comprime árboles durante $union$ Su implementación se ejecuta en $O(\log n/\log \log n)$ 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. dieron una estructura que tiene un tiempo óptimo en el peor de los casos. $O(\log n/\log \log n)$ junto con el tiempo amortizado de Ackermann inverso. ^{[ 17 ]}

Supresión

La implementación regular como bosques de conjuntos disjuntos no reacciona favorablemente a la eliminación de elementos, en el sentido de que el tiempo para 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 límite de tiempo para Finddepende del número actual de elementos ^{[ 18 ]}^{[ 19 ]}

Retroceder

Es posible extender ciertas estructuras de bosque de conjuntos disjuntos para permitir el retroceso . La forma básica de retroceso es permitir una Backtrack(1)operación que deshace la última Union. Una forma más avanzada permite Backtrack(i)que deshaga las últimas i uniones. Se conoce el siguiente resultado de complejidad: existe una estructura de datos que admite Union y Finden $O(\log n/\log \log n)$ tiempo por operación y Backtracken $O(1)$ tiempo. ^{[ 20 ]} En este resultado, la libertad de Unionelegir el representante del conjunto formado es esencial. No se puede lograr un mejor tiempo amortizado dentro de la clase de algoritmos de puntero separables . ^{[ 20 ]}

Aplicaciones

Una demostración de Union-Find al usar el algoritmo de Kruskal para encontrar el árbol de expansión mínima.

Las estructuras de datos de conjuntos disjuntos modelan la partición de un conjunto , por ejemplo, para realizar un seguimiento de los componentes conexos de un grafo no dirigido . Este modelo se puede utilizar para determinar si dos vértices pertenecen al mismo componente o si añadir una arista entre ellos daría como resultado un ciclo. El algoritmo Union-Find se utiliza en implementaciones de unificación de alto rendimiento . ^{[ 21 ]}

Esta estructura de datos es utilizada por la biblioteca Boost Graph 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ínima de un grafo.

El algoritmo de Hoshen-Kopelman utiliza una operación de unión y búsqueda.

El algoritmo Union-find puede utilizarse para implementar algoritmos de inferencia de tipos con un rendimiento razonable .

Véase también

Refinamiento de partición , una estructura de datos diferente para mantener conjuntos disjuntos, con actualizaciones que dividen los conjuntos en lugar de fusionarlos.
Conectividad dinámica : estructura de datos que mantiene información sobre los componentes conectados de un grafo.

Referencias

1 2 3 4 5 6 Tarjan, Robert Endre (1975). "Eficiencia de un buen algoritmo de unión de conjuntos, pero no lineal". Journal of the 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" . Communications of the ACM . 7 (5): 301– 303. doi : 10.1145/364099.364331 . S2CID 9034016 . . El artículo que dio origen a los bosques de conjuntos disjuntos.
↑ Hopcroft, JE ; Ullman, JD (1973). "Algoritmos de fusión de conjuntos". SIAM Journal on Computing . 2 (4): 294– 303. doi : 10.1137/0202024 .
1 2 3 Tarjan, Robert E. ; van Leeuwen, Jan (1984). "Análisis del peor caso de algoritmos de unión de conjuntos" . Journal of the ACM . 31 (2): 245– 281. doi : 10.1145/62.2160 . S2CID 5363073 .
1 2 Tarjan, Robert Endre (1979). "Una clase de algoritmos que requieren tiempo no lineal para mantener conjuntos disjuntos" . Journal of Computer and System Sciences . 18 (2): 110– 127. doi : 10.1016/0022-0000(79)90042-4 .
1 2 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 la ACM sobre Teoría de la Computación - 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 )) de tiempo para ejecutar m Find y n − 1 Union, comenzando con n conjuntos unitarios.
↑ Galil, Z.; Italiano, G. (1991). "Estructuras de datos y algoritmos para problemas de unión de conjuntos disjuntos". ACM Computing Surveys . 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 unión-búsqueda . 23.º Simposio ACM sobre Teoría de la Computación. pp. 370–380 . doi : 10.1145/103418.103458 .
↑ Conchon, Sylvain; Filliâtre, Jean-Christophe (octubre de 2007). "Una estructura de datos persistente de unión-búsqueda". Taller ACM SIGPLAN sobre aprendizaje automático . 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
1 2 3 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.). MIT Press. págs. 571–572 . ISBN 978-0-262-03384-8.
↑ Raimund Seidel , Micha Sharir. "Análisis descendente de la compresión de rutas", SIAM J. Comput. 34(3):515–525, 2005
↑ Tarjan, Robert Endre (1975). "Eficiencia de un buen algoritmo de unión de conjuntos, pero no lineal" . Journal of the ACM . 22 (2): 215– 225. doi : 10.1145/321879.321884 . hdl : 1813/5942 . S2CID 11105749 .
↑ Hopcroft, JE; Ullman, JD (1973). "Algoritmos de fusión de conjuntos". SIAM Journal on Computing . 2 (4): 294– 303. doi : 10.1137/0202024 .
↑ Robert E. Tarjan y Jan van Leeuwen . Análisis del peor caso de los algoritmos de unión de conjuntos. Journal of the ACM, 31(2):245–281, 1984.
↑ Blum, Norbert (1985). "Sobre la complejidad temporal en el peor de los casos de una sola operación del problema de unión de conjuntos disjuntos". 2.º Simposio sobre aspectos teóricos de la informática : 32–38 .
↑ Alstrup, Stephen; Ben-Amram, Amir M.; Rauhe, Theis (1999). "Optimalidad en el peor de los casos y amortizada en union-find (Resumen extendido)". Actas del trigésimo primer simposio anual de la 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, Simon (2011). "Un algoritmo simple y eficiente de unión, búsqueda y eliminación". Theoretical Computer Science . 412 ( 4–5 ): 487–492 . doi : 10.1016/j.tcs.2010.11.005 .
1 2 Westbrook, Jeffery R.; Tarjan, Robert E. (1989). "Análisis amortizado de algoritmos para la unión de conjuntos con retroceso". SIAM Journal on Computing . 18 (1): 1– 11. doi : 10.1137/0218001 .
↑ Knight, Kevin (1989). "Unificación: Un estudio multidisciplinario" (PDF) . ACM Computing Surveys . 21 : 93–124 . doi : 10.1145/62029.62030 . S2CID 14619034 .

Enlaces externos

Implementación en C++ , parte de las bibliotecas Boost C++.
Implementación en Java , parte de la biblioteca JGraphT.
Implementación de Javascript
Implementación en Python

[tarjan1975-1] 1 2 3 4 5 6 Tarjan, Robert Endre (1975). "Eficiencia de un buen algoritmo de unión de conjuntos, pero no lineal". Journal of the ACM . 22 (2): 215– 225. doi : 10.1145/321879.321884 . hdl : 1813/5942 . S2CID 11105749 .

[Galler1964-2] Galler, Bernard A. ; Fischer, Michael J. (mayo de 1964). "Un algoritmo de equivalencia mejorado" . Communications of the ACM . 7 (5): 301– 303. doi : 10.1145/364099.364331 . S2CID 9034016 . . El artículo que dio origen a los bosques de conjuntos disjuntos.

[Hopcroft1973-3] Hopcroft, JE ; Ullman, JD (1973). "Algoritmos de fusión de conjuntos". SIAM Journal on Computing . 2 (4): 294– 303. doi : 10.1137/0202024 .

[Tarjan1984-4] 1 2 3 Tarjan, Robert E. ; van Leeuwen, Jan (1984). "Análisis del peor caso de algoritmos de unión de conjuntos" . Journal of the ACM . 31 (2): 245– 281. doi : 10.1145/62.2160 . S2CID 5363073 .

[Tarjan1979-5] 1 2 Tarjan, Robert Endre (1979). "Una clase de algoritmos que requieren tiempo no lineal para mantener conjuntos disjuntos" . Journal of Computer and System Sciences . 18 (2): 110– 127. doi : 10.1016/0022-0000(79)90042-4 .

[Fredman1989-6] 1 2 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 la ACM sobre Teoría de la Computación - 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 )) de tiempo para ejecutar m Find y n − 1 Union, comenzando con n conjuntos unitarios.

[Galil1991-7] Galil, Z.; Italiano, G. (1991). "Estructuras de datos y algoritmos para problemas de unión de conjuntos disjuntos". ACM Computing Surveys . 23 (3): 319– 344. doi : 10.1145/116873.116878 . S2CID 207160759 .

[Anderson1994-8] Anderson, Richard J.; Woll, Heather (1994). Algoritmos paralelos sin espera para el problema de unión-búsqueda . 23.º Simposio ACM sobre Teoría de la Computación. pp. 370–380 . doi : 10.1145/103418.103458 .

[Conchon2007-9] Conchon, Sylvain; Filliâtre, Jean-Christophe (octubre de 2007). "Una estructura de datos persistente de unión-búsqueda". Taller ACM SIGPLAN sobre aprendizaje automático . Friburgo, Alemania.

[10] 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

[Cormen2009-11] 1 2 3 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.). MIT Press. págs. 571–572 . ISBN 978-0-262-03384-8.

[12] Raimund Seidel , Micha Sharir. "Análisis descendente de la compresión de rutas", SIAM J. Comput. 34(3):515–525, 2005

[13] Tarjan, Robert Endre (1975). "Eficiencia de un buen algoritmo de unión de conjuntos, pero no lineal" . Journal of the ACM . 22 (2): 215– 225. doi : 10.1145/321879.321884 . hdl : 1813/5942 . S2CID 11105749 .

[14] Hopcroft, JE; Ullman, JD (1973). "Algoritmos de fusión de conjuntos". SIAM Journal on Computing . 2 (4): 294– 303. doi : 10.1137/0202024 .

[15] Robert E. Tarjan y Jan van Leeuwen . Análisis del peor caso de los algoritmos de unión de conjuntos. Journal of the ACM, 31(2):245–281, 1984.

[16] Blum, Norbert (1985). "Sobre la complejidad temporal en el peor de los casos de una sola operación del problema de unión de conjuntos disjuntos". 2.º Simposio sobre aspectos teóricos de la informática : 32–38 .

[17] Alstrup, Stephen; Ben-Amram, Amir M.; Rauhe, Theis (1999). "Optimalidad en el peor de los casos y amortizada en union-find (Resumen extendido)". Actas del trigésimo primer simposio anual de la ACM sobre Teoría de la Computación . págs. 499–506 . doi : 10.1145/301250.301383 . ISBN 1581130678. S2CID 100111 .

[18] 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 .

[19] Ben-Amram, Amir M.; Yoffe, Simon (2011). "Un algoritmo simple y eficiente de unión, búsqueda y eliminación". Theoretical Computer Science . 412 ( 4–5 ): 487–492 . doi : 10.1016/j.tcs.2010.11.005 .

[WT-20] 1 2 Westbrook, Jeffery R.; Tarjan, Robert E. (1989). "Análisis amortizado de algoritmos para la unión de conjuntos con retroceso". SIAM Journal on Computing . 18 (1): 1– 11. doi : 10.1137/0218001 .

[Knight1989-21] Knight, Kevin (1989). "Unificación: Un estudio multidisciplinario" (PDF) . ACM Computing Surveys . 21 : 93–124 . doi : 10.1145/62029.62030 . S2CID 14619034 .

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

Historia

Representación

Operaciones

Fabricación de nuevos conjuntos

Encontrar representantes de conjuntos

Combinar dos conjuntos

Unión por tamaño

Unión por rango

complejidad temporal

Demostración de la complejidad temporal O(m log* n) de Union-Find

Otras estructuras

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

Supresión

Retroceder

Aplicaciones

Véase también

Referencias

Enlaces externos

Articulos relacionados