如何在广度优先搜索中跟踪深度? [英] How to keep track of depth in breadth first search?

问题描述

我有一棵树作为广度优先搜索的输入，我想知道随着算法的进展它处于哪个级别?

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.

推荐答案

您不需要使用额外的队列或进行任何复杂的计算来实现您想要的.这个想法很简单.

You don't need to use extra queue or do any complicated calculation to achieve what you want to do. This idea is very simple.

除了用于 BFS 的队列之外，这不会使用任何额外的空间.

This does not use any extra space other than queue used for BFS.

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

The idea I am going to use is to add null at the end of each level. So the number of nulls you encountered +1 is the depth you are at. (of course after termination it is just 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);
     }

这篇关于如何在广度优先搜索中跟踪深度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！