如何实现一个广度优先搜索，以一定的深度？ [英] How to implement a breadth first search to a certain depth?
问题描述
我了解并能轻松实现BFS。
I understand and can easily implement BFS.
我的问题是，我们如何使该BFS限制到一定深度？假设，我只是需要走10级深。
My question is, how can we make this BFS limited to a certain depth? Suppose, I just need to go 10 level deep.
推荐答案
您可以用恒定的空间开销做到这一点。
You can do this with constant space overhead.
BFS具有这样的性质，在队列中未访问节点都有深处，从来没有下降，并增加至多为1。所以，当你从BFS队列中读取节点，可以跟踪当前的深度在一个单一的深度变量，它最初是0。
BFS has the property that unvisited nodes in the queue all have depths that never decrease, and increase by at most 1. So as you read nodes from the BFS queue, you can keep track of the current depth in a single depth variable, which is initially 0.
所有你需要做的是哪个节点队列对应于下一个深度增加记录。你可以简单地通过使用一个变量 timeToDepthIncrease 来记录那些已经在队列中的元素个数，当您插入此节点，和递减这个计数器，每当你弹出一个节点做到这一点从队列中
All you need to do is record which node in the queue corresponds to the next depth increase. You can do this simply by using a variable timeToDepthIncrease to record the number of elements that are already in the queue when you insert this node, and decrementing this counter whenever you pop a node from the queue.
当它达到零时，就从队列中弹出下一个节点将在一个新的，更大的（由1）的深度，这样：
When it reaches zero, the next node you pop from the queue will be at a new, greater (by 1) depth, so:
- 增量
深度 - 设置
pendingDepthIncrease真
- Increment
depth - Set
pendingDepthIncreaseto true
当你把一个子节点上的队列，首先检查是否 pendingDepthIncrease 是真实的。如果是，该节点将拥有更大的深度，所以设置 timeToDepthIncrease 来推入，并重置前的队列中的节点数<code> pendingDepthIncrease 为false。
Whenever you push a child node on the queue, first check whether pendingDepthIncrease is true. If it is, this node will have greater depth, so set timeToDepthIncrease to the number of nodes in the queue before you push it, and reset pendingDepthIncrease to false.
最后，停车时深度超过所需的深度！可能出现以后每个未访问节点必须在这个深度以上。
Finally, stop when depth exceeds the desired depth! Every unvisited node that could appear later on must be at this depth or greater.
这篇关于如何实现一个广度优先搜索，以一定的深度？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
