L013_Graph_BFS_DFS.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graphs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Requirements"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Queue\n",
    "class Queue:\n",
    "    def __init__(self):\n",
    "        self.queue = []\n",
    "    def enqueue(self, item):\n",
    "        self.queue.append(item)\n",
    "    def dequeue(self):\n",
    "        if self.is_empty():\n",
    "            return None\n",
    "        return self.queue.pop(0)\n",
    "    def isEmpty(self):\n",
    "        return len(self.queue) == 0\n",
    "    def size(self):\n",
    "        return len(self.queue)\n",
    "    def __str__(self):\n",
    "        return str(self.queue)\n",
    "    \n",
    "#Stack\n",
    "class Stack:\n",
    "    def __init__(self):\n",
    "        self.items = []\n",
    "    def isEmpty(self):\n",
    "        return self.items == []\n",
    "    def push(self, item):\n",
    "        self.items.append(item)\n",
    "    def pop(self):\n",
    "        if self.isEmpty():\n",
    "            return None\n",
    "        return self.items.pop()\n",
    "    def peek(self): #return the top element of the stack without removing it\n",
    "        return self.items[len(self.items)-1]\n",
    "    def size(self):\n",
    "        return len(self.items)\n",
    "    def __str__(self):\n",
    "        return str(self.items)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def neighbors(graph, node): #return a list of neighbors of a node\n",
    "    return graph[node]\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## BFS - Breadth First Search\n",
    "This is a systematic way to visit all the vertices and edges of a graph. It starts at a given vertex and explores all the neighboring vertices. Then for each of those neighbor vertices in turn, it explores their neighbor vertices which were unexplored, and so on.\n",
    "\n",
    "Complexity: \n",
    "- O(V+E) for adjacency list representation of graph\n",
    "- O(V^2) for adjacency matrix representation of graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Rechability"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "def BFS(AMat,v): #AMat is the adjacency matrix, v is the starting vertex\n",
    "    # Initailization\n",
    "    rows,cols=AMat.shape\n",
    "    visited={}\n",
    "    for i in range(rows):\n",
    "        visited[i]=False\n",
    "    q=Queue()\n",
    "\n",
    "    #Start BFS from vertex v\n",
    "    visited[v]=True\n",
    "    q.enqueue(v)\n",
    "\n",
    "    # Remove and explore vertex i at the head of the queue\n",
    "    while(not q.isEmpty()):\n",
    "        j=q.dequeue()\n",
    "        for k in neighbors(AMat,j): #neighbors() is a function that returns the neighbors of vertex j\n",
    "            if not visited[k]:\n",
    "                visited[k]=True\n",
    "                q.enqueue(k)\n",
    "    \n",
    "    return visited\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Path to rechability"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def BFSListPath(AList,v): #AList is the adjacency list, v is the starting vertex\n",
    "    visited,parent={},{}\n",
    "    for i in AList.keys():\n",
    "        visited[i]=False\n",
    "        parent[i]=-1\n",
    "    q=Queue()\n",
    "\n",
    "    visited[v]=True\n",
    "    q.enqueue(v)\n",
    "\n",
    "    while(not q.isEmpty()):\n",
    "        j=q.dequeue()\n",
    "        for k in AList[j]:\n",
    "            if not visited[k]:\n",
    "                visited[k]=True\n",
    "                parent[k]=j\n",
    "                q.enqueue(k)\n",
    "\n",
    "    return visited,parent\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Record Distance"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def BFSListPathLevel(AList,v):\n",
    "    level,parent={},{}\n",
    "    for i in AList.keys():\n",
    "        level[i]=-1\n",
    "        parent[i]=-1\n",
    "    q=Queue()\n",
    "\n",
    "    level[v]=0\n",
    "    q.enqueue(v)\n",
    "\n",
    "    while(not q.isEmpty()):\n",
    "        j=q.dequeue()\n",
    "        for k in AList[j]:\n",
    "            if level[k]==-1:\n",
    "                level[k]=level[j]+1\n",
    "                parent[k]=j\n",
    "                q.enqueue(k)\n",
    "    \n",
    "    return level,parent\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## DFS - Depth First Search\n",
    "This is a systematic way to visit all the vertices and edges of a graph. It starts at a given vertex and explores as far as possible along each branch before backtracking."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def DFSInit(AMat):\n",
    "    #initialization\n",
    "    rows,cols=AMat.shape\n",
    "    visited,parent={},{}\n",
    "    for i in range(rows):\n",
    "        visited[i]=False\n",
    "        parent[i]=-1\n",
    "    return visited,parent\n",
    "\n",
    "def DFS(AMat,visited,parent,v):\n",
    "    visited[v]=True\n",
    "\n",
    "    for k in neighbors(AMat,v):\n",
    "        if not visited[k]:\n",
    "            parent[k]=v\n",
    "            visited,parent=DFS(AMat,visited,parent,k)\n",
    "    return visited,parent\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "###  We can make visited and parent global variables\n",
    "visited,parent={},{}\n",
    "\n",
    "def DFSInitGlobal(AMat):\n",
    "    #initialization\n",
    "    rows,cols=AMat.shape\n",
    "    for i in range(rows):\n",
    "        visited[i]=False\n",
    "        parent[i]=-1\n",
    "    return\n",
    "\n",
    "def DFSGlobal(AMat,v):\n",
    "    visited[v]=True\n",
    "\n",
    "    for k in neighbors(AMat,v):\n",
    "        if not visited[k]:\n",
    "            parent[k]=v\n",
    "            DFSGlobal(AMat,k)\n",
    "    return\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Using Adjacency List:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def DFSInitList(AList):\n",
    "    visited,parent={},{}\n",
    "    for i in AList.keys():\n",
    "        visited[i]=False\n",
    "        parent[i]=-1\n",
    "    return visited,parent\n",
    "\n",
    "def DFSList(AList,visited,parent,v):\n",
    "    visited[v]=True\n",
    "\n",
    "    for k in AList[v]:\n",
    "        if not visited[k]:\n",
    "            parent[k]=v\n",
    "            visited,parent=DFSList(AList,visited,parent,k)\n",
    "    \n",
    "    return visited,parent\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.12.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}