{
 "metadata": {
  "name": "",
  "signature": "sha256:a85fddad5ca1dfcfd83be3de3e24c0c6e6b3cfc061b0141fb4ecc95c31a3f057"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "4 Graphs and planar graphs"
     ]
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 03:Page 199 "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print \"GRAPH TRAVERSLS-DEPTH FIRST SEARCH\"\n",
      "graph={'A': ['G','B'],\n",
      "       'B': ['C'],\n",
      "       'C': ['E','D'],\n",
      "       'D': [],\n",
      "       'E': ['D','F'],\n",
      "       'F': ['A'],\n",
      "       'G': ['F']}#Input the graph details using a sequence data structure \n",
      "\n",
      "def dfs(graph,start):\n",
      "    path=[]#Initially the path is empty, as no nodes are visited\n",
      "    stack=[start]#The starting node is pushed into the stack\n",
      "    while stack!=[]:\n",
      "        visited=stack.pop()#The node is marked as visited\n",
      "        if visited not in path:\n",
      "            path.append(visited)#The node is added to the path\n",
      "        for w in reversed(graph[visited]):#The node is checked to see if it has any adjacent nodes. \n",
      "            if w not in path:\n",
      "                stack.append(w)#Adjacent nodes if any without being visited are added to the stack\n",
      "    return path\n",
      "print  \"path=\",dfs(graph,'A')#The sequence and the starting nodes are given as input \n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "GRAPH TRAVERSLS-DEPTH FIRST SEARCH\n",
        "path= ['A', 'G', 'F', 'B', 'C', 'E', 'D']\n"
       ]
      }
     ],
     "prompt_number": 1
    },
    {
     "cell_type": "heading",
     "level": 2,
     "metadata": {},
     "source": [
      "Example 04:Page 201"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print \"GRAPH TRAVERSALS-BREADTH FIRST SEARCH\"\n",
      "graph={'A': set(['G','B']),\n",
      "       'B': set(['C']),\n",
      "       'C': set(['D','E']),\n",
      "       'D': set([]),\n",
      "       'E': set(['D','F']),\n",
      "       'F': set(['A']),\n",
      "       'G': set(['F'])}#Input the graph information\n",
      "\n",
      "def bfs(graph,start):\n",
      "    path=[]#Initially path is empty as no nodes are visited\n",
      "    queue=[start]#The start node is added to the queue\n",
      "    while queue:\n",
      "        v=queue.pop(0)#Always the first node is only popped\n",
      "        if v not in path:\n",
      "            path+=[v]#The popped node is added to the path\n",
      "            queue+=graph[v]#The adjacent nodes of the visited nodes are inserted in the queue\n",
      "    return path\n",
      "print \"path=\",bfs(graph,'A')\n"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "GRAPH TRAVERSALS-BREADTH FIRST SEARCH\n",
        "path= ['A', 'B', 'G', 'C', 'F', 'E', 'D']\n"
       ]
      }
     ],
     "prompt_number": 2
    }
   ],
   "metadata": {}
  }
 ]
}