विस्तार के साथ चौड़ाई पहली खोज (BFS) एल्गोरिथम

BFS एल्गोरिथम (चौड़ाई-प्रथम खोज) क्या है?

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

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

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

इस एल्गोरिथ्म ट्यूटोरियल में, आप सीखेंगे:

• BFS एल्गोरिथम (चौड़ाई-प्रथम खोज) क्या है?
• ग्राफ़ ट्रैवर्सल्स क्या है?
• बीएफएस एल्गोरिथ्म की वास्तुकला
• हमें BFS एल्गोरिथम की आवश्यकता क्यों है?
• BFS एल्गोरिथम कैसे काम करता है?
• उदाहरण बीएफएस एल्गोरिथम
• बीएफएस एल्गोरिदम के नियम
• बीएफएस एल्गोरिदम के अनुप्रयोग

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

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

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

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

हमें BFS एल्गोरिथम की आवश्यकता क्यों है?

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

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

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

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

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

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

चरण 1)

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

चरण 2)

यदि केस V को एक्सेस नहीं किया गया है तो वर्सेट वी को बीएफएस क्यू में जोड़ें

चरण 3)

बीएफएस खोज शुरू करें, और पूरा होने के बाद, मार्क वीटेक्स वी का दौरा किया।

चरण 4)

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

चरण 5)

वर्टेक्स V से सटे ग्राफ़ पर शेष सभी लंबों को पुनः प्राप्त करें

चरण 6)

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

चरण 7)

BFS V1 पर जाएगा और इसे विज़िट के रूप में चिह्नित करेगा और इसे कतार से हटा देगा।

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

चरण 1)

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

चरण 2)

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

चरण 3)

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

चरण 4)

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

चरण 5)

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

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

यहाँ, BFS एल्गोरिथ्म का उपयोग करने के लिए महत्वपूर्ण नियम हैं:

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

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

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

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

सारांश

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