I understand and can easily implement BFS.
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 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.
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.
When it reaches zero, the next node you pop from the queue will be at a new, greater (by 1) depth, so:
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.
[EDIT: Thanks commenter keyser.]