¿Cómo implementar una primera búsqueda de amplitud a cierta profundidad?

Question

Entiendo y puedo implementar fácilmente BFS.

Mi pregunta es, ¿cómo podemos hacer que esta BFS se limite a una cierta profundidad? Supongamos que solo necesito llegar a 10 niveles de profundidad.

Answer 1

Puede hacerlo con una sobrecarga de espacio constante.

BFS tiene la propiedad de que los nodos no visitados en la cola tienen profundidades que nunca disminuyen y aumentan a lo sumo 1. Para leer nodos de la cola BFS, puede realizar un seguimiento de la profundidad actual en un solo depth variable, que es inicialmente 0.

Todo lo que necesita hacer es registrar qué nodo en la cola corresponde al siguiente aumento de profundidad. Puede hacer esto simplemente usando una variable timeToDepthIncrease para registrar la cantidad de elementos que ya están en la cola cuando inserta este nodo, y disminuyendo este contador cada vez que saca un nodo de la cola.

Cuando llega a cero, el siguiente nodo que el pop de la cola estará en un nuevo, mayor (por 1) de profundidad, por lo que:

• Incremento depth
• Establecer pendingDepthIncrease a cierto

Cada vez que inserta un nodo secundario en la cola, primero verifique si pendingDepthIncrease es verdadero. Si es así, este nodo tendrá una mayor profundidad, por lo tanto, establezca timeToDepthIncrease en la cantidad de nodos en la cola antes de presionarlo, y restablezca pendingDepthIncrease en falso.

¡Finalmente, pare cuando depth exceda la profundidad deseada! Cada nodo no visitado que podría aparecer más tarde debe estar a esta profundidad o más.

[EDIT:. Gracias comentarista Keyser]

Answer 2

Para los futuros lectores, mira este ejemplo del algoritmo descrito anteriormente. Esta implementación controlará cuántos nodos contiene el siguiente nivel. Al hacerlo, la implementación puede realizar un seguimiento de la profundidad actual.

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

Answer 3

Esto funciona. Asumiendo que la bandera visitada no está allí en Nodo. Si isVisited está disponible, no es necesario rastrear 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; 
} 

Answer 4

Si usted no quiere tener un nodo de clase (y añadir una profundidad variable a su nodo), entonces puede tener dos mapas de distancia y visitedNodes o una matriz 2D donde cada fila es un nodo y column1: Profundidad , columna 2: visitado. Por supuesto, puede rastrear ambos con un map<Node,Depth> (donde el nodo es una instancia de la clase o int, cadena, etc. y la profundidad es un int que representa la profundidad del nodo desde el nodo raíz). si el mapa contiene un nodo (costo O (1)), entonces se lo visita; si no, proceda y agréguelo al mapa con la profundidad del nodo actual +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); 
        } 
       } 
      } 
     } 
    } 
} 

Answer 5

La idea fácil de hacer un seguimiento de la profundidad es agregar "NULO" a la cola cada vez que vaya a un nivel profundo. Tan pronto como sondee un nulo de la cola, aumente su contador de nivel en 1 y agregue otro 'nulo' a la cola. Si obtienes dos nulos consecutivos, puedes salir del ciclo.

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