如何实现广度优先搜索到一定深度？-Java 学习之路

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

我的问题是，我们怎样才能将这个BFS限制在一定深度？假设，我只需要深入10级 .

5 回答

14
你可以用恒定的空间开销来做到这一点 .

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

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

当它达到零时，从队列中弹出的下一个节点将处于一个新的更大（1）深度，因此：
- 增量 depth
- 将 pendingDepthIncrease 设为true
无论何时在队列中推送子节点，首先要检查 pendingDepthIncrease 是否为真 . 如果是，则此节点将具有更大的深度，因此在推送之前将 timeToDepthIncrease 设置为队列中的节点数，并将 pendingDepthIncrease 重置为false .

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

[EDIT: Thanks commenter keyser.]
回复于 2024-05-10T01:53:47+08:00

对于未来的读者，请查看上述算法的示例 . 此实现将监视以下级别包含的节点数 . 在这样做时，该实现能够跟踪当前深度 .

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

回复于 2024-05-10T01:53:47+08:00

0
跟踪深度的简单想法是每次深入时向队列添加“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;
    }
```
回复于 2024-05-10T01:53:47+08:00

如果你不想拥有一个类节点（并向你的节点添加一个变量深度），那么你可以有两个distance和visitedNodes的映射，或者一个2d Array，其中每一行是一个节点，column1：depth，column2：visited . 当然，您可以使用一个 map<Node,Depth> （其中Node是类或int的实例，String等）来跟踪两者，而Depth是一个int，表示从根节点到节点的深度 . 如果map包含一个节点（O（1）cost），则访问它，如果不继续，则将其添加到当前节点1的深度的map中 .

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

回复于 2024-05-10T01:53:47+08:00

这很有效 . 假设在Node中没有访问标志 . 如果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;
}

回复于 2024-05-10T01:53:47+08:00

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

5 回答

相关问题