Estructura de datos para conjuntos disjuntos

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En computación, una estructura de datos para conjuntos disjuntos, es una estructura de datos que mantiene un conjunto de elementos particionados en un número de conjuntos disjuntos(no se solapan los conjuntos).Un algoritmo Unión-Buscar es un algoritmo que realiza dos importantes operaciones en esta estructura de datos:

  • Buscar: Determina a cual subconjunto pertenece un elemento. Esta operación puede usarse para verificar si dos elementos están en el mismo conjunto.
  • Union: Une dos subconjuntos en uno solo.

La otra operación importante CrearConjunto es generalmente trivial, esta crea un conjunto con un elemento dado. Con estas tres operaciones, muchos problemas prácticos de particionamiento pueden ser resueltos(ver la sección de Aplicaciones).

Con el fin de definir estas operaciones más precisamente , es necesario representar los conjuntos de alguna manera. Un aproximamiento común es seleccionar un elemento fijo de cada conjunto , llamado el representativo, para representar el conjunto como un todo. Entonces Buscar(x) retorna el elemento representativo del conjunto al cuál x pertenece , y Unión toma como argumento dos elementos representivos de dos conjuntos respectivamente.

Listas Enlazadas de Conjuntos Disjuntos[editar]

Un simple acercamiento para crear una estructura de datos para conjuntos disjuntos es crear una lista enlazada para cada conjunto. El elemento en la cabeza de cada lista enlazada se escoge como elemento representativo.

CrearConjunto crea una lista con un solo elemento. Unión concatena dos listas , una operación en tiempo constante. El problema de esta implementación es que Buscar(x) requiere Ω(n) u orden lineal para recorrer de atrás hacia adelante, desde el elemento dado hasta la cabeza de la lista.

Esto puede ser evitado añadiendo a cada nodo de la lista enlazada un puntero a la cabeza de la lista; por tanto Buscar toma tiempo constante. Pero ahora Unión ahora tiene que actualizar a cada elemento de la lista que está siendo concatenada una referencia a la cabeza de la nueva lista combinada, requiriendo Ω(n) tiempo.

Cuando sabemos la longitud de cada lista, el tiempo requerido puede ser mejorado concatenando siempre la lista de menor longitud a la de mayor longitud. Usando esta heurística llamada weighted-union, una secuencia de m operaciones de CrearConjunto, Unión y Buscar sobre n elementos requiere O(m + nlog n) tiempo.[1] Para operaciones asintóticamente más rápidas otra estructura de datos es necesaria.

Análisis de este acercamiento simple[editar]

Ahora explicaremos el tiempo O(n \log(n)) de arriba. Supongamos que tenemos una colección de listas, cada nodo de la lista contiene un objeto, el nombre de la lista a la cual pertenece, y el número de elementos de esa lista. También asumamos que la suma de todos los elementos de todas las listas es n (por tanto existen n elementos). Quisiéramos poder mezclar cualquiera dos de estas listas, y actualizar todos sus nodos para que sigan teniendo el nombre de la lista a la que pertenecen. La regla para mezclar las listas A y B es que, si A es mayor que B entonces se añaden los de B en A y se actualizan los elementos que pertenecen a B, y viceversa.

Escoger un elemento arbitrario de la lista L, digamos x. Quisiéramos contar en el peor caso cuántas veces el elemento x va a necesitar actualizar el nombre de la lista a la cuál pertenece. El elemento x solo va a actualizar su nombre cuando la lista a la cuál pertenece es mezclada con una lista del mismo o mayor tamaño. Cada momento que pase esto , el tamaño de la lista de x al menos se dobla. Entonces finalmente, la pregunta es ¿Cuántas veces puede un número doblar su tamaño antes de que llegue a n? (entonces la lista de x tiene tamaño n). La respuesta exacta es \log_2(n). Entonces para cualquier elemento en cualquier lista en la estructura descrita, será necesario actualizar \log_2(n) veces en el peor de los casos. Por tanto actualizar una lista de n elementos almacenados de esta manera tomaría O(n \log(n)) tiempo en el peor caso. Una operación de búsqueda se puede realizar en O(1) en esta estructura pues todos los nodos contienen el nombre de la lista a la cual pertenecen.

Un argumento similar se mantienen para mezclar los árboles de las estructuras de datos discutidas más abajo, adicionalmente ayuda a explicar el análisis de tiempo de algunas operaciones sobre las estructuras de datos Binomial Heap y Fibonacci Heap.

Bosques de Conjuntos-Disjuntos[editar]

Los Bosques de Conjuntos-Disjuntos son estructuras de datos donde cada conjunto está representado por un árbol , en el cual cada nodo mantiene una referencia a su nodo padre (ver pila espagueti). Estos fueron descritos primeros por Bernard A. Galler y Michael J. Fisher en 1964,[2] tomando años para su preciso análisis.

En los Bosques de Conjuntos-Disjuntos, el representativo de cada conjunto es la raíz del árbol el cual representa el conjunto. Buscar sigue por los padres nodos hasta encontrar la raíz del árbol. Unión combina dos árboles en uno añadiendo la raíz de uno en la raíz del otro. Una manera de implementar esto puede ser:

 function CrearConjunto(x)
     x.padre := x
 function Buscar(x)
      if x.padre == x
         return x
      else

return Buscar(x.padre)

 function Unión(x,y)
     xRaíz := Buscar(x)
     yRaíz := Buscar(y)
     xRaíz.padre := yRaíz

En esta simple forma, este implementación no es mejor que la implementación basada en listas enlazadas, porque el árbol que se crea puede ser muy desbalanceado; de todas maneras , esto puede ser mejorado de dos formas.

La primera forma, se llama unión por rank, consiste en siempre añadir el árbol más pequeño a la raíz del árbol más grande. Como la profundidad del árbol afecta el tiempo de ejecución del algoritmo, el árbol con menor profundidad es añadido a la raíz del árbol con mayor profundidad, el cual aumenta su profundidad solo si sus profundidades son iguales. En el contexto de este algoritmo, el término rank se usa en vez de profundidad porque este deja de ser igual a la profundidad si se usa la compresión de camino (descrita más abajo). Los árboles con un solo elemento tienen rank igual a cero, y cualquiera dos árboles del mismo rank r son combinados, el rank resultante es r+1. Solo aplicando esta técnica obtenemos en el peor caso un tiempo de ejecución de O(\log n) para las operaciones CrearConjunto, Unión y Buscar. Pseudocódigo del CrearConjunto y Unión mejorado:

 function CrearConjunto(x)
     x.padre := x
     x.rank  := 0
 function Unión(x, y)
     xRaíz := Buscar(x)
     yRaíz := Buscar(y)
     if xRaíz == yRaíz
        return
     //Ya que no están en el mismo conjunto, se unen.
     if xRaíz.rank < yRaíz.rank
        xRaíz.padre := yRaíz
     else if xRaíz.rank > yRaíz.rank
        yRaíz.padre := xRaíz
     else
        yRaíz.padre := xRaíz
        xRaíz.rank := xRaíz.rank + 1

La segunda mejora, llamada compresión de camino, es una forma de aplanar la estructura del árbol cuando se aplique Buscar. La idea es que cada nodo visitado en el camino hacia la raíz puede ser añadido directamente a la raíz; todos ellos comparten el mismo representativo. Para lograr este efecto, mientras Buscar recursivamente se mueve hacia la raíz, este cambia la referencia del padre del nodo a la raíz que encuentre. El árbol resultante es más aplanado, acelerando operaciones futuras no solo en estos elementos sino también en aquellos que referencian a estos. Aquí va el Buscar mejorado:

 function Buscar(x)
     if x.padre != x
        x.padre:= Buscar(x.padre)
     return x.padre

Estas dos técnicas se complementan una a otra; aplicadas juntas, el tiempo amortizado es solo O(\alpha(n)), donde \alpha(n) es la inversa de la función n = f(x) = A(x,x), y A es la función de Ackermann. Como \alpha(n) es la inversa de esta función, \alpha(n) es menor que 5 para todos los prácticamente remotos valores de n. Por tanto el tiempo de ejecución amortizado es efectivamente una pequeña constante.

Aplicaciones[editar]

Las estructuras de datos para conjuntos disjuntos modelan el particionamiento de conjuntos, por ejemplo las componentes conexas de un grafo no dirigido. Este modelo también puede utilizarse para verificar si dos vértices pertenecen a una misma componente conexa, o para comprobar si al añadir una arista entre dos vértices se forma un ciclo. El algoritmo Unión-Buscar es usado en implementaciones muy eficientes de Unificación.[3]

Esta estructura de datos es usada por la librería Boost Graph Library para implementar su funcionalidad de Componentes Conexas Incrementales. También es usado es la implementación del algoritmo de Kruskal para hallar el árbol abarcador de costo mínimo de un grafo.

Historia[editar]

Mientras que las ideas usadas en conjuntos disjuntos son bien familiar, Robert Tarjan fue el primero en demostrar la cota superior (y la versión restricta de la cota inferior) en términos de la función de Ackermann en 1975.[4] Hasta este momento la mejor cota lograda por operación demostrada por Hopcroft y Ullman,[5] era O(log(*n)), el logaritmo iterado de n, otra función que crece muy lento (pero no tanto como la inversa de la función de Ackermann).

Tarjan y Van Leeuwen implementaron también algoritmos de Buscar en una sola pasada manteniendo la misma complejidad computacional en el peor de los casos.[6]


Referencias[editar]

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw–Hill, 2001. ISBN 0-262-03293-7. Chapter 21: Data structures for Disjoint Sets, pp. 498–524.
  2. Bernard A. Galler and Michael J. Fischer. An improved equivalence algorithm. Communications of the ACM, Volume 7, Issue 5 (May 1964), pp. 301–303. The paper originating disjoint-set forests. ACM Digital Library
  3. Knight, Kevin (1989). «Unification: A multidisciplinary survey». ACM Computing Surveys 21:  pp. 93–124. doi:10.1145/62029.62030. http://portal.acm.org/citation.cfm?id=62030. 
  4. Tarjan, Robert Endre (1975). «Efficiency of a Good But Not Linear Set Union Algorithm». Journal of the ACM 22 (2):  pp. 215–225. doi:10.1145/321879.321884. http://portal.acm.org/citation.cfm?id=321884. 
  5. Hopcroft, J. E.; Ullman, J. D. (1973). «Set Merging Algorithms». SIAM Journal on Computing 2 (4):  pp. 294–303. doi:10.1137/0202024. 
  6. Robert E. Tarjan and Jan van Leeuwen. Worst-case analysis of set union algorithms. Journal of the ACM, 31(2):245–281, 1984.

Enlaces externos[editar]