• API
• FAQ
• Tools
• Trends
• Archive
SHARE
TWEET

DFS-BFS

a guest Jul 31st, 2013 43 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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)
RAW Paste Data
Top