1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
{
"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": {}
}
]
}
|
