Как реализовать ширину первого поиска до определенной глубины?

Ответ 1

Вы можете сделать это с постоянным объемом служебных данных.

BFS обладает тем свойством, что невидимые узлы в очереди имеют глубины, которые никогда не уменьшаются, и увеличиваются не более чем на 1. Таким образом, когда вы читаете узлы из очереди BFS, вы можете отслеживать текущую глубину в одном depth, которая изначально равна 0.

Все, что вам нужно сделать, это записать, что node в очереди соответствует следующему увеличению глубины. Вы можете сделать это, просто используя переменную timeToDepthIncrease, чтобы записать количество элементов, которые уже находятся в очереди, когда вы вставляете этот node, и уменьшаете этот счетчик всякий раз, когда вы выталкиваете node из очереди.

Когда он достигнет нуля, следующий node, который вы выскочите из очереди, будет на новой, большей (на 1) глубине, поэтому:

• Приращение depth
• Установите pendingDepthIncrease в true

Всякий раз, когда вы нажимаете дочерний элемент node в очереди, сначала проверьте, является ли pendingDepthIncrease true. Если это так, этот node будет иметь большую глубину, поэтому установите timeToDepthIncrease на количество узлов в очереди, прежде чем вы нажмете его, и reset pendingDepthIncrease на false.

Наконец, остановитесь, когда depth превысит желаемую глубину! Каждый невидимый node, который может появиться позже, должен быть на этой глубине или больше.

[EDIT: Спасибо, комментатор.]

Ответ 2

Для будущих читателей посмотрите на этот пример алгоритма, описанного выше. Эта реализация будет отслеживать, сколько узлов содержит следующий уровень. При этом реализация может отслеживать текущую глубину.

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

Ответ 3

Простая идея отслеживания глубины заключается в добавлении "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;
    }

Ответ 4

Если вы не хотите иметь класс node (и добавьте глубину переменной к вашему node), то вы можете иметь две карты для расстояния и посещенияNodes или 2d Array, где каждая строка является node и column1: depth, column2: посещен. Конечно, вы можете отслеживать оба с одним map<Node,Depth> (где node - это экземпляр класса или int, String и т.д., А Depth - это int, которые представляют глубину node из корня node). если карта содержит стоимость node (O (1)), то она посещается, если не выполняется и добавляет ее для отображения с глубиной текущего node +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);
                    }
                }
            }
        }
    }
}

Ответ 5

Это работает. Предполагая, что посещаемый флаг отсутствует в Node. Если isVisited доступен, тогда нет необходимости в Tracker 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;
}