Wie kann man eine Breitensuche bis zu einer bestimmten Tiefe durchführen?

Question

Ich verstehe BFS und kann es leicht umsetzen.

Meine Frage ist, wie können wir dieses BFS auf eine bestimmte Tiefe beschränken? Angenommen, ich muss nur 10 Ebenen tief gehen.

Answer 1

Sie können dies mit konstantem Raum über dem Kopf tun.

BFS hat die Eigenschaft, dass alle nicht besuchten Knoten in der Warteschlange eine Tiefe haben, die niemals abnimmt und höchstens um 1 zunimmt. Wenn Sie also Knoten aus der BFS-Warteschlange lesen, können Sie die aktuelle Tiefe in einer einzigen depth die anfänglich 0 ist.

Sie brauchen nur zu notieren, welcher Knoten in der Warteschlange der nächsten Tiefenerhöhung entspricht. Dies können Sie ganz einfach mit Hilfe einer Variablen tun timeToDepthIncrease um die Anzahl der Elemente zu erfassen, die sich bereits in der Warteschlange befinden, wenn Sie diesen Knoten einfügen, und diesen Zähler zu dekrementieren, wenn Sie einen Knoten aus der Warteschlange entfernen.

Wenn sie Null erreicht, wird der nächste Knoten, den Sie aus der Warteschlange herausnehmen, eine neue, größere (um 1) Tiefe haben, also:

• Inkrement depth
• Satz pendingDepthIncrease zu wahr

Wenn Sie einen untergeordneten Knoten in die Warteschlange stellen, prüfen Sie zunächst, ob pendingDepthIncrease wahr ist. Wenn ja, hat dieser Knoten eine größere Tiefe, also setzen Sie timeToDepthIncrease auf die Anzahl der Knoten in der Warteschlange, bevor Sie sie verschieben, und setzen Sie pendingDepthIncrease auf falsch.

Halten Sie schließlich an, wenn depth übersteigt die gewünschte Tiefe! Jeder unbesuchte Knoten, der später auftauchen könnte, muss in dieser Tiefe oder höher liegen.

(EDIT: Danke an den Kommentator keyser.)

Answer 2

Für künftige Leser sei dieses Beispiel des oben beschriebenen Algorithmus angeführt. Bei dieser Implementierung wird überwacht, wie viele Knoten die folgende Ebene enthält. Auf diese Weise ist die Implementierung in der Lage, die aktuelle Tiefe im Auge zu behalten.

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

Eine einfache Idee, um die Tiefe im Auge zu behalten, besteht darin, jedes Mal, wenn Sie eine Ebene tiefer gehen, "NULL" zur Warteschlange hinzuzufügen. Sobald Sie eine Null aus der Warteschlange abrufen, erhöhen Sie Ihren Levelzähler um 1 und fügen der Warteschlange eine weitere "Null" hinzu. Wenn Sie zwei aufeinanderfolgende Nullen erhalten, können Sie die Schleife verlassen.

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

Answer 4

Wenn Sie nicht wollen, eine Klasse Knoten (und fügen Sie eine variable Tiefe zu Ihrem Knoten) dann können Sie zwei Karten für Entfernung und visitedNodes oder ein 2d Array, wo jede Zeile ist ein Knoten und Spalte1:Tiefe, Spalte2: besucht haben. Natürlich kann man beides mit einer map<Node,Depth> (wobei Node eine Instanz der Klasse oder int, String usw. ist und Depth ein int ist, das die Tiefe des Knotens vom Root-Knoten darstellt). Wenn die Karte einen Knoten enthält (O(1)-Kosten), wird er besucht, wenn nicht, wird er mit der Tiefe des aktuellen Knotens +1 zur Karte hinzugefügt.

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

Eine einfache Möglichkeit ist die Verwendung eines Wörterbuchs, um die Tiefe jedes Knotens bei der Erkundung des Graphen festzuhalten. Dann brechen Sie einfach ab, wenn die maximale Tiefe erreicht ist.

Beispiel in 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