एक निश्चित गहराई के लिए पहली बार चौड़ाई को कैसे कार्यान्वित करें?

Question

मैं समझता हूं और बीएफएस को आसानी से कार्यान्वित कर सकता हूं।

मेरा सवाल है, हम इस बीएफएस को एक निश्चित गहराई तक कैसे सीमित कर सकते हैं? मान लीजिए, मुझे सिर्फ 10 स्तर की गहरी जाना है।

Answer 1

आप निरंतर अंतरिक्ष ओवरहेड के साथ ऐसा कर सकते हैं।

बीएफएस में ऐसी संपत्ति है जो कतार में अनदेखी नोड्स की गहराई में है, जो कभी भी कम नहीं होती है, और सबसे अधिक बढ़ जाती है। इसलिए जब आप बीएफएस कतार से नोड्स पढ़ते हैं, तो आप वर्तमान गहराई को एक depth में ट्रैक कर सकते हैं परिवर्तनीय, जो प्रारंभ में 0.

आपको केवल इतना करना है कि कतार में कौन सा नोड अगली गहराई में वृद्धि के अनुरूप है। जब आप इस नोड को सम्मिलित करते हैं तो कतार में पहले से मौजूद तत्वों की संख्या रिकॉर्ड करने के लिए आप एक चर timeToDepthIncrease का उपयोग कर ऐसा कर सकते हैं, और जब भी आप कतार से नोड पॉप करते हैं तो इस काउंटर को कम कर सकते हैं।

जब यह शून्य तक पहुंच, अगले नोड आप कतार से पॉप, अधिक से अधिक (1) के द्वारा गहराई है, तो एक नया पर किया जाएगा:

• वृद्धि depth
• सेट pendingDepthIncrease को सच

जब भी आप कतार पर एक बच्चे नोड को दबाते हैं, तो पहले जांचें कि pendingDepthIncrease सत्य है या नहीं। यदि ऐसा है, तो इस नोड में अधिक गहराई होगी, इसलिए इसे दबाए जाने से पहले कतार में नोड्स की संख्या के लिए timeToDepthIncrease सेट करें, और pendingDepthIncrease को गलत पर रीसेट करें।

अंत में, depth वांछित गहराई से अधिक होने पर रोकें! प्रत्येक अनदेखी नोड जो बाद में दिखाई दे सकती है, इस गहराई या अधिक पर होनी चाहिए।

[संपादित करें:। धन्यवाद टिप्पणीकार Keyser]

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

Answer 3

यह काम करता है। यह मानते हुए कि नोड में दौरा किया गया ध्वज नहीं है। यदि विज़िट किया गया है, तो ट्रैकर मानचित्र की कोई आवश्यकता नहीं है।

// 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

आप न एक वर्ग नोड है (और अपने नोड के लिए एक चर गहराई जोड़ने) करना चाहते हैं तो आप दूरी और visitedNodes या एक 2d सरणी जहां प्रत्येक पंक्ति एक नोड और स्तम्भ 1 है के लिए दो नक्शे हो सकते हैं: गहराई , कॉलम 2: विज़िट किया गया। बेशक आप एक map<Node,Depth> (जहां नोड कक्षा या int, स्ट्रिंग इत्यादि का उदाहरण है और गहराई एक int है जो रूट नोड से नोड की गहराई का प्रतिनिधित्व करता है) दोनों को ट्रैक कर सकता है। यदि मानचित्र में नोड (ओ (1) लागत है) तो यह आगे बढ़ेगा, अगर आगे बढ़ें और इसे वर्तमान नोड +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

गहराई का ट्रैक रखने के लिए आसान विचार है जब भी आप गहरा स्तर पर जाते हैं तो कतार में "न्यूल" जोड़ना होता है। जैसे ही आप कतार से एक नल को मतदान करते हैं, अपने स्तर के काउंटर को 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; 
    }