S09_EDNoLineales_ConjuntosDisjuntos.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "3c7952f3-c2f8-4579-8d7e-d1be0d9ea2f8",
   "metadata": {},
   "source": [
    "<h1 align=\"center\">Estructura de Datos y Algoritmos I</h1>\n",
    "<h1 align=\"center\">Estructuras de Datos No Lineales - Conjuntos Disjuntos</h1>\n",
    "<h1 align=\"center\">2024</h1>\n",
    "<h1 align=\"center\">MEDELLÍN - COLOMBIA </h1>"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "249ac896",
   "metadata": {},
   "source": [
    "*** \n",
    "|[![Outlook](https://img.shields.io/badge/Microsoft_Outlook-0078D4?style=plastic&logo=microsoft-outlook&logoColor=white)](mailto:calvar52@eafit.edu.co)||[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/carlosalvarezh/EstructuraDatosAlgoritmos1/blob/main/S09_EDNoLineales_ConjuntosDisjuntos.ipynb)\n",
    "|-:|:-|--:|\n",
    "|[![LinkedIn](https://img.shields.io/badge/linkedin-%230077B5.svg?style=plastic&logo=linkedin&logoColor=white)](https://www.linkedin.com/in/carlosalvarez5/)|[![@alvarezhenao](https://img.shields.io/twitter/url/https/twitter.com/alvarezhenao.svg?style=social&label=Follow%20%40alvarezhenao)](https://twitter.com/alvarezhenao)|[![@carlosalvarezh](https://img.shields.io/badge/github-%23121011.svg?style=plastic&logo=github&logoColor=white)](https://github.com/carlosalvarezh)|\n",
    "\n",
    "<table>\n",
    " <tr align=left><td><img align=left src=\"https://github.com/carlosalvarezh/Curso_CEC_EAFIT/blob/main/images/CCLogoColorPop1.gif?raw=true\" width=\"25\">\n",
    " <td>Text provided under a Creative Commons Attribution license, CC-BY. All code is made available under the FSF-approved MIT license.(c) Carlos Alberto Alvarez Henao</td>\n",
    "</table>\n",
    "\n",
    "***"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2a06d440",
   "metadata": {},
   "source": [
    "## Conjuntos Disjuntos"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b4247eb",
   "metadata": {},
   "source": [
    "### Introducción"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "eda19b24",
   "metadata": {},
   "source": [
    "Dos conjuntos se denominan disjuntos si no comparten ningún elemento en común; es decir, su intersección es el conjunto vacío.\n",
    "\n",
    "Una estructura de datos que almacena subconjuntos no superpuestos o disjuntos de elementos se llama estructura de datos de conjuntos disjuntos. Esta estructura de datos admite las siguientes operaciones:\n",
    "\n",
    "- Añadir nuevos conjuntos al conjunto disjunto.\n",
    "- Fusionar conjuntos disjuntos en un único conjunto disjunto mediante la operación Unión.\n",
    "- Encontrar un representante del conjunto disjunto mediante la operación Búsqueda.\n",
    "- Verificar si dos conjuntos son disjuntos o no.\n",
    "\n",
    "Imagina una situación con varias personas y las siguientes tareas para realizar entre ellas:\n",
    "\n",
    "- Añadir una nueva relación de amistad, es decir, que una persona $x$ se convierta en amiga de otra persona $y$, lo que implica añadir un nuevo elemento a un conjunto.\n",
    "- Determinar si el individuo $x$ es amigo del individuo $y$ (amigo directo o indirecto)."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e07afeb",
   "metadata": {},
   "source": [
    "***Ejemplo:***\n",
    "\n",
    "Supongamos que tenemos 10 individuos, denominados a, b, c, d, e, f, g, h, i, j.\n",
    "\n",
    "Las siguientes son las relaciones de amistad que se deben agregar:\n",
    "```pseudocode\n",
    "a <-> b  \n",
    "b <-> d\n",
    "c <-> f\n",
    "c <-> i\n",
    "j <-> e\n",
    "g <-> j\n",
    "```\n",
    "Dadas consultas como si a es amigo de d o no, lo que necesitamos básicamente es crear los siguientes 4 grupos y mantener una conexión rápidamente accesible entre los elementos del grupo:\n",
    "\n",
    "```pseudocode\n",
    "G1 = {a, b, d}\n",
    "G2 = {c, f, i}\n",
    "G3 = {e, g, j}\n",
    "G4 = {h}\n",
    "```\n",
    "Cada grupo representa un conjunto de individuos entre los cuales todos son amigos directos o indirectos. Así, al consultar si dos personas son amigas, simplemente necesitamos verificar si están en el mismo grupo.\n",
    "\n",
    "Para averiguar si $x$ e $y$ están en el mismo grupo, es decir, para determinar si son amigos directos o indirectos, empleamos un método conocido como la *Unión de Conjuntos Disjuntos*. Este método mantiene una colección de conjuntos disjuntos y cada conjunto está representado por uno de sus integrantes.\n",
    "\n",
    "Para responder la pregunta sobre si dos personas pertenecen al mismo grupo, se deben tener en cuenta dos puntos clave:\n",
    "\n",
    "**¿Cómo resolver los conjuntos?** Inicialmente, cada elemento pertenece a un conjunto diferente. Tras aplicar las relaciones dadas, elegimos un miembro como representante del conjunto. Hay varias formas de seleccionar un representante; una manera simple es escoger al miembro con el índice más alto.\n",
    "\n",
    "**¿Cómo comprobar si dos personas están en el mismo grupo?** Si los representantes de dos individuos son iguales, entonces están en el mismo conjunto, lo cual indica que son amigos, ya sea de manera directa o indirecta."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8cfdf7c2",
   "metadata": {},
   "source": [
    "### Estructuras de datos empleadas"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "81c282a0",
   "metadata": {},
   "source": [
    "Las estructuras de datos utilizadas son:\n",
    "\n",
    "- **Array**: Un arreglo de enteros se denomina `Parent[]`. Si estamos tratando con $N$ elementos, el $i$-ésimo elemento del arreglo representa al $i$-ésimo artículo. Más precisamente, el $i$-ésimo elemento del arreglo `Parent[]` es el padre del $i$-ésimo artículo. Estas relaciones crean uno o más árboles virtuales.\n",
    "\n",
    "- **Árbol**: Es un conjunto disjunto. Si dos elementos están en el mismo árbol, entonces están en el mismo conjunto disjunto. El nodo raíz (o el nodo superior) de cada árbol se llama el *representante del conjunto*. Siempre hay un único representante único para cada conjunto. Una regla simple para identificar a un representante es: si $i$ es el representante de un conjunto, entonces `Parent[i] = i`. Si $i$ no es el representante de su conjunto, entonces se puede encontrar viajando hacia arriba en el árbol hasta que encontremos al representante."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "533b2420",
   "metadata": {},
   "source": [
    "### Operaciones en Estructuras de Datos de Conjuntos Disjuntos"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ba672367",
   "metadata": {},
   "source": [
    "#### Buscar (Find)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f1f934e0",
   "metadata": {},
   "source": [
    "Esta operación tiene como objetivo identificar el conjunto al que pertenece un elemento particular. En términos de la estructura del árbol, se trata de encontrar el representante o la raíz del conjunto al que pertenece un elemento.\n",
    "   - Si cada elemento se representa en un arreglo, `Find` consiste en seguir los enlaces de padres hasta llegar al representante del conjunto. Este es el elemento para el cual el valor en el arreglo `Parent[]` es igual a su propio índice (es decir, `Parent[i] = i`).\n",
    "   - En una implementación optimizada, `Find` también puede incluir una compresión de caminos. Durante la búsqueda del representante, esta técnica aplanará la estructura del árbol haciendo que cada nodo apunte directamente al representante, lo que acelera futuras operaciones de búsqueda en los mismos elementos."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b37d27cb",
   "metadata": {},
   "source": [
    "#### Unir (Union)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "31611079",
   "metadata": {},
   "source": [
    "`Union` es la operación que combina dos conjuntos disjuntos en uno solo. Esto se logra conectando los árboles de dos elementos que no están en el mismo conjunto.\n",
    "   - El procedimiento usual implica primero encontrar los representantes (o raíces) de los conjuntos de los dos elementos. Luego, uno de estos representantes se hace padre del otro, efectivamente fusionando los dos árboles en uno. Si se utiliza unión por rango, el árbol más pequeño se une debajo del más grande para mantener la estructura de árbol equilibrada.\n",
    "   - Un aspecto importante de `Union` es que sólo se realiza si los elementos están en conjuntos diferentes. Si ya están en el mismo conjunto, no es necesario realizar la unión."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fefd1df6",
   "metadata": {},
   "source": [
    "#### Ejemplo: Unión de Conjuntos y Operación Find"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9b695cd2",
   "metadata": {},
   "source": [
    "Volviendo al ejemplo de los 10 individuos (a, b, c, d, e, f, g, h, i, j) y sus relaciones de amistad, se mostrará cómo funcionaría la operación `Find` en una estructura de conjuntos disjuntos. \n",
    "\n",
    "Recordemos que se establecieron las siguientes relaciones:\n",
    "\n",
    "- a <-> b, b <-> d (formando el grupo G1 = {a, b, d})\n",
    "- c <-> f, c <-> i (formando el grupo G2 = {c, f, i})\n",
    "- e <-> j, g <-> j (formando el grupo G3 = {e, g, j})\n",
    "- h está solo (formando el grupo G4 = {h})\n",
    "\n",
    "Supongamos que queremos determinar el representante del grupo al que pertenece el individuo `d` usando la operación `Find`.\n",
    "\n",
    "1. **Inicialización**:\n",
    "    - Comenzamos con 10 individuos: a, b, c, d, e, f, g, h, i, j.\n",
    "    - Cada uno es inicialmente su propio representante, por lo que `parent[a] = a`, `parent[b] = b`, y así sucesivamente hasta `parent[j] = j`.\n",
    "\n",
    "2. **Aplicando Relaciones de Unión**:\n",
    "    - Unimos `a` con `b` (`a <-> b`):\n",
    "        1. `parent[a]` es `a` y `parent[b]` es `b`.\n",
    "        2. Hacemos que `a` sea el representante de `b`, entonces actualizamos `parent[b] = a`.\n",
    "    - Unimos `b` con `d` (`b <-> d`):\n",
    "        1. Ahora necesitamos encontrar el representante actual de `b` para unirlo con `d`.\n",
    "        2. `parent[b]` es `a`, por lo que `a` es el representante de `b`.\n",
    "        3. Unimos `d` con `a` (el representante de `b`), actualizando `parent[d] = a`.\n",
    "    - Similarmente, aplicamos las relaciones `c <-> f`, `c <-> i`, `e <-> j`, y `g <-> j`, actualizando los representantes según las uniones.\n",
    "\n",
    "3. **Estado de `parent` Después de las Uniones**:\n",
    "    - Por ejemplo, después de estas uniones, `parent` podría verse así: `[a, a, c, a, e, c, e, h, c, e]`.\n",
    "\n",
    "4. **Ejecución de Operación Find**:\n",
    "    - Supongamos que queremos encontrar el conjunto al que pertenece el individuo `d`.\n",
    "    - Iniciamos en `d`. `parent[d]` es `a`.\n",
    "    - Verificamos `parent[a]`. Como `parent[a]` es `a` mismo, hemos encontrado el representante del conjunto.\n",
    "    - Por lo tanto, `Find(d)` retorna `a`, lo que significa que `d` pertenece al conjunto representado por `a`.\n",
    "\n",
    "En este ejemplo, hemos detallado cada paso de las operaciones de unión y de búsqueda (Find) en la estructura de conjuntos disjuntos. Hemos mostrado cómo se actualiza el arreglo `parent` para reflejar las uniones y cómo se utiliza la operación `Find` para identificar el conjunto al que pertenece un individuo. La estructura `parent` nos da una visión clara de cómo los individuos están agrupados en conjuntos disjuntos después de las uniones."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b01c613b",
   "metadata": {},
   "source": [
    "#### Implementación computacional"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "b9669839",
   "metadata": {},
   "outputs": [],
   "source": [
    "class DisjointSet:\n",
    "    def __init__(self, size):\n",
    "        self.parent = [i for i in range(size)]\n",
    "\n",
    "    def find(self, i):\n",
    "        if self.parent[i] != i:\n",
    "            self.parent[i] = self.find(self.parent[i])\n",
    "        return self.parent[i]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        xroot = self.find(x)\n",
    "        yroot = self.find(y)\n",
    "        self.parent[yroot] = xroot\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "ca82ebb2",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "El representante de 'd' es: a\n"
     ]
    }
   ],
   "source": [
    "# Creación de la instancia de DisjointSet para 10 individuos\n",
    "n = 10  # n es el número de individuos\n",
    "ds = DisjointSet(n)\n",
    "\n",
    "# Mapeo de individuos a números para simplificar\n",
    "# a = 0, b = 1, c = 2, ..., j = 9\n",
    "# Creación del diccionario para mapear índices a nombres\n",
    "indice_a_nombre = {0: 'a', 1: 'b', 2: 'c', 3: 'd', 4: 'e', 5: 'f', 6: 'g', 7: 'h', 8: 'i', 9: 'j'}\n",
    "\n",
    "# Aplicando las relaciones de unión\n",
    "ds.union(0, 1)  # a <-> b\n",
    "ds.union(1, 3)  # b <-> d\n",
    "ds.union(2, 5)  # c <-> f\n",
    "ds.union(2, 8)  # c <-> i\n",
    "ds.union(4, 9)  # e <-> j\n",
    "ds.union(6, 9)  # g <-> j\n",
    "\n",
    "# Encuentra el representante del conjunto al que pertenece 'd' (3)\n",
    "representante_d = ds.find(3)  # Esperamos que sea 'a' (0)\n",
    "\n",
    "nombre_representante_d = indice_a_nombre[representante_d]\n",
    "\n",
    "print(f\"El representante de 'd' es: {nombre_representante_d}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "055920ef",
   "metadata": {},
   "source": [
    "Estas operaciones son fundamentales en varios algoritmos y aplicaciones, como en el [algoritmo de Kruskal](https://en.wikipedia.org/wiki/Kruskal%27s_algorithm) para encontrar el árbol de expansión mínimo en un grafo, en la detección de ciclos, en el diseño de redes y sistemas de amigos en redes sociales, entre otros."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "eb8367d0",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.8"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "219.429px"
   },
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}