जावास्क्रिप्ट में चौड़ाई-प्रथम बनाम डेप्थ-प्रथम ट्री ट्रैवर्सल

जब हम एक पेड़ के माध्यम से खोज करते हैं कि क्या इसमें एक निश्चित नोड है, तो दो एल्गोरिदम हैं जो हम बना सकते हैं। हम पेड़ को चौड़ाई-पहले या गहराई-पहले दृष्टिकोण के साथ पार कर सकते हैं।

गहराई-पहली विधि पेड़ के नीचे तक जाने में विश्वास करती है जब तक कि यह एक मृत अंत तक नहीं पहुंचता। एक बार जब यह शून्य मान से टकराता है, तो यह शीर्ष पर वापस शुरू होता है और उसी प्रक्रिया का अनुसरण करता है।

चौड़ाई-पहली विधि यथासंभव शीर्ष के करीब रहने की पूरी कोशिश करती है। यह एक समय में पेड़ की एक पंक्ति को पीछे छोड़ देता है और अपने सभी सहोदर नोड्स को देखता है। अंतिम पंक्ति तक पहुंचने तक यह जारी रहता है।

एक साधारण नोड और ट्री क्लास का निर्माण

नोड वर्ग में दो गुणों वाला एक निर्माता होगा। इसमें नोड का मान संग्रहीत करने के लिए एक डेटा प्रॉपर्टी होगी और चाइल्ड प्रॉपर्टीज़ को बाल नोड्स रखने के लिए। Add () विधि का उपयोग ट्री में नए नोड्स जोड़ने के लिए किया जा सकता है और हटाने () विधि एक अवांछित बच्चे नोड को हटा देगा।

ट्री क्लास का निर्माण करते समय, हमें केवल पहले नोड को इंगित करने के लिए एक संपत्ति की आवश्यकता होती है, जिसे रूट के रूप में भी जाना जाता है।

ट्री क्लास के अंदर वह जगह है जहां हम अपने डीएफएस और बीएफएस खोज कार्यों का निर्माण नोड्स के ट्री के माध्यम से खोज करने के लिए करते हैं।

गहराई-पहले एल्गोरिथ्म

किसी वृक्ष को देखने के लिए डीएफएस दृष्टिकोण का उपयोग करके एक निश्चित मान होता है, हम एक फ़ंक्शन बनाएंगे जो संग्रह सरणी को घोषित करके शुरू होता है, जिसमें रूट नोड होगा। हम तब एक लूप का निर्माण करेंगे जो तब तक चलेगा जब तक कि सरणी के अंदर कोई मान नहीं है।

DFS नोड्स के पेड़ को नीचे गिराने के लिए एक स्टैक का उपयोग करता है। हम सरणी के पहले मूल्य को बंद करके वर्तमान नोड को घोषित करेंगे। इस नोड के साथ, हम यह जांचेंगे कि क्या इसका डेटा उस मान के बराबर है जिसे हम खोज रहे हैं। यदि इसके बराबर है, तो हम True लौटेंगे और फ़ंक्शन से बाहर निकल जाएंगे। यदि नोड का मान मेल नहीं खाता है, तो हम मौजूद होने पर उस नोड के बच्चों को सरणी के सामने धकेल देंगे। हम बच्चों को सामने लाने के लिए तैयार करते हैं क्योंकि डीएफएस दृष्टिकोण चाहता है कि हम किसी भी भाई तत्व की जांच करने से पहले पेड़ की तह तक सभी तरह से जा सकें। यदि पूरे पेड़ को खोजने के बाद कोई मूल्य नहीं मिलता है, तो हम अपने फ़ंक्शन के अंत में झूठे लौटते हैं।

चौड़ाई-पहला एल्गोरिथम

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

BFS बनाम DFS का उपयोग कब करें?

एक मूल्य की तलाश के लिए पेड़ के माध्यम से टकराने पर दोनों एल्गोरिदम काम में आ सकते हैं, लेकिन कौन सा बेहतर है? यह सब पेड़ की संरचना और आप क्या देख रहे हैं पर निर्भर करता है। यदि आप जानते हैं कि आप जिस मूल्य की तलाश कर रहे हैं वह शीर्ष के करीब है, तो बीएफएस दृष्टिकोण एक बेहतर विकल्प हो सकता है, लेकिन यदि कोई पेड़ बहुत चौड़ा है और बहुत गहरा नहीं है, तो डीएफएस दृष्टिकोण तेज और अधिक कुशल हो सकता है। बस ध्यान रखें कि कई अन्य कारक हैं जिन्हें चुनने से पहले आपको यह निर्धारित करना होगा कि कौन सा दृष्टिकोण लेना है। मुझे विश्वास है कि आप इसका पता लगाएंगे!