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

Printing breadth First Levels of a graph (Or) Tree (Python recipe) by Venkatesh
ActiveState Code (http://code.activestate.com/recipes/577876/)

Prints the breadth first Levels of a graph (Or) Tree, by performing Breadth First Search

Python, 126 lines
Download
  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
118
119
120
121
122
123
124
125
126
def printBfsLevels(graph,start):
  queue=[start]
  path=[]
  currLevel=1
  levelMembers=1
  height=[(0,start)]
  childCount=0
  print queue
  while queue:
    visNode=queue.pop(0)
    if visNode not in path:
      if  levelMembers==0:
        levelMembers=childCount
        childCount=0
        currLevel=currLevel+1
      queue=queue+graph.get(visNode,[])
      if levelMembers > 0:
        levelMembers=levelMembers-1
        for node in graph.get(visNode,[]):
          childCount=childCount+1
          height.append((currLevel,node))
      path=path+[visNode]

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

g={1: [2, 3,6], 2: [4, 5], 3: [6, 7],4:[8,9,13]}
printBfsLevels(g,1)


>>> 
[1]
1 

2 3 6 

4 5 6 7 

8 9 13
>>> 

# Another version based on Recursion, Which is specific to Binary tree


class BinTree:
  "Node in a binary tree"
  def __init__(self,val,leftChild=None,rightChild=None,root=None):
    self.val=val
    self.leftChild=leftChild
    self.rightChild=rightChild
    self.root=root
    if not leftChild and not rightChild:
      self.isExternal=True

  def getChildren(self,node):
    children=[]
    if node.isExternal:
      return []
    if node.leftChild:
      children.append(node.leftChild)
    if node.rightChild:
      children.append(node.rightChild)
    return children

  @staticmethod
  def createTree(tupleList):
    "Creates a Binary tree Object from a given Tuple List"
    Nodes={}
    root=None
    for item in treeRep:
      if not root:
        root=BinTree(item[0])
        root.isExternal=False
        Nodes[item[0]]=root
        root.root=root
        root.leftChild=BinTree(item[1],root=root)
        Nodes[item[1]]=root.leftChild
        root.rightChild=BinTree(item[2],root=root)
        Nodes[item[2]]=root.rightChild
      else:
        CurrentParent=Nodes[item[0]]
        CurrentParent.isExternal=False
        CurrentParent.leftChild=BinTree(item[1],root=root)
        Nodes[item[1]]=CurrentParent.leftChild
        CurrentParent.rightChild=BinTree(item[2],root=root)
        Nodes[item[2]]=CurrentParent.rightChild
    root.nodeDict=Nodes
    return root

  def printBfsLevels(self,levels=None):
    if levels==None:
      levels=[self]
    nextLevel=[]
    for node in levels:
      print node.val,
    for node in levels:
      nextLevel.extend(node.getChildren(node))
    print '\n'
    if nextLevel:
      node.printBfsLevels(nextLevel)  
     

##       1
##     2     3
##   4   5  6  7
##  8

treeRep = [(1,2,3),(2,4,5),(3,6,7),(4,8,None)]
tree= BinTree.createTree(treeRep)
tree.printBfsLevels()

>>> 
1 

2 3 

4 5 6 7 

8 None
Tags: bfs, level, tree
Created by Venkatesh on Thu, 22 Sep 2011 (MIT)
◄ Python recipes (4591) ►
◄ Venkatesh's recipes (1) ►

Required Modules

  • (none specified)

Other Information and Tasks