Check out the Pastebin Gadgets Shop. We have thousands of fun, geeky & affordable gadgets on sale :-)Want more features on Pastebin? Sign Up, it's FREE!
tweet

# DFS-BFS

By: a guest on Jul 31st, 2013  |  syntax: Python  |  size: 0.82 KB  |  views: 41  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. #!/usr/local/bin/python2.7
2.
3. def bfs(graph, ex, wy):
4.   queue = [(ex,wy,0)]
5.   currl = 0
6.   while len(queue):
7.     (x,y,l) = queue.pop(0)
8.     if x<0 or y<0 or x==len(graph) or y==len(graph[0]):
9.       continue
10.     if l!=currl:
11.       currl = l
12.       printGraph(graph)
13.     if graph[x][y]==0:
14.       graph[x][y]=1
15.       queue+=[(x+1,y,l+1),(x-1,y,l+1),(x,y-1,l+1),(x,y+1,l+1)]
16.
17. def dfs(graph, ex, wy):
18.   stack = [(ex,wy,0)]
19.   while len(stack):
20.     (x,y,l) = stack.pop(len(stack)-1)
21.     if x<0 or y<0 or x==len(graph) or y==len(graph[0]):
22.       continue
23.     if graph[x][y]==0:
24.       graph[x][y]=1
25.       stack+=[(x+1,y,l+1),(x-1,y,l+1),(x,y-1,l+1),(x,y+1,l+1)]
26.       printGraph(graph)
27.
28. def printGraph(graph):
29.   for i in graph:
30.     print i
31.   print
32.
33. x = 11
34. y = 11
35. curr = [[0]*y for i in xrange(x)]
36. bfs(curr,x/2,y/2)
clone this paste RAW Paste Data
Top