如何跟踪深度的广度第一搜索？ [英] How to keep track of depth in breadth first search?

问题描述

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

 ＃宽度优先搜索实现
 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（图，源）：

这个功能是breadth_first_search程序

＃将每个节点标记为未访问
 mark = {} 
 for graph.keys（）中的项目：
 mark [item] = 0 
 
 queue，output = []，[] 
 
＃初始化源节点的空队列，并将其标记为已探索
 queue.append（source） 
 mark [source] = 1 
 output.append（source）
 
＃，而队列不为空
同时队列：
＃删除队列的第一个元素并调用它顶点
 vertex = queue [0] 
 queue.pop（0）
＃对于顶点中的每个边缘，在图[顶点]中为vrtx执行以下
：
＃如果顶点未开发
如果标记[vrtx] == 0：
 queue.append（vrtx）＃标记为探索
标记[vrtx] = 1＃，并将其附加到队列
输出。 append（vrtx）＃填写输出向量
返回输出
 
打印breadth_first_search（图，'A'）
  

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

解决方案

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

这不会使用BFS以外的任何其他空格。

我要使用的想法是在每个级别的末尾添加 null 。所以你遇到的null数量+1就是你所处的深度。 （当然，终止后只是级别）。

  int level = 0; 
队列< Node> quque = 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; //你遇到两个连续的`nulls`意味着你访问了所有的节点。 
 else继续; 
} 
 if（temp.right！= null）
 queue.add（temp.right）; 
 if（temp.left！= null）
 queue.add（temp.left）; 
} 
  

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.

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

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> quque = 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屋！