उदाहरण के साथ ब्रेडथ फर्स्ट सर्च (BFS) एल्गोरिदम

बीएफएस एल्गोरिदम (ब्रेडथ-फर्स्ट सर्च) क्या है?

ब्रेडथ-फर्स्ट सर्च (BFS) एक एल्गोरिथ्म है जिसका उपयोग डेटा या सर्चिंग ट्री या ट्रैवर्सिंग संरचनाओं को ग्राफ़ करने के लिए किया जाता है। BFS का पूरा नाम ब्रेडथ-फर्स्ट सर्च है।

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

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

ग्राफ ट्रैवर्सल क्या है?

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

बीएफएस एल्गोरिथम की वास्तुकला

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

हमें बीएफएस एल्गोरिदम की आवश्यकता क्यों है?

अपने डेटासेट की खोज के लिए BFS एल्गोरिदम का उपयोग करने के कई कारण हैं। कुछ सबसे महत्वपूर्ण पहलू जो इस एल्गोरिदम को आपकी पहली पसंद बनाते हैं, वे हैं:

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

बीएफएस एल्गोरिथ्म कैसे काम करता है?

ग्राफ़ ट्रैवर्सल के लिए एल्गोरिथ्म को पेड़ जैसी संरचना में हर एक अन-विजिटेड नोड पर जाना, जाँचना और/या अपडेट करना आवश्यक है। ग्राफ़ ट्रैवर्सल को उस क्रम के अनुसार वर्गीकृत किया जाता है जिसमें वे ग्राफ़ पर नोड्स पर जाते हैं।

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

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

चरण 1)

ग्राफ में प्रत्येक शीर्ष या नोड ज्ञात है। उदाहरण के लिए, आप नोड को V के रूप में चिह्नित कर सकते हैं।

चरण 2)

यदि शीर्ष V तक पहुँच नहीं है तो शीर्ष V को BFS कतार में जोड़ें

चरण 3)

बीएफएस खोज शुरू करें, और पूरा होने के बाद, शीर्ष V को विज़िट किए गए के रूप में चिह्नित करें।

चरण 4)

बीएफएस कतार अभी भी खाली नहीं है, इसलिए कतार से ग्राफ के शीर्ष V को हटा दें।

चरण 5)

ग्राफ पर शेष सभी शीर्षों को पुनः प्राप्त करें जो शीर्ष V के समीप हैं

चरण 6)

प्रत्येक समीपवर्ती शीर्ष के लिए मान लीजिए V1, यदि अभी तक इसका दौरा नहीं हुआ है तो V1 को BFS कतार में जोड़ें

चरण 7)

BFS, V1 पर जाएगा और उसे विजिट किया हुआ चिह्नित करेगा तथा कतार से हटा देगा।

उदाहरण बीएफएस एल्गोरिथ्म

चरण 1)

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

चरण 2)

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

चरण 3)

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

चरण 4)

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

चरण 5)

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

बीएफएस एल्गोरिथम के नियम

यहां, बीएफएस एल्गोरिदम का उपयोग करने के लिए महत्वपूर्ण नियम दिए गए हैं:

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

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

आइए कुछ वास्तविक जीवन अनुप्रयोगों पर नजर डालें जहां बीएफएस एल्गोरिदम कार्यान्वयन अत्यधिक प्रभावी हो सकता है।

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

सारांश

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