How to implement a breadth first search to a certain depth?

Question

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.

Solution 1

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:

• Increment depth
• Set pendingDepthIncrease to true

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.]

Solution 2

For future readers, look at this example of the algorithm described above. This implementation will monitor how many nodes the following level contains. In doing so, the implementation is able to keep track of the current depth.

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

Solution 3

The easy Idea for keeping track of the depth is to add "NULL" to the Queue every time you go a level deep. As soon as you poll a null from the queue, Increase your level counter by 1 and add another 'null' to the Queue. If you get two consecutive nulls you can exit from the loop.

q.offer(user);
q.offer(null);

user.setVisited(true);

while(!q.isEmpty()){

    User userFromQ = q.poll();

    if(userFromQ == null){
        level++;
        q.offer(null);
        if(q.peek()==null)
            break;
        else
            continue;
    }

Solution 4

If you dont want to have a class node (and add a variable depth to your node) then you can have two maps for distance and visitedNodes or a 2d Array where each row is a node and column1:depth, column2: visited. Of course you can track both with one map<Node,Depth> (where Node is an instance of the class or int,String etc and Depth is an int that represent the Depth of the Node from the root node). if map contains a node (O(1) cost) then it is visited, if not proceed and add it to map with depth of current node +1.

public static void BfsToDepth(graph graphDb, Node rootNode, int depth) {
    if(depth<1)
       return;
    Queue<Node> queue = new LinkedList<>();
    ResourceIterator<Node> nodesIterator = graphDb.getAllNodes().iterator();
    LinkedHashMap<Node, Boolean> visited = new LinkedHashMap<>();
    LinkedHashMap<Node, Integer> distance = new LinkedHashMap<>();
    // Start: Bfs Init Step
    if (nodesIterator.hasNext() == true) {
        while (nodesIterator.hasNext()) {
            Node currentNode = nodesIterator.next();
            visited.put(currentNode, false);
            distance.put(currentNode, Integer.MAX_VALUE);
        }
    } else {
        System.out.println("No nodes found");
    }
    // End: Bfs Init Step 

    distance.put(rootNode, 0);
    visited.put(rootNode, true);
    queue.add(rootNode);
    Node current = null;

    while (queue.isEmpty() == false) {
        current = queue.poll();
        if (distance.get(current) <= depth) {
            Iterator<Relationship> relationships = current.getRelationships().iterator();
            if (relationships.hasNext() == true) {
                while (relationships.hasNext()) {
                    Relationship relationship = relationships.next();
                    Node adjacent = relationship.getOtherNode(current);

                    if (visited.get(adjacent) == false) {
                        /*if you want to print the distance of each node from root then 
                        System.out.println("len: "+ (distance.get(current) + 1)+" to: "+ adjacent);*/
                        distance.put(adjacent, (distance.get(current) + 1));
                        visited.put(adjacent, true);
                        queue.add(adjacent);
                    }
                }
            }
        }
    }
}

Solution 5

One simple way is to use a dictionary to keep track of the depth of each node when exploring the graph. Then just break if the max depth is reached.

Example in Python:

from collections import deque

def bfs_maxdepth(graph, start, maxdepth):
    queue = deque([start])
    depths = {start: 0}
    while queue:
        vertex = queue.popleft()
        if depths[vertex] == maxdepth:
            break
        for neighbour in graph[vertex]:
            if neighbour in depths:
                continue
            queue.append(neighbour)
            depths[neighbour] = depths[vertex] + 1
    return depths

View more solutions

Comments

[Mat]

Just stop searching when you've reached the max depth?

[ControlAltDel]

just maintain a depth parameter is your bfs routine so that when you hit max you don't keep searching deeper

[user1220022]

Can you explain with an exmaple?

[Thomas]

Example: if(currentdepth > maxdepth) { /*stop*/ } (or if( currentdepth < maxdepth) { /*put children to visit list*/ }), there's nothing complicated to that.

[user1220022]

Yes but the problem is to keep track of the current depth. With a queue (on a graph not tree)

[Thomas]

Well, you normally should know the depth of a node. If a node does have multiple parents (I assume so since you mentioned it being a graph) then the depth might either be the shortest or longest path to the root (if there is no root you'll have a problem anyways).

[Rickard]

Add the depth of the node together with the node to the entry you put in your queue.

[Igor L.]

Why no visited vector?

[Igor L.]

Algorithm works well, but a lot of nodes have been visited more than once, which doesn't raise the performance

[Rafael Winterhalter]

Not if you assume that we handle a tree.

[Igor L.]

Good to know, thanks for our reply :) Maybe it would be good to inform about the asumption in the answer.

[Rafael Winterhalter]

It's at least obvious from the comments now.

[Ankit Roy]

This is a nice, simple solution, not sure why it got a -1. It can in the worst case almost double the maximum queue size, however (consider a graph consisting of k paths of length n, all adjacent to a single vertex that is the root of the BFS).

[stephanmg]

If I want to restart at a certain level, would I just return nodeQueue instead of return?

[canbax]

actually timeToDepthIncrease keeps the number of nodes in the queue from the upper level of the first element of a level. Correct me if I'm wrong. Nice algorithms. Thanks

[Ankit Roy]

That sounds right, but I can't tell if you are claiming that my current explanation is wrong/misleading. If you are, could you clarify where you think I'm going wrong? Thanks!

[canbax]

I don't think anything wrong here. I just wanted to understand the algorithm. To do that I think naming is important. I think instead of timeToDepthIncrease a name like cntElementsInQueueFromUpperLevel more explanatory and ugly ;)