如何实现广度优先搜索到一定深度？

Question

我理解并且可以轻松实现BFS.

我的问题是,我们怎样才能将这个BFS限制在一定深度？假设,我只需要深入10级.

Answer 1

你可以用恒定的空间开销来做到这一点.

BFS具有以下属性:队列中未访问​​的节点都具有永不减少的深度,并且最多增加1.因此当您从BFS队列中读取节点时,您可以在单个depth变量中跟踪当前深度,这最初是0.

您需要做的就是记录队列中哪个节点对应下一个深度增加.您可以简单地通过使用变量timeToDepthIncrease来记录插入此节点时队列中已有的元素数,并在从队列中弹出节点时递减此计数器.

当它达到零时,从队列中弹出的下一个节点将处于一个新的更大(1)深度,因此:

• 增量 depth
• 设为pendingDepthIncreasetrue

无论何时在队列上推送子节点,首先要检查是否pendingDepthIncrease为真.如果是,则此节点将具有更大的深度,因此timeToDepthIncrease在推送之前设置为队列中的节点数,并重置pendingDepthIncrease为false.

最后,depth超过所需深度时停止!以后可能出现的每个未访问节点必须处于此深度或更高深度.

[编辑:感谢评论员密钥.]

Answer 2

对于未来的读者,请查看上述算法的示例.此实现将监视以下级别包含的节点数.在这样做时,该实现能够跟踪当前深度.

void breadthFirst(Node parent, int maxDepth) {

  if(maxDepth < 0) {
    return;
  }

  Queue<Node> nodeQueue = new ArrayDeque<Node>();
  nodeQueue.add(parent);

  int currentDepth = 0, 
      elementsToDepthIncrease = 1, 
      nextElementsToDepthIncrease = 0;

  while (!nodeQueue.isEmpty()) {
    Node current = nodeQueue.poll();
    process(current);
    nextElementsToDepthIncrease += current.numberOfChildren();
    if (--elementsToDepthIncrease == 0) {
      if (++currentDepth > maxDepth) return;
      elementsToDepthIncrease = nextElementsToDepthIncrease;
      nextElementsToDepthIncrease = 0;
    }
    for (Node child : current.children()) {
      nodeQueue.add(child);
    }
  }

}

void process(Node node) {
  // Do your own processing here. All nodes handed to
  // this method will be within the specified depth limit.
}