उदाहरण के साथ ब्रेडथ फर्स्ट सर्च (BFS) एल्गोरिदम
सारा चेन
⚡ स्मार्ट सारांश
ब्रेथ फर्स्ट सर्च (बीएफएस) एक एल्गोरिदम है जो ग्राफ को स्तर दर स्तर पार करता है, गहराई में जाने से पहले एक नोड के सभी पड़ोसियों का दौरा करता है। यह एक एफआईएफओ कतार का उपयोग करता है और अनंत लूप के बिना भारहीन ग्राफ में सबसे छोटा पथ ढूंढता है।
बीएफएस एल्गोरिदम (ब्रेडथ-फर्स्ट सर्च) क्या है?
ब्रॉडथ-फर्स्ट सर्च (बीएफएस) एक एल्गोरिदम है जिसका उपयोग डेटा को ग्राफ़ करने, ट्री में खोजने या संरचनाओं को पार करने के लिए किया जाता है। बीएफएस का पूरा नाम ब्रॉडथ-फर्स्ट सर्च है।
यह एल्गोरिथ्म ग्राफ में सभी प्रमुख नोड्स को कुशलतापूर्वक देखता है और उन्हें सटीक चौड़ाई में चिह्नित करता है। यह एल्गोरिथ्म ग्राफ में एक नोड (प्रारंभिक या स्रोत बिंदु) का चयन करता है और फिर चयनित नोड के आस-पास के सभी नोड्स को देखता है। याद रखें, BFS इन नोड्स को एक-एक करके एक्सेस करता है।
एक बार जब एल्गोरिथ्म आरंभिक नोड पर जाता है और उसे चिह्नित करता है, तो यह निकटतम अप्रयुक्त नोड्स की ओर बढ़ता है और उनका विश्लेषण करता है। एक बार दौरा करने के बाद, सभी नोड्स को चिह्नित किया जाता है। ये पुनरावृत्तियाँ तब तक जारी रहती हैं जब तक कि ग्राफ के सभी नोड्स को सफलतापूर्वक दौरा और चिह्नित नहीं किया जाता है।
ग्राफ ट्रैवर्सल क्या है?
ग्राफ ट्रैवर्सल ग्राफ में शीर्ष स्थान का पता लगाने के लिए आमतौर पर इस्तेमाल की जाने वाली पद्धति है। यह एक उन्नत खोज एल्गोरिथ्म है जो विज़िट किए गए शीर्षों के अनुक्रम को चिह्नित करने के साथ-साथ गति और सटीकता के साथ ग्राफ का विश्लेषण कर सकता है। यह प्रक्रिया आपको अनंत लूप में बंद हुए बिना ग्राफ में प्रत्येक नोड को जल्दी से देखने में सक्षम बनाती है।
बीएफएस एल्गोरिथम की वास्तुकला
- डेटा के विभिन्न स्तरों में, आप किसी भी नोड को ट्रैवर्सिंग शुरू करने के लिए आरंभिक नोड के रूप में चिह्नित कर सकते हैं। बीएफएस उस नोड पर जाएगा, उसे विज़िट किया गया के रूप में चिह्नित करेगा और उसे क्यू में डाल देगा।
- अब बीएफएस निकटतम और अब तक विज़िट न किए गए नोड्स पर जाएगा और उन्हें चिह्नित करेगा। ये मान भी कतार में जोड़ दिए जाते हैं। कतार निम्नलिखित आधारों पर कार्य करती है: फीफो मॉडल.
- इसी प्रकार, ग्राफ़ पर शेष निकटतम और अप्रकाशित नोड्स का विश्लेषण किया जाता है, उन्हें चिह्नित किया जाता है और कतार में जोड़ा जाता है। प्राप्त होते ही इन आइटमों को कतार से हटा दिया जाता है और परिणाम के रूप में प्रिंट किया जाता है।
हमें बीएफएस एल्गोरिदम की आवश्यकता क्यों है?
अपने डेटासेट में खोज करने के लिए बीएफएस एल्गोरिदम का उपयोग करने के कई कारण हैं। इस एल्गोरिदम को आपकी पहली पसंद बनाने वाले कुछ सबसे महत्वपूर्ण पहलू इस प्रकार हैं:
- बीएफएस ग्राफ में नोड्स का विश्लेषण करने और इनसे होकर गुजरने का सबसे छोटा रास्ता बनाने के लिए उपयोगी है।
- बीएफएस न्यूनतम पुनरावृत्तियों में ग्राफ को पार कर सकता है।
- बीएफएस एल्गोरिथम की वास्तुकला सरल और मजबूत है।
- बीएफएस एल्गोरिथम का परिणाम अन्य एल्गोरिथम की तुलना में उच्च स्तर की सटीकता रखता है।
- बीएफएस पुनरावृत्तियाँ निर्बाध हैं, और इस एल्गोरिथम के अनंत लूप समस्या में फंसने की कोई संभावना नहीं है।
बीएफएस एल्गोरिथ्म कैसे काम करता है?
ग्राफ़ ट्रैवर्सल के लिए एल्गोरिथ्म को पेड़ जैसी संरचना में हर एक अन-विजिटेड नोड पर जाना, जाँचना और/या अपडेट करना आवश्यक है। ग्राफ़ ट्रैवर्सल को उस क्रम के अनुसार वर्गीकृत किया जाता है जिसमें वे ग्राफ़ पर नोड्स पर जाते हैं।
बीएफएस एल्गोरिदम ग्राफ में पहले या शुरुआती नोड से ऑपरेशन शुरू करता है और इसे पूरी तरह से पार करता है। एक बार जब यह प्रारंभिक नोड को सफलतापूर्वक पार कर लेता है, तो ग्राफ में अगले गैर-पार किए गए शीर्ष पर जाकर उसे चिह्नित किया जाता है।
अतः, आप कह सकते हैं कि पहले पुनरावृति में वर्तमान शीर्ष से सटे सभी नोड्स का दौरा किया जाता है और उन्हें पार किया जाता है। बीएफएस एल्गोरिदम के कार्य को लागू करने के लिए एक सरल कतार पद्धति का उपयोग किया जाता है, और इसमें निम्नलिखित चरण शामिल हैं:
चरण 1)
ग्राफ में प्रत्येक शीर्ष या नोड ज्ञात है। उदाहरण के लिए, आप नोड को V के रूप में चिह्नित कर सकते हैं।
चरण 2)
यदि वर्टेक्स V तक पहुंच नहीं हो पा रही है, तो वर्टेक्स V को BFS कतार में जोड़ दें।
चरण 3)
बीएफएस खोज शुरू करें, और पूरा होने के बाद, वर्टेक्स V को विज़िट किया गया के रूप में चिह्नित करें।
चरण 4)
बीएफएस कतार अभी भी खाली नहीं है, इसलिए कतार से ग्राफ के शीर्ष V को हटा दें।
चरण 5)
ग्राफ पर मौजूद उन सभी शेष शीर्षों को पुनः प्राप्त करें जो शीर्ष V से सटे हुए हैं।
चरण 6)
प्रत्येक आसन्न शीर्ष (मान लीजिए V1) के लिए, यदि उस पर अभी तक जाया नहीं गया है, तो V1 को BFS कतार में जोड़ें।
चरण 7)
बीएफएस वी1 पर जाएगा, उसे विज़िट किया हुआ चिह्नित करेगा और उसे कतार से हटा देगा।
उदाहरण बीएफएस एल्गोरिथ्म
चरण 1)
आपके पास 0 से 6 तक की सात संख्याओं का एक ग्राफ है।
चरण 2)
0 या शून्य को मूल नोड के रूप में चिह्नित किया गया है।
चरण 3)
0 को देखा जाता है, चिह्नित किया जाता है, और कतार डेटा संरचना में डाला जाता है।
चरण 4)
शेष 0-समीपवर्ती और अनविज़िटेड नोड्स को विज़िट किया जाता है, चिह्नित किया जाता है और कतार में डाला जाता है।
चरण 5)
ट्रैवर्सिंग पुनरावृत्तियों को तब तक दोहराया जाता है जब तक कि सभी नोड्स का दौरा नहीं किया जाता।
बीएफएस एल्गोरिथम के नियम
बीएफएस एल्गोरिदम का उपयोग करने के लिए यहां कुछ महत्वपूर्ण नियम दिए गए हैं:
- एक कतार (FIFO – फर्स्ट इन फर्स्ट आउट) डेटा संरचना बीएफएस द्वारा उपयोग किया जाता है.
- आप ग्राफ में किसी भी नोड को रूट के रूप में चिह्नित करते हैं और वहां से डेटा को ट्रैवर्स करना शुरू करते हैं।
- BFS ग्राफ के सभी नोड्स को पार करता है और ड्रॉप करता रहता हैping उन्हें पूर्ण के रूप में चिह्नित किया गया।
- बीएफएस एक निकटवर्ती अप्रयुक्त नोड पर जाता है, उसे पूर्ण के रूप में चिह्नित करता है, तथा उसे कतार में सम्मिलित करता है।
- यदि कोई आसन्न शीर्ष नहीं मिलता है, तो यह कतार से पिछले शीर्ष को हटा देता है।
- बीएफएस एल्गोरिदम तब तक चलता रहता है जब तक कि ग्राफ के सभी शीर्षों को सफलतापूर्वक पार नहीं कर लिया जाता और उन्हें पूर्ण के रूप में चिह्नित नहीं कर दिया जाता।
- किसी भी नोड से डेटा के आवागमन के दौरान BFS के कारण कोई लूप उत्पन्न नहीं होता।
बीएफएस एल्गोरिथ्म के अनुप्रयोग
आइए कुछ वास्तविक जीवन अनुप्रयोगों पर नजर डालें जहां बीएफएस एल्गोरिदम कार्यान्वयन अत्यधिक प्रभावी हो सकता है।
- अभारित ग्राफ़: बीएफएस एल्गोरिदम उच्च सटीकता के साथ कम से कम समय में ग्राफ के सभी शीर्षों का दौरा करने के लिए सबसे छोटा पथ और न्यूनतम स्पैनिंग ट्री आसानी से बना सकता है।
- पी2पी नेटवर्क: पीयर-टू-पीयर नेटवर्क में सभी निकटतम या पड़ोसी नोड्स का पता लगाने के लिए बीएफएस (BFS) का उपयोग किया जा सकता है। इससे आवश्यक डेटा को तेजी से खोजा जा सकेगा।
- वेब क्रॉलर: सर्च इंजन या वेब क्रॉलर आसानी से BFS का उपयोग करके इंडेक्स के कई स्तरों का निर्माण कर सकते हैं। BFS कार्यान्वयन स्रोत से शुरू होता है, जो वेब पेज है, और फिर यह उस स्रोत से सभी लिंक पर जाता है।
- नेविगेशन सिस्टम: बीएफएस मुख्य या स्रोत स्थान से सभी पड़ोसी स्थानों को खोजने में मदद कर सकता है।
- नेटवर्क प्रसारण: एक प्रसारित पैकेट को BFS एल्गोरिथ्म द्वारा निर्देशित किया जाता है ताकि वह उन सभी नोड्स को ढूंढ सके और उन तक पहुंच सके जिनके लिए उसका पता उपलब्ध है।
