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

algorithm java search breadth-first-search depth-first-search

2022-09-03 08:43:31

我理解并可以轻松实现BFS。

我的问题是，我们如何使这个BFS限制在一定的深度？假设，我只需要深入10级。

答案 1

您可以在开销空间恒定的情况下执行此操作。

BFS 具有这样的属性：队列中所有未访问的节点都具有永不减少的深度，并且最多增加 1。因此，当您从 BFS 队列中读取节点时，可以在单个变量（最初为 0）中跟踪当前深度。depth

您需要做的就是记录队列中的哪个节点对应于下一个深度增加。只需使用变量来记录插入此节点时队列中已存在的元素数，并在从队列中弹出节点时递减此计数器，即可执行此操作。timeToDepthIncrease

当它达到零时，您从队列中弹出的下一个节点将处于一个新的，更大的（1）深度，因此：

增加depth
设置为 truependingDepthIncrease

每当在队列上推送子节点时，请先检查是否为 true。如果是，则此节点将具有更大的深度，因此在推送之前，请设置为队列中的节点数，并重置为 false。pendingDepthIncreasetimeToDepthIncreasependingDepthIncrease

最后，在超过所需深度时停止！以后可能出现的每个未访问节点都必须处于此深度或更大深度。depth

[编辑：感谢评论者键控器。

答案 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.
}