Estructura de datos de conjunto disjunto

Estructura de datos para almacenar conjuntos no superpuestos

En informática , una estructura de datos de conjunto disjunto , 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 (reemplazándolos 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 existen varias formas de implementar estructuras de datos de conjuntos disjuntos, en la práctica a menudo se las identifica con una implementación particular llamada bosque de conjuntos disjuntos . Este es un tipo especializado de bosque que realiza uniones y hallazgos en un tiempo amortizado casi constante . Para realizar una secuencia de m operaciones de adición, unión o hallazgo 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 unión y hallazgo individuales pueden tardar más que un tiempo constante multiplicado por α( 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 desempeñan un papel fundamental en el algoritmo de Kruskal para encontrar el árbol de expansión mínimo de un grafo. La importancia de los árboles de expansión mínimos significa que las estructuras de datos de conjuntos disjuntos son la base de 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 los 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, su complejidad temporal fue limitada a , el logaritmo iterado de , por Hopcroft y Ullman . ^[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 estricto. En 1979, demostró que este era el límite inferior para una cierta 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 optimalidad de la estructura de datos en este modelo. ${\displaystyle O(\log ^{*}(n))}$ ${\displaystyle n}$ ${\displaystyle O(m\alpha (n))}$ ${\displaystyle \Omega (\alpha (n))}$ ${\displaystyle O(\log n)}$

En 1991, Galil e Italiano publicaron un estudio de 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 del bosque 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 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 un 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 de 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 primarios , 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 primarios tienen valores no válidos, como una referencia circular al nodo o un valor centinela. Cada árbol representa un conjunto almacenado en el bosque, y los miembros del conjunto 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 una matriz. En este caso, los padres se pueden indicar mediante su índice de matriz. Cada entrada de la matriz requiere Θ(log n ) bits de almacenamiento para el puntero padre. 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 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 el nuevo elemento, y el nuevo conjunto se añade a la estructura de datos. Si, en cambio, la estructura de datos se considera como 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 el nuevo elemento.

En un bosque de conjuntos disjuntos, 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:

función MakeSet( x ) es  si  x no está ya 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  fin si fin de la función

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

La falta de un padre asignado al nodo 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 . Mientras la asignación de memoria sea una operación de tiempo constante amortizada, como lo es para una buena implementación de matriz dinámica , 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 al que llega.

La ejecución de una Findoperación presenta una oportunidad importante para mejorar el bosque. El tiempo de una Findoperación se emplea en buscar punteros principales, por lo que un árbol más plano conduce a Findoperaciones más rápidas. Cuando Findse ejecuta a, no hay una forma más rápida de llegar a la raíz que seguir 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 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 Findque logran la complejidad temporal óptima de forma asintótica. 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 ruta se puede implementar utilizando una recursión simple de la siguiente manera:

función Find( x ) es  si  x .parent ≠ x  entonces  x .parent := Find( x .parent) devuelve  x .parent de lo contrario  devuelve  x  fin si fin de 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 ambas pasadas en la misma dirección. La implementación de memoria constante recorre 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 . padre ≠ raíz  hacer  raíz  := raíz . padre fin mientras mientras  x .parent ≠ root  hacer  padre  := x .parent x .parent := root  x  := padre  fin mientras  función de retorno raíz final

Tarjan y Van LeeuwenFind también desarrollaron algoritmos de una sola pasada que conservan la misma complejidad del 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 nodo principal del nodo:

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

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

función Find( x ) es  mientras  x .parent ≠ x  hacer  x .parent := x .parent.parent x  := x .parent fin mientras  devuelve  x fin de 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 a x y el conjunto que contiene a y con su unión. primero se utiliza para determinar las raíces de los árboles que contienen a x e y . Si las raíces son las mismas, 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 en y o estableciendo el puntero padre de la raíz de y en x.Union(x, y)UnionFind

La elección de qué nodo se convierte en el 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 Unionsiempre hizo que el árbol que contiene x fuera un subárbol del árbol que contiene y . Comience con un bosque que acaba de ser inicializado con elementos y ejecute , , ..., . El bosque resultante contiene un solo árbol cuya raíz es n , y la ruta de 1 a n pasa por cada nodo del árbol. Para este bosque, el tiempo de ejecución es O ( n ) . ${\displaystyle 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 la unión por tamaño o la unión por rango . Ambas requieren un nodo para almacenar información además de su puntero padre. Esta información se utiliza para decidir qué raíz se convierte en la nueva raíz 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 padre. Si los dos nodos tienen el mismo número de descendientes, entonces cualquiera de ellos puede convertirse en el 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  := Find( x ) y  := Find( y ) si  x = y  entonces  retorna  // x e y ya están en el mismo conjunto  fin si // Si es necesario, intercambie las variables para garantizar que  x tenga al menos tantos descendientes como y  if  x .size < y .size then ( x , y ) := ( y , x ) end if // 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 agrega un factor constante al almacenamiento requerido del bosque.

Unión por rangos

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 rangos. Si los rangos son diferentes, entonces el árbol de rango más grande se convierte en el padre, y los rangos de x e y no cambian. Si los rangos son los mismos, entonces cualquiera de los dos 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:

función Unión( x , y ) es  // Reemplazar nodos por raíces  x  := Find( x ) y  := Find( y ) si  x = y  entonces  retorna  // x e y ya están en el mismo conjunto  fin 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 then ( x , y ) := ( y , x ) end if // Convierte a x en la nueva raíz  y .parent := x  // Si es necesario, incrementa 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 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 los rangos sean una porción asintóticamente insignificante del tamaño del bosque. ${\displaystyle \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 el nodo sea la raíz de un árbol. Una vez que un nodo se convierte en un nodo secundario, nunca más se vuelve a acceder a su tamaño y rango.

Complejidad temporal

Una implementación de bosque de conjuntos disjuntos en la que Findno se actualizan los punteros principales y en la que Unionno se intenta controlar la altura de los árboles puede tener árboles con una altura de O ( n ) . En tal situación, las operaciones Findy requieren un tiempo de 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 . ^[11] ${\displaystyle \Theta (n+f\cdot \left(1+\log _{2+f/n}n\right))}$

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

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

Prueba de la complejidad temporal de 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 m Find o Unionoperaciones en un bosque de conjuntos disjuntos que contenga 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 de búsqueda sigue el camino hacia la raíz, el rango del nodo que encuentra aumenta.

Prueba

Afirmamos que, a medida que se aplican las operaciones de búsqueda y unión al conjunto de datos, este hecho sigue siendo cierto a lo largo del 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 de unión por rango. En este caso, un árbol con un rango menor se adjuntará a un árbol con un rango mayor, en lugar de lo contrario. 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. ${\displaystyle 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 se fusionan dos árboles con rango r utilizando la operación Unión por rango, resulta un árbol con rango r + 1 , cuya raíz tiene al menos nodos. ${\displaystyle 2^{r}+2^{r}=2^{r+1}}$

Lema 3: El número máximo de nodos de rango r es como máximo ${\displaystyle {\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 ${\displaystyle 2^{r}}$ ${\displaystyle 2^{r}}$ ${\displaystyle {\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 de forma inductiva, de la siguiente manera: El cubo 0 contiene vértices de rango 1. El cubo 1 contiene vértices de rango 2 y 3. En general, si el cubo B -ésimo contiene vértices con rangos del intervalo , entonces el cubo (B+1)º contendrá vértices con rangos del intervalo ${\displaystyle \left[r,2^{r}-1\right]=[r,R-1]}$ ${\displaystyle \left[R,2^{R}-1\right].}$

Para , sea . Entonces el cubo tendrá vértices con rangos en el intervalo . ${\displaystyle B\in \mathbb {N} }$ ${\displaystyle {\text{tower}}(B)=\underbrace {2^{2^{\cdots ^{2}}}} _{B{\text{ times}}}}$ ${\displaystyle B}$ ${\displaystyle [{\text{tower}}(B),{\text{tower}}(B)-1]}$

Prueba de unión Encontrar ${\displaystyle O(\log ^{*}n)}$

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

1. El número total de cubos es como máximo log ^* n .

   Prueba: Dado que ningún vértice puede tener un rango mayor que , solo los primeros grupos pueden tener vértices, donde denota la inversa de la función definida anteriormente. ${\displaystyle n}$ ${\displaystyle \log ^{*}(n)}$ ${\displaystyle \log ^{*}}$ ${\displaystyle {\text{tower}}}$

2. El número máximo de elementos en el depósito es como máximo . ${\displaystyle \left[B,2^{B}-1\right]}$ ${\displaystyle {\frac {2n}{2^{B}}}}$

   Prueba: El número máximo de elementos en el depósito es como máximo ${\displaystyle \left[B,2^{B}-1\right]}$ ${\displaystyle {\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

$${\displaystyle T_{1}=\sum _{F}{\text{(link to the root)}}}$$ $${\displaystyle T_{2}=\sum _{F}{\text{(number of links traversed where the buckets are different)}}}$$ $${\displaystyle T_{3}=\sum _{F}{\text{(number of links traversed where the buckets are the same).}}}$$

Entonces el costo total de m hallazgos es ${\displaystyle 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 ₁ = O ( m ) .

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

Para T ₃ , supongamos que estamos recorriendo una arista desde u hasta v , donde u y v tienen rango en el contenedor [ B , 2 ^B − 1] y v no es la raíz (en el momento de este recorrido, de lo contrario el recorrido se contabilizaría en T ₁ ). Fijemos u y consideremos la secuencia que toma el papel de v en diferentes operaciones de búsqueda. Debido a la compresión de la ruta y al no tener en cuenta la arista hacia 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 contenedor, podemos concluir que la longitud k de la secuencia (el número de veces que el nodo u está unido a una raíz diferente en el mismo contenedor) es como máximo el número de rangos en los contenedores B , es decir, como máximo ${\displaystyle v_{1},v_{2},\ldots ,v_{k}}$ ${\displaystyle 2^{B}-1-B<2^{B}.}$

Por lo tanto, ${\displaystyle 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, ${\displaystyle 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 tiempo de peor caso 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 proporcionó una implementación de las operaciones que no utiliza compresión de trayectorias, sino que comprime los árboles durante . Su implementación se ejecuta en tiempo por operación, ^[16] y, por lo tanto, en comparación con la estructura de Galler y Fischer, tiene un mejor tiempo de peor caso por operación, pero un tiempo amortizado inferior. En 1999, Alstrup et al. proporcionaron una estructura que tiene un tiempo de peor caso óptimo junto con un tiempo amortizado de Ackermann inverso. ^[17] ${\displaystyle \Theta (\log n)}$ ${\displaystyle O(\log n)}$ ${\displaystyle union}$ ${\displaystyle O(\log n/\log \log n)}$ ${\displaystyle O(\log n/\log \log n)}$

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 de ejecución 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 de ejecución 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 el á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 . 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 alto rendimiento de unificación . ^[20]

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

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

Véase también

• Refinamiento de particiones , una estructura de datos diferente para mantener conjuntos disjuntos, con actualizaciones que separan los conjuntos en lugar de fusionarlos
• Conectividad dinámica

Referencias

1. 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.
2. 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 documento que da origen a los bosques disjuntos.
3. Hopcroft, JE ; Ullman, JD (1973). "Algoritmos de fusión de conjuntos". Revista SIAM de informática . 2 (4): 294–303. doi :10.1137/0202024.
4. Tarjan, Robert E. ; van Leeuwen, Jan (1984). "Análisis del peor caso de algoritmos de unión de conjuntos". Revista de la ACM . 31 (2): 245–281. doi : 10.1145/62.2160 . S2CID  5363073.
5. 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 .
6. Fredman, M. ; Saks, M. (mayo de 1989). "La complejidad de la sonda celular en 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 )) tiempo para ejecutar m Hallazgos y n −1 Uniones, comenzando con n conjuntos singleton.
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.
8. Anderson, Richard J.; Woll, Heather (1994). Algoritmos paralelos sin espera para el problema de búsqueda de unión . 23.° Simposio ACM sobre teoría de la computación. págs. 370–380.
9. Conchon, Sylvain; Filliâtre, Jean-Christophe (octubre de 2007). "Una estructura de datos persistente de búsqueda de unión". Taller ACM SIGPLAN sobre ML. 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
11. 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 edición). MIT Press. págs. 571–572. ISBN 978-0-262-03384-8.
12. Raimund Seidel , Micha Sharir. "Análisis de arriba hacia abajo de la compresión de trayectorias", SIAM J. Comput. 34(3):515–525, 2005
13. 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.
14. Hopcroft, JE; Ullman, JD (1973). "Algoritmos de fusión de conjuntos". Revista SIAM de informática . 2 (4): 294–303. doi :10.1137/0202024.
15. Robert E. Tarjan y Jan van Leeuwen . Análisis del peor caso de algoritmos de unión de conjuntos. Journal of the ACM, 31(2):245–281, 1984.
16. Blum, Norbert (1985). "Sobre la complejidad temporal del peor caso 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). "Optimidad en el peor de los casos y amortizada en union-find (Resumen ampliado)". 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.S2CID100111  .​
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-eliminación". Ciencias de la computación teórica . 412 (4–5): 487–492. doi :10.1016/j.tcs.2010.11.005.
20. Knight, Kevin (1989). "Unificación: un estudio multidisciplinario" (PDF) . Encuestas de computación de la ACM . 21 : 93–124. doi :10.1145/62029.62030. S2CID  14619034.

Enlaces externos

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