बीएफएस और डीएफएस के बीच अंतर

2019

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

बीएफएस और डीएफएस एक ग्राफ की खोज में उपयोग की जाने वाली ट्रैवर्सिंग विधियां हैं। ग्राफ ट्रैवर्सल ग्राफ के सभी नोड्स पर जाने की प्रक्रिया है। एक ग्राफ वर्टिकल 'V' का एक समूह है और किनारों को जोड़ने वाला 'E' एड करता है।

तुलना चार्ट

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

बीएफएस की परिभाषा

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

उदाहरण

हमारे पास एक ग्राफ है, जिसके कोने A, B, C, D, E, F, G. हैं, जो प्रारंभिक बिंदु के रूप में एक है। इस प्रक्रिया में शामिल चरण हैं:

वर्टेक्स ए का विस्तार और कतार में संग्रहित किया जाता है।
A के कार्यक्षेत्र B, D और G उत्तराधिकारी का विस्तार किया जाता है और कतार में संग्रहीत किया जाता है इस बीच वर्टेक्स ए को हटा दिया जाता है।
अब कतार के सामने के छोर पर B को उसके उत्तराधिकारी कोने E और F को संचित करने के साथ हटा दिया जाता है।
वर्टेक्स डी कतार के सामने के छोर पर है और इसे हटाए गए नोड F पर पहले से ही जाना जाता है।
वर्टेक्स जी को कतार से हटा दिया गया है, और इसमें उत्तराधिकारी ई है जो पहले से ही दौरा किया गया है।
अब ई और एफ को कतार से हटा दिया जाता है, और इसके उत्तराधिकारी शीर्ष C का पता लगाया जाता है और कतार में संग्रहीत किया जाता है।
अंत में C को भी हटा दिया जाता है और कतार खाली हो जाती है जिसका मतलब है कि हम कर चुके हैं।
उत्पन्न आउटपुट है - ए, बी, डी, जी, ई, एफ, सी।

अनुप्रयोगों-

BFS यह पता लगाने में उपयोगी हो सकता है कि ग्राफ में घटक जुड़े हैं या नहीं। और यह भी एक द्विदलीय ग्राफ का पता लगाने में इस्तेमाल किया जा सकता है।

एक ग्राफ द्विदलीय होता है जब ग्राफ कोने दो अलग-अलग सेट में विभाजित होते हैं; कोई भी दो आसन्न कोने एक ही सेट में नहीं रहेंगे। एक द्विदलीय ग्राफ की जांच करने का एक अन्य तरीका ग्राफ में एक विषम चक्र की घटना की जांच करना है। एक द्विदलीय ग्राफ में विषम चक्र नहीं होना चाहिए।

BFS भी एक नेटवर्क के रूप में देखा जा सकता है ग्राफ में सबसे छोटा रास्ता खोजने में बेहतर है।

डीएफएस की परिभाषा

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

उदाहरण

बीएफएस के समान डीएफएस संचालन करने के लिए एक ही ग्राफ लेने देता है, और इसमें शामिल कदम हैं:

अनुप्रयोग

डीएफएस के अनुप्रयोगों में दो किनारे जुड़े ग्राफ का निरीक्षण, दृढ़ता से जुड़ा ग्राफ, एसाइक्लिक ग्राफ और टोपोलॉजिकल ऑर्डर शामिल हैं ।

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

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

बीएफएस और डीएफएस के बीच महत्वपूर्ण अंतर

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

निष्कर्ष

बीएफएस और डीएफएस, दोनों ग्राफ खोज तकनीकों का समान समय चल रहा है, लेकिन अलग-अलग स्थान की खपत है, डीएफएस रैखिक स्थान लेता है, क्योंकि हमें अस्पष्टीकृत नोड्स के साथ एकल पथ को याद रखना है, जबकि बीएफएस हर नोड को स्मृति में रखता है।

डीएफएस गहन समाधान देता है और यह इष्टतम नहीं है, लेकिन यह घने होने पर अच्छी तरह से काम करता है जबकि बीएफएस इष्टतम है जो पहले से इष्टतम लक्ष्य की खोज करता है।