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

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

提问by user1220022

I understand and can easily implement BFS.

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

My question is, how can we make this BFS limited to a certain depth? Suppose, I just need to go 10 level deep.

我的问题是，我们如何才能将这个 BFS 限制在某个深度？假设，我只需要深入 10 级。

回答by j_random_hacker

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 depthvariable, which is initially 0.

BFS 具有队列中所有未访问节点的深度永远不会减少，最多增加 1 的属性。因此，当您从 BFS 队列中读取节点时，您可以跟踪单个depth变量中的当前深度，该变量最初是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 timeToDepthIncreaseto 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.

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

When it reaches zero, the next node you pop from the queue will be at a new, greater (by 1) depth, so:

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

• Increment depth
• Set pendingDepthIncreaseto true

• 增量 depth
• 设置pendingDepthIncrease为真

Whenever you push a child node on the queue, first check whether pendingDepthIncreaseis true. If it is, this node will have greater depth, so set timeToDepthIncreaseto the number of nodes in the queue before you push it, and reset pendingDepthIncreaseto false.

每当您将子节点推入队列时，首先检查是否pendingDepthIncrease为真。如果是，这个节点将有更大的深度，所以timeToDepthIncrease在推送之前设置为队列中的节点数，并重置pendingDepthIncrease为false。

Finally, stop when depthexceeds the desired depth! Every unvisited node that could appear later on must be at this depth or greater.

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

[EDIT: Thanks commenter keyser.]

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

回答by Rafael Winterhalter

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

回答by Somu

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.

跟踪深度的简单想法是每次深入一层时向队列添加“NULL”。一旦您从队列中轮询空值，将您的级别计数器增加 1 并将另一个“空值”添加到队列中。如果您获得两个连续的空值，您可以退出循环。

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

回答by a.s.p.

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.

如果你不想有一个类节点（并为你的节点添加一个可变深度），那么你可以有两个距离地图和visitedNodes或一个二维数组，其中每行是一个节点和column1：depth，column2：visited。当然，您可以使用一个来跟踪两者map<Node,Depth>（其中 Node 是类或 int、String 等的实例，而 Depth 是表示从根节点开始的节点深度的 int）。如果地图包含一个节点（O（1）成本），那么它被访问，如果不继续，将其添加到具有当前节点深度+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);
                    }
                }
            }
        }
    }
}

回答by Anders ?hsman

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:

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

回答by artofabhishek

This works. Assuming that visited flag is not there in Node. If isVisited is available, then there no need to tracker Map.

这有效。假设 Node.js 中没有访问过的标志。如果 isVisited 可用，则无需跟踪 Map。

// k is depth, result should not contain initialNode.
public static Collection<Node> bfsWithK_Depth(Node initialNode, int k) {

    if (initialNode == null || k <= 0) {
        return new ArrayList<>();
    }

    Queue<Node> q = new LinkedList<>();
    q.add(initialNode);
    Map<Node, Node> tracker = new HashMap(); // no need if there is visited flag.
    Collection<Node> result = new ArrayList<>();

    while (!q.isEmpty()) { // Q will be filled only with eligible nodes
        --k ;
        Node node = q.remove();
        List<Node> neighbor = node.getNeighbor();
        for (Node n : neighbor) {
            if (tracker.get(n) == null && k > 0) {
                q.add(n);
            }
            if (tracker.get(n) == null) { 
                tracker.put(n, n); 
                result.add(n); // visit this node
            }
        }

    }
    return result;
}