title: How to keep track of depth in breadth first search?
body: <p>I have a tree as input to the breadth first search and I want to know as the algorithm progresses at which level it is?</p>
  
  <pre class="lang-python prettyprint-override"><code># Breadth First Search Implementation
  graph = { 
      'A':['B','C','D'],
      'B':['A'],
      'C':['A','E','F'],
      'D':['A','G','H'],
      'E':['C'],
      'F':['C'],
      'G':['D'],
      'H':['D']
      }
  
  
  def breadth_first_search(graph,source):
      """
      This function is the Implementation of the breadth_first_search program
      """
      # Mark each node as not visited
      mark = {}
      for item in graph.keys():
          mark[item] = 0
  
      queue, output = [],[]
  
      # Initialize an empty queue with the source node and mark it as explored
      queue.append(source)
      mark[source] = 1
      output.append(source)
  
      # while queue is not empty
      while queue:
          # remove the first element of the queue and call it vertex
          vertex = queue[0]
          queue.pop(0)
          # for each edge from the vertex do the following
          for vrtx in graph[vertex]:
              # If the vertex is unexplored
              if mark[vrtx] == 0:
                  queue.append(vrtx)  # mark it as explored
                  mark[vrtx] = 1      # and append it to the queue
                  output.append(vrtx) # fill the output vector
      return output
  
  print breadth_first_search(graph, 'A')
  </code></pre>
  
  <p>It takes tree as an input graph, what I want is, that at each iteration it should print out the current level which is being processed.</p>