En informática , una estructura de datos de conjuntos disjuntos , también denominada estructura de datos de unión-búsqueda o conjunto de combinació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 separados . 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 averiguar de manera eficiente si dos elementos están en el mismo conjunto o en conjuntos diferentes.
Bosque disjoint-set / Union-find | |||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Tipo | árbol de múltiples vías | ||||||||||||||||
Inventado | 1964 | ||||||||||||||||
Inventado por | Bernard A. Galler y Michael J. Fischer | ||||||||||||||||
Complejidad del tiempo en notación O grande | |||||||||||||||||
|
Si bien hay 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 . Este es un tipo de bosque especializado que realiza uniones y se 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 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 búsqueda y unión individuales pueden tardar más que una constante por tiempo α ( 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 juegan 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ínimos 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 para 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, su complejidad temporal se limitó a, el logaritmo iterado de, por Hopcroft y Ullman . [3] En 1975, Robert Tarjan fue el primero en demostrar la( función de Ackermann inversa ) límite superior en la complejidad temporal del algoritmo, [4] y, en 1979, mostró que este era el límite inferior para un caso restringido. [5] En 1989, Fredman y Saks demostraron queLas palabras (amortizadas) deben ser accedidas por cualquier estructura de datos de conjuntos disjuntos por operación, [6] probando así la optimalidad de la estructura de datos.
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 persistente de la estructura de datos del bosque de conjuntos disjuntos, lo que permitió retener de manera eficiente versiones anteriores de la estructura y formalizaron su corrección utilizando el asistente de pruebas Coq . [9] Sin embargo, la implementación solo es asintótica si se usa de manera efímera o si la misma versión de la estructura se usa repetidamente con un retroceso limitado.
Representación
Cada nodo de un bosque de conjuntos disjuntos consta de un puntero y alguna información auxiliar, ya sea un tamaño o un rango (pero no ambos). Los punteros se utilizan para hacer árboles de punteros padre , 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, 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 en el bosque se pueden almacenar de cualquier forma conveniente para 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 matriz requiere un mínimo de O (lg 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 el número de bits necesarios para almacenar el bosque es O ( n lg 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.
Haciendo nuevos conjuntos
La operación MakeSet agrega un nuevo elemento. Este elemento se coloca en un nuevo conjunto que contiene solo el nuevo elemento, y el nuevo conjunto se agrega a la estructura de datos. Si la estructura de datos se ve en cambio como una partición de un conjunto, entonces la operación MakeSet amplía el conjunto agregando el nuevo elemento y extiende la partición existente al colocar el nuevo elemento en un nuevo subconjunto que contiene solo el nuevo elemento.
En un bosque de conjuntos disjuntos, MakeSet inicializa 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 usando el siguiente pseudocódigo:
function 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 end if end function
Esta operación tiene una complejidad de tiempo constante. En particular, la inicialización de un bosque de conjuntos disjuntos con n nodos requiere O ( n ) tiempo.
En la práctica, MakeSet debe 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 conjuntos aleatorios.
Encontrar representantes de conjuntos
La operación Find sigue la cadena de punteros principales 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 . Find devuelve el elemento raíz que alcanza.
Realizar una operación Find presenta una oportunidad importante para mejorar el bosque. El tiempo en una operación de búsqueda se dedica a perseguir punteros principales, por lo que un árbol más plano conduce a operaciones de búsqueda más rápidas . Cuando se ejecuta una búsqueda , 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 apuntar más cerca de la raíz. Debido a que cada elemento visitado en el camino a una raíz es parte del mismo conjunto, esto no cambia los conjuntos almacenados en el bosque. Pero hace que las operaciones de búsqueda 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 desempeño amortizado del bosque disjunto.
Hay varios algoritmos para Find que logran la complejidad de tiempo óptima asintóticamente. 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 usando una recursividad simple de la siguiente manera:
función Find ( x ) es si x .parent ≠ x entonces x .parent: = Find ( x .parent) return x .parent else return x end if end function
Esta implementación hace 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 camina desde el nodo de consulta a la raíz dos veces, una para encontrar la raíz y otra para actualizar los punteros:
la función Find ( x ) es root : = x while root .parent ≠ root do root : = root .parent end while while x .parent ≠ root do parent : = x .parent x .parent: = root x : = parent end while devolver la función de fin de raíz
Tarjan y Van Leeuwen también desarrollaron algoritmos de búsqueda de un solo paso que 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 división de ruta a la mitad. 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:
función Find ( x ) es while x .parent ≠ x do ( x , x .parent): = ( x .parent, x .parent.parent) end while return x end 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 while x .parent ≠ x do x .parent: = x .parent.parent x : = x .parent end while return x end función
Fusionando dos conjuntos
La operación Unión ( x , y ) reemplaza el conjunto que contiene x y el conjunto que contiene y con su unión. Unión primeros usos Buscar para determinar las raíces de los árboles que contienen 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 realiza ya sea estableciendo el puntero del padre de X a Y , o establecer el puntero de matriz de y para x .
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 de manera descuidada, los árboles pueden volverse excesivamente altos. Por ejemplo, suponga que Union siempre hizo que el árbol que contiene x sea un subárbol del árbol que contiene y . Comience con un bosque que se acaba de inicializar con los elementos 1, 2, 3, ..., n , y ejecute Union (1, 2) , Union (2, 3) , ..., Union ( n - 1, n ) . El bosque resultante contiene un solo árbol cuya raíz es n , y la ruta de 1 an pasa por todos los nodos del árbol. Para este bosque, el tiempo para ejecutar Find (1) es O ( n ) .
En una implementación eficiente, la altura del árbol se controla mediante unión por tamaño o unión por rango . Ambos requieren que un nodo almacene 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 se vuelvan demasiado profundos.
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 x e y se fusionan, el nodo con más descendientes 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 Union ( x , y ) es // Reemplazar nodos por raíces x : = Find ( x ) y : = Find ( y ) si x = y entonces devuelve // xey ya están en el mismo conjunto end if // Si es necesario, cambie el nombre de las variables para asegurarse de que // x tenga al menos tantos descendientes como y si x .size < y .size then ( x , y ): = ( y , x ) end if // Hacer x la nueva raíz y .parent: = x // Actualizar el tamaño de x x .size: = x .size + y .size end función
El número de bits necesarios para almacenar el tamaño es claramente el número de bits necesarios para almacenar n . Esto agrega un factor constante al almacenamiento requerido por el bosque.
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 combinar árboles con raíces x e y , en primer lugar comparar sus filas. Si las filas son diferentes, entonces el árbol rango más grande se convierte en el padre, y las filas de X e Y no cambian. Si los rangos son los mismos, entonces 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 operación de búsqueda , 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 Union ( x , y ) es // Reemplazar nodos por raíces x : = Find ( x ) y : = Find ( y ) si x = y entonces devuelve // xey ya están en el mismo conjunto end if // Si es necesario, cambie el nombre de las variables para asegurarse de que // x tenga un rango al menos tan grande como el de y si x .rank < y .rank then ( x , y ): = ( y , x ) end if // Hacer 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 end if end función
Se puede demostrar que cada nodo tiene rango ⌊lg n ⌋ o menos. [10] En consecuencia, el rango se puede almacenar en O (log log n ) bits, lo que lo convierte en 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 un nodo sea la raíz de un árbol. Una vez que un nodo se convierte en un niño, nunca se vuelve a acceder a su tamaño y rango.
Complejidad del tiempo
Una implementación de bosque de conjuntos disjuntos en la que Find no actualiza los punteros principales y en la que Union no intenta controlar las alturas de los árboles, puede tener árboles con una altura O ( n ) . En tal situación, las operaciones de búsqueda y unión requieren O ( n ) tiempo.
Si una implementación usa solo la compresión de ruta, entonces una secuencia de n operaciones MakeSet , seguidas de hasta n - 1 operaciones Union yf operaciones Find , tiene un tiempo de ejecución en el peor de los casos de. [10]
El uso de unión por rango, pero sin actualizar los punteros principales durante la búsqueda , da un tiempo de ejecución depara m operaciones de cualquier tipo, hasta n de las cuales son operaciones MakeSet . [10]
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 operaciones MakeSet , para. [4] [5] Esto hace que el tiempo de ejecución amortizado de cada operación. Esto es asintóticamente óptimo, lo que significa que cada estructura de datos de conjuntos disjuntos debe utilizartiempo amortizado por operación. [6] Aquí, la funciónes la función inversa de Ackermann . La función de Ackermann inversa 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 un tiempo constante.
Prueba de O (log * (n)) complejidad de tiempo de Union-Find
El análisis preciso del desempeño de un bosque disjunto es algo complicado. Sin embargo, hay un análisis mucho más simple que demuestra que el tiempo amortizado para cualquier operación m Find o Union en un bosque de conjuntos disjuntos que contiene n objetos es O (mlog * n ) , donde log * denota el logaritmo iterado . [11] [12] [13] [14]
Lema 1: A medida que la función de búsqueda sigue el camino a lo largo de la raíz, el rango de nodo que encuentra aumenta.
- Prueba: afirme 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 menor rango se adjuntará a un árbol con mayor rango, en lugar de viceversa. 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 2 r nodos.
- Prueba: inicialmente, cuando cada nodo es la raíz de su propio árbol, es trivialmente cierto. Suponga que un nodo u con rango r tiene al menos 2 r nodos. Luego, cuando dos árboles con rango r se unen por rango y forman un árbol con rango r + 1, el nuevo nodo 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 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 n / 2 r
Por conveniencia, definimos "depósito" aquí: un depósito es un conjunto que contiene vértices con rangos particulares.
Creamos algunos cubos y colocamos vértices en los cubos de acuerdo con 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 depósito Bth contiene vértices con rangos del intervalo [ r , 2 r - 1] = [r, R - 1], entonces el depósito (B + 1) st contendrá vértices con rangos del intervalo [R, 2 R - 1] .
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 depósito al siguiente, sumamos uno más dos a la potencia, es decir, el próximo depósito a [ B , 2 B - 1] será [2 B , 2 2 B - 1]
- El número máximo de elementos en el segmento [ B , 2 B - 1] es como máximo 2 n / 2 B
- Prueba: el número máximo de elementos en el cubo [ B , 2 B - 1] es como máximo n / 2 B + n / 2 B +1 + n / 2 B +2 + ... + n / 2 2 B - 1 ≤ 2 n / 2 B
Sea F la lista de operaciones de "búsqueda" realizadas, y sea
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, desde el límite anterior en el número de cubos, tenemos T 2 = O ( m log * n ).
Para T 3 , supongamos que estamos atravesando una ventaja 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 desplazamiento, de lo contrario el recorrido haría ser contabilizado en T 1 ). Fije uy considere la secuencia v 1 , v 2 , ..., v k 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 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 aumentan estrictamente. 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 está conectado a una raíz diferente en el mismo depósito) es como máximo el número de rangos en los depósitos B , es decir como máximo 2 B - 1 - B <2 B .
Por lo tanto,
De las observaciones 1 y 2 , podemos concluir que
Por lo tanto, T = T 1 + T 2 + T 3 = O ( m log * n ).
Aplicaciones
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 usar para determinar si dos vértices pertenecen al mismo componente, o si agregar un borde entre ellos daría como resultado un ciclo. El algoritmo Union-Find se utiliza en implementaciones de unificación de alto rendimiento . [15]
Esta estructura de datos es utilizada por Boost Graph Library para implementar su funcionalidad Incremental Connected Components . 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.
Tenga en cuenta que la implementación como bosques de conjuntos disjuntos no permite la eliminación de bordes, incluso sin compresión de ruta o heurística de rango.
Sharir y Agarwal informan conexiones entre el peor comportamiento de los conjuntos disjuntos y la longitud de las secuencias de Davenport-Schinzel , una estructura combinatoria de geometría computacional. [dieciséis]
Ver también
- Refinamiento de particiones , una estructura de datos diferente para mantener conjuntos disjuntos, con actualizaciones que dividen los conjuntos en lugar de fusionarlos.
- Conectividad dinámica
Referencias
- ↑ a b c d e f 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 bosques desarticulados.
- ^ 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, Jan (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 .
- ^ a b Tarjan, Robert Endre (1979). "Una clase de algoritmos que requieren un tiempo no lineal para mantener conjuntos disjuntos". Revista de Ciencias de la Computación y Sistemas . 18 (2): 110-127. doi : 10.1016 / 0022-0000 (79) 90042-4 .
- ^ a b 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 computación : 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's y n −1 Union's, 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 Union-Find . 23º Simposio ACM sobre Teoría de la Computación. págs. 370–380.
- ^ Conchon, Sylvain; Filliâtre, Jean-Christophe (octubre de 2007). "Una estructura de datos de búsqueda de unión persistente". Taller ACM SIGPLAN sobre ML . Friburgo, Alemania.
- ^ 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 caminos", 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.
- ^ Caballero, Kevin (1989). "Unificación: una encuesta multidisciplinar" (PDF) . Encuestas de computación ACM . 21 : 93-124. doi : 10.1145 / 62029.62030 . S2CID 14619034 .
- ^ Sharir, M .; Agarwal, P. (1995). Secuencias de Davenport-Schinzel y sus aplicaciones geométricas . Prensa de la Universidad de Cambridge.
enlaces externos
- Implementación de C ++ , parte de las bibliotecas de Boost C ++
- Una implementación de Java con una aplicación para la segmentación de imágenes en color, Fusión de regiones estadísticas (SRM), IEEE Trans. Patrón Anal. Mach. Intell. 26 (11): 1452–1458 (2004)
- Subprograma de Java: Implementación de búsqueda de unión gráfica , por Rory LP McGuire
- Una implementación de Matlab que forma parte de la biblioteca de componentes de Tracker
- Implementación de Python
- Explicación visual y código C #