बीएफएस बनाम डीएफएस – उनके बीच अंतर

बीएफएस क्या है?

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

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

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

डीएफएस क्या है?

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

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

बीएफएस और डीएफएस के बीच महत्वपूर्ण अंतर यहां दिए गए हैं।

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

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

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

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

चरण 1)

आपके पास 0 से 6 तक की सात संख्याओं का ग्राफ है।

चरण 2)

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

चरण 3)

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

चरण 4)

शेष 0 आसन्न और अप्रयुक्त नोड्स का दौरा किया जाता है, उन्हें चिह्नित किया जाता है, और कतार में डाला जाता है।

चरण 5)

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

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

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

चरण 1)

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

चरण 2)

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

चरण 3)

शीर्ष 2 के पास शीर्ष 4 में एक अप्रयुक्त शीर्ष है। इसलिए, हम उसे स्टैक में जोड़ते हैं और उस पर जाते हैं।

चरण 4)

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

बीएफएस के अनुप्रयोग

बीएफएस के अनुप्रयोग इस प्रकार हैं:

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

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

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

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

वेब क्रॉलर

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

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

एक प्रसारित पैकेट को BFS एल्गोरिथ्म द्वारा निर्देशित किया जाता है ताकि वह उन सभी नोड्स को ढूंढ सके और उन तक पहुंच सके जिनके लिए उसका पता उपलब्ध है।

डीएफएस के अनुप्रयोग

डीएफएस के महत्वपूर्ण अनुप्रयोग इस प्रकार हैं:

भारित ग्राफ़

भारित ग्राफ में, DFS ग्राफ ट्रैवर्सल सबसे छोटा पथ वृक्ष और न्यूनतम स्पैनिंग वृक्ष उत्पन्न करता है।

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

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

पथ खोज

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

टोपोलॉजिकल सॉर्टिंग

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

किसी ग्राफ के दृढ़तापूर्वक जुड़े घटकों की खोज करना

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

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

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