बीएफएस बनाम डीएफएस: अंतर जानिए

BFS क्या है?

बीएफएस एक एल्गोरिथ्म है जो डेटा को ग्राफ़ करने या पेड़ या ट्रैवर्सिंग संरचनाओं को खोजने के लिए उपयोग किया जाता है। एल्गोरिथ्म कुशलता से एक सही चौड़ाई के फैशन में एक ग्राफ में सभी प्रमुख नोड्स पर जाता है और चिह्नित करता है।

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

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

इसमें बीएसएफ बनाम DFS बाइनरी ट्री ट्यूटोरियल, आप सीखेंगे:

• BFS क्या है?
• DFS क्या है?
• बीएफएस का उदाहरण
• डीएफएस का उदाहरण
• बीएफएस और डीएफएस बाइनरी ट्री के बीच अंतर
• बीएफएस के आवेदन
• डीएफएस के आवेदन

DFS क्या है?

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

बीएफएस का उदाहरण

डीएफएस के निम्नलिखित उदाहरण में, हमने 6 वर्टिकल वाले ग्राफ का उपयोग किया है।

बीएफएस का उदाहरण

चरण 1)

आपके पास 0 - 6 से लेकर सात नंबरों का ग्राफ है।

चरण 2)

0 या शून्य को रूट नोड के रूप में चिह्नित किया गया है।

चरण 3)

0 का दौरा, चिह्नित, और कतार डेटा संरचना में डाला जाता है।

चरण 4)

शेष 0 आसन्न और गैर-स्वीकृत नोड का दौरा किया जाता है, चिह्नित किया जाता है, और कतार में डाला जाता है।

चरण 5)

सभी नोड्स का दौरा किए जाने तक ट्रैवर्सिंग पुनरावृत्तियों को दोहराया जाता है।

डीएफएस का उदाहरण

DFS के निम्नलिखित उदाहरण में, हमने 5 सिरों वाले अप्रत्यक्ष ग्राफ का उपयोग किया है।

चरण 1)

हमने वर्टेक्स 0. से शुरू किया है। एल्गोरिथ्म इसे विज़िट की गई सूची में डालने के साथ शुरू होता है और साथ ही इसके सभी सटे हुए सिरों को डेटा संरचना में डाल देता है।

चरण 2)

आप तत्व का दौरा करेंगे, जो स्टैक के शीर्ष पर है, उदाहरण के लिए, 1 और इसके आस-पास के नोड्स पर जाएं। ऐसा इसलिए है क्योंकि 0 का दौरा पहले ही हो चुका है। इसलिए, हम शीर्ष 2 पर जाते हैं।

चरण 3)

वर्टेक्स 2 में 4 में एक पास की परिकल्पना है। इसलिए, हम इसे स्टैक में जोड़ते हैं और इसे देखते हैं।

चरण 4)

अंत में, हम अंतिम शीर्ष 3 पर जाएंगे, इसमें किसी भी तरह के गैर-समीपवर्ती नोड नहीं हैं। हमने डीएफएस एल्गोरिथ्म का उपयोग करके ग्राफ के ट्रावेल को पूरा किया है।

बीएफएस और डीएफएस बाइनरी ट्री के बीच अंतर

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

बीएफएस के आवेदन

यहाँ, BFS के अनुप्रयोग हैं:

अन-भारित रेखांकन:

उच्च सटीकता के साथ कम से कम समय में ग्राफ के सभी छोरों पर जाने के लिए बीएफएस एल्गोरिदम आसानी से सबसे छोटा रास्ता और न्यूनतम फैले हुए पेड़ बना सकता है।

पी 2 पी नेटवर्क:

सहकर्मी से सहकर्मी नेटवर्क तक सभी निकटतम या पड़ोसी नोड्स का पता लगाने के लिए बीएफएस लागू किया जा सकता है। इससे जरूरी डेटा तेजी से मिल जाएगा।

वेब क्रॉलर:

खोज इंजन या वेब क्रॉलर आसानी से बीएफएस को नियोजित करके अनुक्रमित के कई स्तरों का निर्माण कर सकते हैं। बीएफएस कार्यान्वयन स्रोत से शुरू होता है, जो वेब पेज है, और फिर यह उस स्रोत से सभी लिंक पर जाता है।

नेटवर्क प्रसारण:

एक प्रसारण पैकेट को बीएफएस एल्गोरिथ्म द्वारा निर्देशित किया गया है और इसके लिए सभी नोड्स को खोजने और पहुंचने के लिए है।

डीएफएस के आवेदन

यहां डीएफएस के महत्वपूर्ण आवेदन दिए गए हैं:

भारित ग्राफ़:

भारित ग्राफ में, डीएफएस ग्राफ ट्रैवर्सल सबसे छोटा रास्ता पेड़ और न्यूनतम फैले हुए पेड़ उत्पन्न करता है।

एक ग्राफ में एक चक्र का पता लगाना:

यदि हम DFS के दौरान बैक एज पाते हैं तो ग्राफ में एक चक्र होता है। इसलिए, हमें ग्राफ़ के लिए DFS चलाना चाहिए और बैक किनारों के लिए सत्यापन करना चाहिए।

रास्ता पाना:

हम दो चक्करों के बीच एक रास्ता खोजने के लिए डीएफएस एल्गोरिथ्म में विशेषज्ञ कर सकते हैं।

सामयिक छँटाई:

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

एक ग्राफ के मजबूती से जुड़े घटकों की खोज:

डीएफएस ग्राफ में इसका उपयोग तब किया जाता है जब ग्राफ में प्रत्येक और हर वर्टेक्स से अन्य शेष वर्टेक्स तक का रास्ता होता है।

केवल एक समाधान के साथ पहेलियाँ सुलझाना:

डीएफएस एल्गोरिथ्म को आसानी से विज़िट किए गए सेट में मौजूदा पथ पर नोड्स को शामिल करके भूलभुलैया के सभी समाधानों को खोजने के लिए अनुकूलित किया जा सकता है।

प्रमुख आयाम:

• बीएफएस गंतव्य के लिए सबसे छोटा रास्ता खोजता है जबकि डीएफएस एक सबट्री के निचले हिस्से में जाता है, फिर पीछे जाता है।
• BFS का पूर्ण रूप चौड़ाई-प्रथम खोज है जबकि DFS का पूर्ण रूप गहराई प्रथम खोज है।
• BFS विज़िट करने के लिए अगले स्थान का ट्रैक रखने के लिए एक कतार का उपयोग करता है। जबकि DFS विज़िट करने के लिए अगले स्थान का ट्रैक रखने के लिए स्टैक का उपयोग करता है।
• बीएफएस ट्री लेवल के हिसाब से ट्रेस होता है जबकि डीएफएस पेड़ की गहराई के हिसाब से ट्रेस होता है।
• दूसरी ओर BFS को FIFO सूची का उपयोग करके कार्यान्वित किया जाता है, दूसरी ओर DFS को LIFO सूची का उपयोग करके कार्यान्वित किया जाता है।
• बीएफएस में, आप कभी भी सीमित छोरों में नहीं फंस सकते हैं जबकि डीएफएस में आप अनंत छोरों में फंस सकते हैं।