Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

DFS-BFS

By: a guest on Jul 31st, 2013  |  syntax: Python  |  size: 0.82 KB  |  views: 37  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
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)