Welcome, guest | Sign In | My Account | Store | Cart

Recipe 577876 revision 2 

def printBfsLevels(graph,start):
  queue=[start]
  path=[]
  currLevel=1
  levelMembers=1
  height={start:0}
  print queue
  while queue:
    visNode=queue.pop(0)
    if visNode not in path:
      try:
        if  levelMembers==0:
          levelMembers=2
          currLevel=currLevel+1
        queue=queue+graph[visNode]
        if levelMembers > 0:
          levelMembers=levelMembers-1
          for node in graph[visNode]:
            height[node]=currLevel
      except KeyError:
        pass
      path=path+[visNode]

  prevLevel=None      
  for k,v in height.items():
        if prevLevel!=v:
          if prevLevel!=None:
            print "\n"
        prevLevel=v
        print k,
      

g={1: [2, 3], 2: [4, 5], 3: [6, 7]}

>>> printBfsLevels(g,1)
[1]
1 

2 3 

4 5 6 7

Diff to Previous Revision

--- revision 1 2011-09-22 12:22:56
+++ revision 2 2011-09-22 12:33:08
@@ -10,7 +10,7 @@
     if visNode not in path:
       try:
         if  levelMembers==0:
-          levelMembers=len(graph[visNode])
+          levelMembers=2
           currLevel=currLevel+1
         queue=queue+graph[visNode]
         if levelMembers > 0:

History