如何在广度优先搜索中跟踪深度？

Question

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

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

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

Answer 1

实际上，我们不需要额外的队列来存储深度，也不需要添加null来判断是否是当前级别的结束。我们只需要知道当前关卡有多少个节点，那么我们就可以处理同一个关卡中的所有节点，完成后将关卡增加1。

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

Answer 2

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

除了用于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);
     }

Answer 3

维护一个队列，该队列存储BFS队列中相应节点的深度。供您参考的示例代码：

queue bfsQueue, depthQueue;
bfsQueue.push(firstNode);
depthQueue.push(0);
while (!bfsQueue.empty()) {
    f = bfsQueue.front();
    depth = depthQueue.front();
    bfsQueue.pop(), depthQueue.pop();
    for (every node adjacent to f) {
        bfsQueue.push(node), depthQueue.push(depth+1);
    } 
}

此方法简单又幼稚，对于O（1）额外的空间，您可能需要@stolen_leaves的答案。

Answer 4

试试看这个帖子。它使用变量跟踪深度currentDepth

/sf/answers/1184640831/

对于您的实现，请跟踪最左边的节点和深度变量。每当最左边的节点从队列中弹出时，您就知道您达到了一个新级别并增加了深度。

所以，你的根是leftMostNode0 级。那么最左边的孩子是leftMostNode。一旦你点击它，它就会变成级别 1。这个节点最左边的孩子是下一个leftMostNode，依此类推。