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

Das funktioniert. Angenommen, das visited-Flag ist nicht in Node. Wenn isVisited vorhanden ist, dann gibt es keine Notwendigkeit, 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;
}

Answer 2

Diese Lösung funktionierte für mich, es gibt alle Inhalte der Scheitelpunkt, die innerhalb der Tiefe Grenze zugänglich sein kann.

def bfs(graph,src,limit):
  v = [src]
  q = [src]
  lastElement = src

  while len(q) > 0 and limit > 0:
    ele = q.pop(0)

    for i in graph[ele]:
      if i not in v:
        q.append(i)
        v.append(i)

    if len(q) > 0 and ele == lastElement:        
      lastElement = q[-1]
      limit -= 1

  return v