如何实现广度优先搜索到一定深度？
我理解并且可以轻松实现BFS。
我的问题是，我们怎样才能将这个BFS限制在一定深度？ 假设，我只需要深入10级。
你可以用恒定的空间开销来做到这一点。
BFS具有以下属性：队列中未访问的节点都具有永不减少的深度，并且最多增加1.因此，当您从BFS队列中读取节点时，您可以在单个depth变量中跟踪当前深度，这是最初为0。
您需要做的就是记录队列中哪个节点对应下一个深度增加。 您可以通过使用变量timeToDepthIncrease来记录插入此节点时队列中已有的元素数，并在从队列中弹出节点时递减此计数器。
当它达到零时，从队列中弹出的下一个节点将处于一个新的更大（1）深度，因此：
- 增加
depth - 将
pendingDepthIncrease设置为true
每当您在队列上推送子节点时，首先检查pendingDepthIncrease是否为true。 如果是，则此节点将具有更大的深度，因此在推送之前将timeToDepthIncrease设置为队列中的节点数，并将pendingDepthIncrease重置为false。
最后，当depth超过所需深度时停止！ 以后可能出现的每个未访问节点必须处于此深度或更高深度。
[编辑：谢谢评论员密钥。]
对于未来的读者，请查看上述算法的示例。 此实现将监视以下级别包含的节点数。 在这样做时，该实现能够跟踪当前深度。
void breadthFirst(Node parent, int maxDepth) { if(maxDepth < 0) { return; } Queue nodeQueue = new ArrayDeque (); 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. }
跟踪深度的简单想法是每次深入时向队列添加“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; }
如果你不想拥有一个类节点（并向你的节点添加一个变量深度），那么你可以有两个distance和visitedNodes映射或一个2d Array，其中每一行是一个节点，column1：depth，column2：visited。 当然，您可以使用一个map （其中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 queue = new LinkedList<>(); ResourceIterator nodesIterator = graphDb.getAllNodes().iterator(); LinkedHashMap visited = new LinkedHashMap<>(); LinkedHashMap 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 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); } } } } } }
这很有效。 假设在Node中没有访问标志。 如果isVisited可用，则无需跟踪Map。
// k is depth, result should not contain initialNode. public static Collection bfsWithK_Depth(Node initialNode, int k) { if (initialNode == null || k <= 0) { return new ArrayList<>(); } Queue q = new LinkedList<>(); q.add(initialNode); Map tracker = new HashMap(); // no need if there is visited flag. Collection result = new ArrayList<>(); while (!q.isEmpty()) { // Q will be filled only with eligible nodes --k ; Node node = q.remove(); List 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; }