जावास्क्रिप्ट-केवल डोम ट्री ट्रैवर्सल - डीएफएस और बीएफएस?

Question

क्या कोई भी कोड, स्यूडोकोड प्रदान कर सकता है या यहां तक ​​कि सादे जावास्क्रिप्ट (डी JQuery, या किसी भी सहायक पुस्तकालयों) में डीएफएस और बीएफएस को लागू करने के लिए अच्छे लिंक भी प्रदान कर सकता है? मैं समझने की कोशिश कर रहा हूं कि या तो ट्रैवर्सल को कैसे कार्यान्वित किया जाए, लेकिन मैं वास्तव में बीएफएस और डीएफएस कार्यान्वयन के अंतर को अलग नहीं कर सकता।

यदि हम एक उदाहरण के रूप में एक ठोस समस्या चाहते हैं: मैं किसी दिए गए नोड पर डीओएम को पार करना चाहता हूं, और सभी वर्ग के नाम प्राप्त करना चाहता हूं।

(एकमात्र तरीका जिसे मैं ट्रैवर्स के बारे में सोच सकता हूं, प्रत्येक माता-पिता नोड के माध्यम से जाना है, मुझे उस नोड से जो चाहिए वह प्राप्त करें, जो इस उदाहरण में कक्षा का नाम है, फिर देखें कि उनके बच्चे हैं, प्रत्येक बच्चे के लिए भर्ती करें। मान लीजिए कि यह डीएफएस है? फिर, मुझे एक डोम ट्रैवर्सल कार्यान्वयन में मतभेदों को समझने में कठिनाई हो रही है!)

अंत में, क्षमा करें अगर यह दोहराना है। मैंने हर जगह अच्छे, स्पष्ट उदाहरणों के लिए खोज की है लेकिन मुझे कोई अच्छा जवाब नहीं मिला है! यदि पहले से ही एक अच्छा जवाब नहीं है, तो कृपया मुझे बताएँ :)

Answer 1

डीएफएस:

function m(elem){ 
elem.childNodes.forEach(function(a){ 
    m(a); 
    }); 
    //do sth with elem 
    } 
    m(document.body); 

इस गर्त सभी तत्वों लूप होता है, और प्रत्येक बच्चे और इतने पर प्रत्येक तत्व गर्त के लिए।

BFS:

var childs=[]; 
function m(elem){ 
elem.childNodes.forEach(function(a){ 
childs.push(a); 
}); 
b=childs; 
childs=[]; 
b.forEach(function(a){ 
m(a); 
}); 
} 
m(document.body); 

इस लूप तत्वों गर्त उद्यम, एक ढेर पर अपने बच्चों को धक्का, और उनमें से eeach के साथ फिर से शुरू होता है। , यह बहुत अधिक स्थान की खपत के रूप में आप देख सकते हैं (बच्चे की सरणी) जो नहीं सबसे अच्छा है ...

Answer 2

के एक उदाहरण के रूप निम्न HTML कोड का उपयोग करते हैं:

<div class="a"> 
    <div class="aa"> 
     <span class="aaa"> 
     </span> 
     <span class="aab"> 
     </span> 
    </div 
    <div class="ab"> 
     <span class="aba"> 
     </span> 
     <span class="abb"> 
     </span> 
    </div 
</div> 

डीएफएस हमेशा के लिए जाना जाएगा पहले नोड्स का अगला स्तर, और केवल तभी जब कोई और गैर-ट्रैवर्स किए गए बच्चे नोड्स वर्तमान स्तर पर अगले नोड तक पहुंच जाएंगे।

एक डीएफएस निम्न क्रम में उदाहरण के नोड्स पार होगा:

a, aa, aaa, aab, ab, aba, abb 

BFS हमेशा वर्तमान स्तर में सभी नोड्स पहले और उसके बाद ही यह नोड्स के अगले स्तर तक जाना होगा पार किए जाने की ।

एक BFS निम्न क्रम में उदाहरण के नोड्स पार होगा:

a, aa, ab, aaa, aab, aba, abb 

वहाँ एक निश्चित जवाब इनमें से जो एक का उपयोग करना चाहिए नहीं है। आमतौर पर यह आपकी आवश्यकताओं पर निर्भर करता है।

क्रियान्वयन विवरण:

एक डीएफएस लोगों के लिए अक्सर एक stack का उपयोग करें।

छद्म कोड:

stack my_stack; 
list visited_nodes; 
my_stack.push(starting_node); 

while my_stack.length > 0 
    current_node = my_stack.pop(); 

    if current_node == null 
     continue; 
    if current_node in visited_nodes 
     continue; 
    visited_nodes.add(current_node); 

    // visit node, get the class or whatever you need 

    foreach child in current_node.children 
     my_stack.push(child); 

तक वहां ढेर में किसी भी नोड्स है इस कोड को जाना होगा। प्रत्येक चरण में हमें ढेर में शीर्ष नोड मिलता है और यदि यह शून्य नहीं है और यदि हम उससे पहले नहीं गए हैं तो हम उससे पहले नहीं गए हैं और अपने सभी बच्चों को ढेर में जोड़ते हैं।

Queue आमतौर पर बीएफएस के लिए उपयोग किया जाता है।

छद्म कोड:

queue my_queue; 
list visited_nodes; 
my_queue.enqueue(starting_node); 

while my_queue.length > 0 
    current_node = my_queue.dequeue(); 

    if current_node == null 
     continue; 
    if current_node in visited_nodes 
     continue; 
    visited_nodes.add(current_node); 

    // visit node, get the class or whatever you need 

    foreach child in current_node.children 
     my_queue.enqueue(child); 

तक वहां कतार में किसी भी नोड्स है इस कोड को जाना होगा। प्रत्येक चरण में हमें कतार में पहला नोड मिलता है और यदि यह शून्य नहीं है और यदि हम उससे पहले नहीं गए हैं और हम अपने सभी बच्चों को कतार में जोड़ने से पहले नहीं गए हैं।

ध्यान दें कि दो एल्गोरिदम के बीच मुख्य अंतर डेटा प्रकार का उपयोग हम करते हैं।

Answer 3

डीएफएस के लिए आप TreeWalker या NodeIterator API का उपयोग कर सकते हैं और NodeFilter.SHOW_ELEMENT के साथ फ़िल्टर कर सकते हैं।