15

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

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

4

6 回答 6

27

您可以使用恒定的空间开销来做到这一点。

BFS 具有这样的特性，即队列中未访问​​的节点的深度都不会减少，并且最多增加 1。因此，当您从 BFS 队列中读取节点时，您可以在单个变量中跟踪当前深度，该depth变量最初是0。

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

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

  • 增量depth
  • 设置pendingDepthIncrease为真

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

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

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

于 2012-10-31T02:25:56.750 回答
16

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

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.
}
于 2013-06-04T16:57:06.580 回答
4

跟踪深度的简单想法是每次进入深度级别时将“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;
    }
于 2017-05-23T21:05:06.490 回答
2

如果你不想有一个类节点（并为你的节点添加一个可变深度），那么你可以有两个距离图和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);
                    }
                }
            }
        }
    }
}
于 2016-11-03T18:18:41.513 回答
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
于 2020-01-01T19:07:57.920 回答
0

这行得通。假设节点中不存在已访问标志。如果 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;
}
于 2016-08-06T05:04:23.863 回答