Vistas de página en total

lunes, 17 de marzo de 2014

ESTRUCTURAS DE DATOS

UNION-FIND

O también llamado Disjoint-Set(Conjuntos Disjuntos), esta estructura de datos nos ayuda a particionar de alguna forma que nos convenga una serie de conjuntos que un principio todos están disjuntos(separados) vamos a verlo gráficamente.


Podemos ver que los 4 nodos están separados esa sería la definición de conjuntos disjuntos en teoría de grafos.
Pero, ¿para que nos puede ayudar esta estructura de datos?
Hace un tiempo en el club de algoritmia se nos dio a la tarea de resolver un problema con esta estructura y consistía en lo siguiente...
Existía una red social en la cual podías hacer amistad con alguna persona y esa persona podía hacer amistad con otra y al mismo tiempo tu podías hacer amistad con otra, básicamente todos podían ser amigos de todos. Entonces nos daban un número n que era el número de amistades que podían surgir, y para cada n teníamos que dar el nombre de las dos personas que se volvían amigos por ejemplo:
Definiremos a
q0 = Beto
q1 = Elisa
q2 = Esteban
q3 = Pedro
q4 = Estefany
q5 = Ivan
en un inicio todos en el conjunto todos son padre de sí mismos.



Con n = 3
Beto Elisa
Esteban Pedro
Ivan Estefany

después de formar las redes sociales:



Y lo que teníamos que decir era de que tamaño hasta ese momento con esas personas, que se volvieron amigos, era la red social. Para el caso anterior las respuestas serían:
Personas          Respuesta
Beto Elisa              2
Esteban Pedro        2
Ivan Estefany         2

¿Pero porque dos? Bien pues en un principio la unión de dos personas forma una red de tamaño 2 y ninguna de las uniones de personas en cada consulta se volvió amigo de otra red social, para entenderlo mejor pondré otro ejemplo:
Personas          Respuesta
Beto Elisa              2
Esteban Pedro        2
Elisa Estefany         3



En este caso Beto y Elisa formaron una red de 2 personas pero después Elisa se volvió amiga de Estefany entonces la red que era de dos personas agregó a su conjunto otra persona entonces se volvió una red total de 3 personas.
Y así sucesivamente se iban agregando conjuntos a otros conjuntos para más información sobre el problema pueden ver acá
Pero como resolverlo, es aquí donde entra la magia de esta estructura de datos Disjoint Set y el algoritmo de Union Find.

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
  • Unión: Une dos subconjuntos en uno solo.

Para ello entonces tendremos dos funciones importantes la de calcular raíz del conjunto que analicemos y la de unión y en c estarán implementadas de la siguiente manera:
Primero tendremos un arreglo llamado padre donde el índice i es el conjunto y el contenido en el indice i es su raíz o su padre.

padre[]    1   2   3   4   5   //Nótese que al inicio el padre de cada conjunto es si mismo
raiz         1   2   3   4   5   // porque cada uno forma un conjunto por si solo

Para la raíz

int raiz(int a){//Devolvera un entero para saber cual es la raiz y recibe el numero del que se quiere calcular su raiz
   if(padre[a] != a)//Si el padre de ese numero a su contenido quiere decir que esa no es su raiz
      return padre[a] = raiz(padre[a]); //Y en esa posicion se guarda el contenido del padre y se calcula recursivamente hasta que el padre de 'a' sea igual a 'a'
   return a;//y se regresa a 'a'
}

Para la unión:

void une(int a, int b){//Se reciben los dos números a unir
   raizA = raiz(a);//Se calcula la raiz de a y se guarda en raizA
   raizB = raiz(b);//Se calcula la raiz de b y se guarda en raizB
   padre[raizA] = raizB;//La raiz de b o raizB se convierte en el nuevo padre de a o raizA }

Esta función es muy interesante porque recibe los dos números que se quieren unir y se calculan sus raices y se guardan en dos variables raizA y raizB una para cada número y en el arreglo de padres en la posición de la raiz de a se guarda la raiz de b entonces el padre de b pasa a ser el padre de a y así se une dicho conjunto. Su complejidad es O(nlogn).

Por esta sesión es todo y sugiero si quieres entender mejor como funciona esta sensacional estructura de datos en este algoritmo agarres lápiz y papel y hagas tus pruebas de escritorio que en verdad sirven y notes como funciona. ¡Hasta la próxima!
 

Ya saben si tienen dudas escríbanme a adrian.ipod25@gmail.com. Visitenme en Twitter @ferprogramming. Saludos.