How to keep track of depth in breadth first search?

Question

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?

# 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') 

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.

Answer 1

Actually, we don't need an extra queue to store the info on the current depth, nor do we need to add null to tell whether it's the end of current level. We just need to know how many nodes the current level contains, then we can deal with all the nodes in the same level, and increase the level by 1 after we are done processing all the nodes on the current level.

int level = 0; Queue<Node> queue = new LinkedList<>(); queue.add(root); while(!queue.isEmpty()){     int level_size = queue.size();     while (level_size-- != 0) {         Node temp = queue.poll();         if (temp.right != null) queue.add(temp.right);         if (temp.left != null) queue.add(temp.left);     }         level++; }