DSA_Notebooks/Minimum_Spanning_Tree_(Disjoint_Set).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h1 align='center'>Minimum Spanning Tree( Disjoint Set)</h1>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "    A Minimum Spanning Tree is a subset of the edges of connected, weighted and undirected graph.\n",
    "    - Connects all vertices together\n",
    "    - No cycle\n",
    "    - Minimum total edge"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<h2>Disjoint set</h2>\n",
    "\n",
    "\n",
    "    The disjoint set data structure is also known as union-find data structure and merge-find set. It is a data structure that contains a collection of disjoint or non-overlapping sets. The disjoint set means that when the set is partitioned into the disjoint subsets. The various operations can be performed on the disjoint subsets. In this case, we can add new sets, we can merge the sets, and we can also find the representative member of a set. It also allows to find out whether the two elements are in the same set or not efficiently.\n",
    "    \n",
    "### Operations\n",
    "    - Make set\n",
    "    - Union\n",
    "    - Find set\n",
    "\n",
    "\n",
    "#### Make set\n",
    "![](https://static.javatpoint.com/ds/images/disjoint-set-data-structure.png)\n",
    "\n",
    "s1 = {1, 2, 3, 4}\n",
    "\n",
    "s2 = {5, 6, 7, 8}\n",
    "\n",
    "#### Union set\n",
    "![](https://static.javatpoint.com/ds/images/disjoint-set-data-structure2.png)\n",
    "\n",
    "s3 = s1Us2 \n",
    "\n",
    "s3 = {1, 2, 3, 4, 5, 6, 7, 8}\n",
    "\n",
    "#### Find set \n",
    "    - Return the name of the set in which this element is.\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "class DisjointSet:\n",
    "    def __init__(self, vertices):\n",
    "        self.vertices = vertices\n",
    "        self.parent = {}\n",
    "        for v in vertices:\n",
    "            self.parent[v] = v\n",
    "        self.rank = dict.fromkeys(vertices, 0)\n",
    "    \n",
    "    def find(self, item):\n",
    "        if self.parent[item] == item:\n",
    "            return item\n",
    "        else:\n",
    "            return self.find(self.parent[item])\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        xroot = self.find(x)\n",
    "        yroot = self.find(y)\n",
    "        if self.rank[xroot] < self.rank[yroot]:\n",
    "            self.parent[xroot] = yroot\n",
    "        elif self.rank[xroot] > self.rank[yroot]:\n",
    "            self.parent[yroot] = xroot\n",
    "        else:\n",
    "            self.parent[yroot] = xroot\n",
    "            self.rank[xroot] += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "vertices = [\"A\", \"B\", \"C\", \"D\", \"E\"]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "ds = DisjointSet(vertices)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'B'"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ds.find(\"B\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "ds.union(\"A\", \"B\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'A'"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ds.find(\"B\")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.10.2 64-bit",
   "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.10.2"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "369f2c481f4da34e4445cda3fffd2e751bd1c4d706f27375911949ba6bb62e1c"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}