logo标签列表

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

javaalgorithmsearchdepth-first-searchbreadth-first-search
15

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

我的问题是，我们如何将这个BFS限制在某一个深度范围内？假设我只需要搜索10层深度。

当达到最大深度时，只需停止搜索即可？ - Mat
只需在你的 BFS 程序中维护一个深度参数，这样当你达到最大深度时就不会继续搜索更深的层级。 - ControlAltDel
你能举个例子来解释一下吗？ - user1220022
通常情况下，您应该知道节点的深度。如果一个节点有多个父节点（我假设是因为您提到了它是一个图），那么深度可能是到根节点的最短或最长路径（如果没有根节点，您肯定会遇到问题）。 - Thomas
2
将节点的深度与节点本身相加，然后将其添加到您放入队列中的条目中。 - Rickard
显示剩余2条评论
7个回答
27
您可以使用常量空间开销来完成此操作。
BFS具有这样的特性：队列中未访问的节点的深度从不减少，并且最多增加1。因此，当您从BFS队列中读取节点时，可以使用单个`depth`变量跟踪当前深度，该变量最初为0。
您只需要记录队列中哪个节点对应于下一个深度增加即可。您可以通过使用一个变量`timeToDepthIncrease`来记录在插入此节点时已经在队列中的元素数量，并在弹出节点时将此计数器递减。
当它减少到零时，您从队列中弹出的下一个节点将位于新的、更大（增加1）深度上，因此：
- 递增`depth` - 将`pendingDepthIncrease`设置为true 每当您将子节点推入队列时，首先检查`pendingDepthIncrease`是否为true。如果是，则该节点将具有更大的深度，因此将`timeToDepthIncrease`设置为在将其推入之前队列中的节点数，并将`pendingDepthIncrease`重置为false。
最后，当`depth`超过所需深度时停止！每个未访问的节点都必须处于此深度或更大。
实际上，timeToDepthIncrease 保持了队列中第一个元素所在层级上一层的节点数。如果我说错了，请纠正我。算法很棒。谢谢。 - canbax
听起来没问题，但我无法确定你是否认为我的当前解释是错误/误导的。如果是这样，请问你能否澄清一下我哪里说错了？谢谢！ - j_random_hacker
1
我认为这里没有任何问题。我只是想理解算法。为了做到这一点，我认为命名很重要。我认为，与其使用timeToDepthIncrease这样的名称，不如使用cntElementsInQueueFromUpperLevel这样更具说明性但不太美观的名称。 - canbax
17

对于未来的读者，看一下上面描述的算法的示例。这个实现将监视以下级别包含的节点数。通过这样做，该实现能够跟踪当前深度。

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.
}
为什么没有访问过的向量？ - Igor L.
算法运行良好，但是许多节点被访问了多次，这会降低性能。 - Igor L.
不过，前提是我们处理一棵树。 - Rafael Winterhalter
好的，谢谢您的回复 :)也许在答案中说明假设会很有帮助。 - Igor L.
1
现在至少从评论中可以明显看出来。 - Rafael Winterhalter
如果我想重新开始某个级别，我只需要返回nodeQueue而不是返回吗？ - stephanmg
4

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

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;
    }
这是一个不错、简单的解决方案，不确定为什么它会得到-1。然而，在最坏情况下它几乎可以将最大队列大小翻倍（考虑由k条长度为n的路径组成的图，所有路径都相邻于一个作为BFS根节点的单个顶点）。 - j_random_hacker
2
如果你不想有一个类节点（并为节点添加一个变量深度），那么你可以有两个映射，分别用于距离和已访问节点，或者一个二维数组，其中每行是一个节点，第一列是深度，第二列是已访问。当然，你也可以使用一个 map<Node,Depth> 来跟踪这两个信息（其中 Node 是类的实例、int、String 等，而 Depth 是从根节点开始计算的深度）。如果 map 包含一个节点（O(1) 成本），则说明它被访问过，否则请继续进行操作，并将其添加到 map 中，并将其深度设置为当前节点深度+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);
                    }
                }
            }
        }
    }
}
1
一种简单的方法是使用字典来跟踪探索图形时每个节点的深度。然后，如果达到最大深度，就停止搜索。
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
0

这个可以工作。假设节点中没有visited标志。如果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;
}
0

这个解决方案对我很有效，它返回了在深度限制内可以访问的顶点的所有内容。


def bfs(graph,src,limit):
  v = [src]
  q = [src]
  lastElement = src
  
  while len(q) > 0 and limit > 0:
    ele = q.pop(0)

    for i in graph[ele]:
      if i not in v:
        q.append(i)
        v.append(i)

    if len(q) > 0 and ele == lastElement:        
      lastElement = q[-1]
      limit -= 1

  return v
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接