Graph_traversals_algorithms.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyMnTQQr1c4UNa5hlgmIBpY7",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/slothengineer/DSA/blob/main/Graph_traversals_algorithms.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## DEPTH-FIRST SEARCH"
      ],
      "metadata": {
        "id": "jo82GaW4K2b3"
      }
    },
    {
      "cell_type": "code",
      "execution_count": 21,
      "metadata": {
        "id": "8kBP6aexKHDv"
      },
      "outputs": [],
      "source": [
        "## time complexity is O(V + E), where V is the number of vertices, and E is the number of edges in the graph\n",
        "## space complexity of the code is O(V)\n",
        "## recursion -> Stack data structure to store\n",
        "\n",
        "def depthFirstTraversal(visited, graph, node):\n",
        "    if node not in visited:\n",
        "        print(node, end=\" \")\n",
        "        visited.add(node)\n",
        "        for adjacentnodes in graph[node]:\n",
        "            if adjacentnodes not in visited:\n",
        "                depthFirstTraversal(visited, graph, adjacentnodes)"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "## storing the data of the graph using adjacency list\n",
        "visited = set()\n",
        "\n",
        "directed_graph = {\n",
        "    '11' : ['5', '98'],\n",
        "    '5' : ['29', '10'],\n",
        "    '98' : ['14'],\n",
        "    '29' : [],\n",
        "    '10' : ['14'],\n",
        "    '14' : []\n",
        "}\n",
        "\n",
        "print(\"DFS Traversal:\")\n",
        "depthFirstTraversal(visited, directed_graph, \"11\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Q6SLG86uaAZr",
        "outputId": "9e4d5009-7216-4311-f2b4-629998b74d9c"
      },
      "execution_count": 22,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "DFS Traversal:\n",
            "11 5 29 10 14 98 "
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "visited = set()\n",
        "complex_graph = {\n",
        "    'A': ['B', 'C', 'D'],\n",
        "    'B': ['E'],\n",
        "    'C': ['E', 'F'],\n",
        "    'D': ['F'],\n",
        "    'E': ['G'],\n",
        "    'F': ['G'],\n",
        "    'G': []\n",
        "}\n",
        "print(\"DFS Traversal:\")\n",
        "depthFirstTraversal(visited, complex_graph, 'A')"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "OI95L_3kcDyh",
        "outputId": "b45a8a8a-7a60-4c16-961f-ed2c29360c9d"
      },
      "execution_count": 23,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "DFS Traversal:\n",
            "A B E G C F D "
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "visited = set()\n",
        "disconnected_graph = {\n",
        "    'A': ['B', 'C', 'D'],\n",
        "    'B': ['E'],\n",
        "    'C': ['E', 'F'],\n",
        "    'D': ['F'],\n",
        "    'E': ['G'],\n",
        "    'F': ['G'],\n",
        "    'G': [],\n",
        "    'X': ['Y', 'Z'],\n",
        "    'Y': ['W'],\n",
        "    'Z': []\n",
        "}\n",
        "\n",
        "print(\"DFS Traversal:\")\n",
        "depthFirstTraversal(visited, disconnected_graph, 'A')"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ALxBC-cree5n",
        "outputId": "4062c595-2447-4ac5-da81-1f7b5f536c6a"
      },
      "execution_count": 24,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "DFS Traversal:\n",
            "A B E G C F D "
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## BREADTH-FIRST SEARCH"
      ],
      "metadata": {
        "id": "lFcUA5XaPzTy"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "## the time complexity is O(V + E), and the space complexity is O(V)\n",
        "## here , also we have used adjancency list\n",
        "\n",
        "from collections import deque\n",
        "queue = deque()\n",
        "\n",
        "def breadthFirstTraversal(visited, graph, node):\n",
        "    visited.add(node)\n",
        "    queue.appendleft(node)\n",
        "\n",
        "    while queue:\n",
        "        node = queue.pop()\n",
        "        print(node)\n",
        "        for adjacentnodes in graph[node]:\n",
        "            if adjacentnodes not in visited:\n",
        "                visited.add(adjacentnodes)\n",
        "                queue.appendleft(adjacentnodes)"
      ],
      "metadata": {
        "id": "agvk1p8CPy6h"
      },
      "execution_count": 25,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "visited = set()\n",
        "\n",
        "graph = {\n",
        "    'A' : ['B', 'C', 'D'],\n",
        "    'B' : ['E'],\n",
        "    'C' : ['E', 'F'],\n",
        "    'D' : ['F'],\n",
        "    'E' : ['G'],\n",
        "    'F' : ['G'],\n",
        "    'G' : []\n",
        "\n",
        "}\n",
        "\n",
        "print(\"BFS Traversal:\")\n",
        "breadthFirstTraversal(visited, graph, \"A\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "qer5m9xBY2J6",
        "outputId": "f2f45149-d0c3-4c3f-f7e1-20e60b97b9bc"
      },
      "execution_count": 26,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "BFS Traversal:\n",
            "A\n",
            "B\n",
            "C\n",
            "D\n",
            "E\n",
            "F\n",
            "G\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "visited = set()\n",
        "\n",
        "graph2 = {\n",
        "    'A': ['B', 'C'],\n",
        "    'B': ['C'],\n",
        "    'C': ['D'],\n",
        "    'D': ['A', 'B'],\n",
        "    'E': ['A']\n",
        "}\n",
        "\n",
        "breadthFirstTraversal(visited, graph2, \"E\")"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ko793dUDa42k",
        "outputId": "6964d961-0756-4bde-cd67-3f6e441fc46e"
      },
      "execution_count": 27,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "E\n",
            "A\n",
            "B\n",
            "C\n",
            "D\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "visited = set()\n",
        "complex_graph = {\n",
        "    'A': ['B', 'C', 'D'],\n",
        "    'B': ['E'],\n",
        "    'C': ['E', 'F'],\n",
        "    'D': ['F'],\n",
        "    'E': ['G'],\n",
        "    'F': ['G'],\n",
        "    'G': []\n",
        "}\n",
        "print(\"DFS Traversal:\")\n",
        "breadthFirstTraversal(visited, complex_graph, 'A')"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "yd9YMWGHbOuj",
        "outputId": "2e14a5d1-894d-4f14-b1c8-d47179b588f6"
      },
      "execution_count": 28,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "DFS Traversal:\n",
            "A\n",
            "B\n",
            "C\n",
            "D\n",
            "E\n",
            "F\n",
            "G\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "visited = set()\n",
        "\n",
        "disconnected_graph = {\n",
        "    'A': ['B', 'C', 'D'],\n",
        "    'B': ['E'],\n",
        "    'C': ['E', 'F'],\n",
        "    'D': ['F'],\n",
        "    'E': ['G'],\n",
        "    'F': ['G'],\n",
        "    'G': [],\n",
        "    'X': ['Y', 'Z'],\n",
        "    'Y': ['W'],\n",
        "    'Z': []\n",
        "}\n",
        "\n",
        "print(\"DFS Traversal:\")\n",
        "breadthFirstTraversal(visited, disconnected_graph, 'A')"
      ],
      "metadata": {
        "id": "7jlLX4ihcvKu",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "ac579e6e-e7b0-4b8f-f2a2-45b0b9721c16"
      },
      "execution_count": 29,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "DFS Traversal:\n",
            "A\n",
            "B\n",
            "C\n",
            "D\n",
            "E\n",
            "F\n",
            "G\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Application of Graph DataStructure"
      ],
      "metadata": {
        "id": "EDcHgHUMuZeX"
      }
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 1. Number of Islands\n",
        "Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.\n",
        "\n",
        "An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water."
      ],
      "metadata": {
        "id": "yRTirOjyuxJm"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def numIslands(grid):\n",
        "    if not grid:\n",
        "        return 0\n",
        "\n",
        "    def dfs(row, col):            ## dfs => depth first search\n",
        "\n",
        "        # Base case: If the current cell is out of bounds or is water, return\n",
        "        if row < 0 or col < 0 or row >= len(grid) or col >= len(grid[0]) or grid[row][col] == '0':\n",
        "            return\n",
        "\n",
        "        grid[row][col] = '0'      ## to check visited\n",
        "\n",
        "        # visit the neighboring cells recursively in all four directions.\n",
        "        dfs(row - 1, col)     #up\n",
        "        dfs(row + 1, col)     #down\n",
        "        dfs(row, col - 1)     #left\n",
        "        dfs(row, col + 1)     #right\n",
        "\n",
        "    num_islands = 0\n",
        "\n",
        "    for row in range(len(grid)):\n",
        "        for col in range(len(grid[0])):\n",
        "            if grid[row][col] == '1':\n",
        "                # found the start of a new island, increment the count and explore it.\n",
        "                num_islands += 1\n",
        "                dfs(row, col)\n",
        "\n",
        "    return num_islands\n",
        "\n",
        "# use\n",
        "grid = [\n",
        "    [\"1\", \"1\", \"0\", \"0\", \"0\"],\n",
        "    [\"1\", \"1\", \"0\", \"0\", \"0\"],\n",
        "    [\"0\", \"0\", \"1\", \"0\", \"0\"],\n",
        "    [\"0\", \"0\", \"0\", \"1\", \"1\"]\n",
        "]\n",
        "\n",
        "result = numIslands(grid)\n",
        "print(result)"
      ],
      "metadata": {
        "id": "6gZ4I9I_fUbm",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "fcc27cca-f6e6-4909-cfbd-dbe052aa9fa1"
      },
      "execution_count": 30,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "3\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 2. Surrounded Regions\n",
        "Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.\n",
        "\n",
        "A region is captured by flipping all 'O's into 'X's in that surrounded region"
      ],
      "metadata": {
        "id": "lUmPevWmy0KS"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def solve(board):\n",
        "    if not board:\n",
        "        return\n",
        "\n",
        "    m = len(board)\n",
        "    n = len(board[0])\n",
        "\n",
        "    def dfs(row, col):\n",
        "        if row < 0 or col < 0 or row >= m or col >= n or board[row][col] != 'O':\n",
        "            return\n",
        "\n",
        "        board[row][col] = 'T'    ## mark current cell as visited\n",
        "\n",
        "        dfs(row - 1, col)\n",
        "        dfs(row + 1, col)\n",
        "        dfs(row, col - 1)\n",
        "        dfs(row, col + 1)\n",
        "\n",
        "    ## tranverse borders of matrix to change 'O' to 'T'\n",
        "    for i in range(m):\n",
        "        dfs(i, 0)            # left border\n",
        "        dfs(i, n - 1)        # right border\n",
        "\n",
        "    for j in range(n):\n",
        "        dfs(0, j)            # top border\n",
        "        dfs(m - 1, j)        # bottom border\n",
        "\n",
        "    # replace 'O's with 'X's and 'T's with 'O's in the entire matrix\n",
        "    for i in range(m):\n",
        "        for j in range(n):\n",
        "            if board[i][j] == 'O':\n",
        "                board[i][j] = 'X'\n",
        "            elif board[i][j] == 'T':\n",
        "                board[i][j] = 'O'\n",
        "    return board\n",
        "\n",
        "# use\n",
        "board = [\n",
        "    ['X', 'X', 'X', 'X'],\n",
        "    ['X', 'O', 'O', 'X'],\n",
        "    ['X', 'X', 'O', 'X'],\n",
        "    ['X', 'O', 'X', 'X']\n",
        "]\n",
        "print(solve(board))"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "YyszSuiZwmy6",
        "outputId": "e57ea3ac-1fe0-4c6d-a123-2ebf49d2f03c"
      },
      "execution_count": 31,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'X'], ['X', 'O', 'X', 'X']]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 3. Clone Graph\n",
        "Given a reference of a node in a connected undirected graph.\n",
        "\n",
        "Return a deep copy (clone) of the graph.\n",
        "\n",
        "Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors."
      ],
      "metadata": {
        "id": "v5uxkOwkp2GE"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "class Node:\n",
        "    def __init__(self, val = 0, neighbors = None):\n",
        "        self.val = val\n",
        "        self.neighbors = []\n",
        "\n",
        "\n",
        "class Solution:\n",
        "    def cloneGraph(node):\n",
        "        if not node:\n",
        "            return None\n",
        "\n",
        "        visited = {}\n",
        "        def dfs(original_node):\n",
        "            if original_node in visited:\n",
        "                return visited[original_node]\n",
        "\n",
        "            ## clone of current node\n",
        "            clone = Node(original_node.val)\n",
        "            visited[original_node] = clone\n",
        "\n",
        "            ## clone its neighbors\n",
        "            for neighbor in original_node.neighbors:\n",
        "                clone.neighbors.append(dfs(neighbor))\n",
        "\n",
        "            return clone\n",
        "        return dfs(node)\n",
        "\n",
        "\n",
        "# use\n",
        "node1 = Node(1)\n",
        "node2 = Node(2)\n",
        "node3 = Node(3)\n",
        "node4 = Node(4)\n",
        "\n",
        "node1.neighbors = [node2, node4]\n",
        "node2.neighbors = [node1, node3]\n",
        "node3.neighbors = [node2, node4]\n",
        "node4.neighbors = [node1, node3]\n",
        "\n",
        "cloned_node1 = Solution.cloneGraph(node1)\n",
        "\n",
        "# to print graphs\n",
        "def printGraph(node):\n",
        "    if not node:\n",
        "        return\n",
        "\n",
        "    visited = set()\n",
        "    stack = [node]\n",
        "\n",
        "    while stack:\n",
        "        current = stack.pop()\n",
        "        if current in visited:\n",
        "            continue\n",
        "\n",
        "        print(f\"Node {current.val} -> \", end=\"\")\n",
        "        for neighbor in current.neighbors:\n",
        "            print(neighbor.val, end=\" \")\n",
        "            stack.append(neighbor)\n",
        "\n",
        "        visited.add(current)\n",
        "        print()\n",
        "\n",
        "print(\"Original Graph:\")\n",
        "printGraph(node1)\n",
        "\n",
        "print(\"Cloned Graph:\")\n",
        "printGraph(cloned_node1)"
      ],
      "metadata": {
        "id": "RNTGfhRAzh7R",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "069ae0fa-33d6-48ea-a9bb-5a3f5ba7d1bb"
      },
      "execution_count": 32,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "Original Graph:\n",
            "Node 1 -> 2 4 \n",
            "Node 4 -> 1 3 \n",
            "Node 3 -> 2 4 \n",
            "Node 2 -> 1 3 \n",
            "Cloned Graph:\n",
            "Node 1 -> 2 4 \n",
            "Node 4 -> 1 3 \n",
            "Node 3 -> 2 4 \n",
            "Node 2 -> 1 3 \n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 4. Evaluate Division\n",
        "You are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.\n",
        "\n",
        "You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.\n",
        "\n",
        "Return the answers to all queries. If a single answer cannot be determined, return -1.0.\n",
        "\n",
        "Note: The input is always valid. You may assume that evaluating the queries will not result in division by zero and that there is no contradiction.\n",
        "\n",
        "Note: The variables that do not occur in the list of equations are undefined, so the answer cannot be determined for them."
      ],
      "metadata": {
        "id": "tEENOd-DubPA"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from collections import defaultdict\n",
        "class Solution:\n",
        "    def calcEquation(equations, values, queries):\n",
        "        graph = defaultdict(dict)       # graph to store values of equation\n",
        "\n",
        "        # build the graph\n",
        "        for (numerator, denominator), value in zip(equations, values):\n",
        "            graph[numerator][denominator] = value\n",
        "            graph[denominator][numerator] = 1 / value\n",
        "\n",
        "        def dfs(start, end, visited):\n",
        "            if start not in graph or end not in graph:\n",
        "                return -1.0\n",
        "\n",
        "            if start == end:\n",
        "                return 1.0\n",
        "\n",
        "            visited.add(start)           ## to avoid cycles in graph\n",
        "            for neighbor, value in graph[start].items():\n",
        "                if neighbor not in visited:\n",
        "                    result = dfs(neighbor, end, visited)\n",
        "                    if result != -1.0:\n",
        "                        return value * result\n",
        "\n",
        "            visited.remove(start)\n",
        "            return -1.0\n",
        "\n",
        "        results = []\n",
        "        for query in queries:\n",
        "            start, end = query\n",
        "            visited = set()\n",
        "            result = dfs(start, end, visited)\n",
        "            results.append(result)\n",
        "\n",
        "        return results\n",
        "\n",
        "# use\n",
        "equations = [[\"a\", \"b\"], [\"b\", \"c\"]]\n",
        "values = [2.0, 3.0]\n",
        "queries = [[\"a\", \"c\"], [\"b\", \"a\"], [\"a\", \"e\"], [\"a\", \"a\"], [\"x\", \"x\"]]\n",
        "results = Solution.calcEquation(equations, values, queries)\n",
        "print(results)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "ZBrJWo7tr2Tj",
        "outputId": "081fc99e-984b-49e5-80ce-d26780661245"
      },
      "execution_count": 33,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "[6.0, 0.5, -1.0, 1.0, -1.0]\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "### 5. Course Schedule\n",
        "There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.\n",
        "\n",
        "For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.\n",
        "Return true if you can finish all courses. Otherwise, return false."
      ],
      "metadata": {
        "id": "-tb7vRTuvoRo"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "from collections import defaultdict, deque\n",
        "class Solution:\n",
        "    def canFinish(numCourses, prerequisites):\n",
        "        # create an adjacency list to represent the graph\n",
        "        graph = defaultdict(list)\n",
        "        in_degree = [0] * numCourses\n",
        "\n",
        "        # build graph and calculate in_degree\n",
        "        for course, prereq in prerequisites:\n",
        "            graph[prereq].append(course)\n",
        "            in_degree[course] += 1\n",
        "\n",
        "        # queue with courses having no prerequisites\n",
        "        queue = deque()\n",
        "        for course in range(numCourses):\n",
        "            if in_degree[course] == 0:\n",
        "                queue.append(course)\n",
        "\n",
        "        completed_courses = 0\n",
        "\n",
        "        # topological sorting\n",
        "        while queue:\n",
        "            course = queue.popleft()\n",
        "            completed_courses += 1\n",
        "\n",
        "            for neighbor in graph[course]:\n",
        "                in_degree[neighbor] -= 1\n",
        "                if in_degree[neighbor] == 0:\n",
        "                    queue.append(neighbor)\n",
        "\n",
        "        return completed_courses == numCourses\n",
        "\n",
        "\n",
        "# use\n",
        "numCourses = 4\n",
        "prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]\n",
        "result = Solution.canFinish(numCourses, prerequisites)\n",
        "print(result)\n",
        ""
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "e2fZfhvHu8H3",
        "outputId": "42892a02-98b1-4fc4-9b90-c25f03498306"
      },
      "execution_count": 34,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "True\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [],
      "metadata": {
        "id": "t4A0pCmcwsnw"
      },
      "execution_count": 34,
      "outputs": []
    }
  ]
}