algorithm - 如何跟踪广度优先搜索的深度？

我有一棵树作为广度优先搜索的输入，我想知道算法在哪一级进行？

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

它需要树作为输入图，我想要的是，在每次迭代时都应打印出正在处理的当前级别。

最佳答案

您无需使用额外的队列或进行任何复杂的计算即可实现您想要的工作。这个想法很简单。

除了用于BFS的队列以外，此空间不使用任何其他空间。

我要使用的想法是在每个级别的末尾添加null。因此，您遇到的+1的空值数就是您所处的深度。 (当然，终止后只是level)。

     int level = 0;
     Queue <Node> queue = new LinkedList<>();
     queue.add(root);
     queue.add(null);
     while(!queue.isEmpty()){
          Node temp = queue.poll();
          if(temp == null){
              level++;
              queue.add(null);
              if(queue.peek() == null) break;// You are encountering two consecutive `nulls` means, you visited all the nodes.
              else continue;
          }
          if(temp.right != null)
              queue.add(temp.right);
          if(temp.left != null)
              queue.add(temp.left);
     }