BFS Full Form in Hindi, BFS की सम्पूर्ण जानकारी , What is BFS in Hindi, BFS MeBFSng in Hindi, BFS Full Form, BFS Kya Hai, BFS का Full Form क्या हैं, BFS का फुल फॉर्म क्या है, BFS Full Form in Hindi, Full Form of BFS in Hindi, BFS किसे कहते है, BFS का फुल फॉर्म इन हिंदी, BFS का पूरा नाम और हिंदी में क्या अर्थ होता है, BFS की शुरुआत कैसे हुई, दोस्तों क्या आपको पता है, BFS की फुल फॉर्म क्या है, और BFS होता क्या है, अगर आपका Answer नहीं है, तो आपको उदास होने की कोई जरुरत नहीं है, क्योंकि आज हम इस पोस्ट में आपको BFS की पूरी जानकारी हिंदी भाषा में देने जा रहे है. तो फ्रेंड्स BFS फुल फॉर्म इन हिंदी में और इसका पूरा इतिहास जानने के लिए आप इस पोस्ट को लास्ट तक पढ़े.
BFS की फुल फॉर्म “Breadth-first search” होती है. BFS को हिंदी में “पहले चौड़ाई खोजो” कहते है. ये अल्गोरिथम है जो ट्री और ग्राफ में ट्रैवेलिंग और सर्चिंग के लिए प्रयोग होती है. ये ट्री के रुट अर्थात जड़ से शुरू होती है और यदि ग्राफ हो तो उसमे एक को key'नोड मान लेते हैं और वहां से शुरू करते हैं. और पास की नोड पे जाते हैं जिसकी डेप्थ सबसे पहले आती है. BFS, queue अल्गोरिथम की मदद से चलता है अर्थात फर्स्ट इन फर्स्ट आउट.
BFS ग्राफ डेटा स्ट्रक्चर को ट्रेवर्स तथा search करने की एक अल्गोरिथम है. इसका प्रयोग ग्राफ में सबसे छोटा रास्ता को ढूँढने तथा puzzle गेम्स को solve करने के लिए किया जाता है. डेटा स्ट्रक्चर में, BFS को implement करने के लिए queue का प्रयोग किया जाता है. BFS में nodes को चौड़ाई के अनुसार (चौड़ाई से) visit किया जाता है. BFS में पहले किसी भी एक node को visit किया जाता है तथा उसके बाद उसके सटा हुआ के नोड्स को visit किया जाता है. इसके बाद इन सटा हुआ नोड के भी सभी सटा हुआ node को विजिट किया जाता है. और यह प्रक्रिया तब तक चलती है जब तक कि सभी nodes को विजिट नहीं कर लिया जाता है.
ब्रेडथ-फर्स्ट सर्च (बीएफएस) एक नोड के लिए ट्री डेटा संरचना की खोज के लिए एक एल्गोरिथ्म है जो किसी दिए गए गुण को संतुष्ट करता है. यह पेड़ की जड़ से शुरू होता है और अगले गहराई स्तर पर नोड्स पर जाने से पहले वर्तमान गहराई पर सभी नोड्स की खोज करता है. अतिरिक्त मेमोरी, आमतौर पर एक कतार, का सामना करने वाले बच्चे नोड्स का ट्रैक रखने के लिए आवश्यक है लेकिन अभी तक पता नहीं लगाया गया है. उदाहरण के लिए, एक शतरंज एंडगेम में एक शतरंज इंजन सभी संभावित चालों को लागू करके वर्तमान स्थिति से गेम ट्री का निर्माण कर सकता है, और सफेद के लिए जीत की स्थिति खोजने के लिए चौड़ाई-पहली खोज का उपयोग कर सकता है. निहित पेड़ (जैसे खेल के पेड़ या अन्य समस्या सुलझाने वाले पेड़) अनंत आकार के हो सकते हैं; चौड़ाई-पहली खोज एक समाधान नोड खोजने की गारंटी है यदि कोई मौजूद है.
इसके विपरीत, (सादा) गहराई-पहली खोज, जो अन्य नोड्स को पीछे करने और विस्तार करने से पहले जहां तक संभव हो नोड शाखा की खोज करती है, एक अनंत शाखा में खो सकती है और इसे समाधान नोड में कभी नहीं बना सकती है. गहन गहन गहराई-पहली खोज पेड़ के शीर्ष भागों की बार-बार खोज करने की कीमत पर बाद की कमी से बचाती है. दूसरी ओर, दोनों गहराई-प्रथम एल्गोरिदम बिना अतिरिक्त मेमोरी के साथ मिलते हैं. चौड़ाई-पहली खोज को ग्राफ़ के लिए सामान्यीकृत किया जा सकता है, जब प्रारंभ नोड (कभी-कभी 'खोज कुंजी' के रूप में संदर्भित) स्पष्ट रूप से दिया जाता है, और दो बार एक शीर्ष का अनुसरण करने के लिए सावधानी बरती जाती है. ग्राफ के जुड़े घटकों को खोजने में बीएफएस और इसके अनुप्रयोग का आविष्कार 1945 में कोनराड ज़ूस ने अपने (अस्वीकार) पीएच.डी. प्लांकल्कुल प्रोग्रामिंग भाषा पर थीसिस, लेकिन यह 1972 तक प्रकाशित नहीं हुई थी. इसे 1959 में एडवर्ड एफ. मूर द्वारा फिर से खोजा गया, जिन्होंने इसका उपयोग भूलभुलैया से सबसे छोटा रास्ता खोजने के लिए किया, और बाद में सी. वाई. ली द्वारा एक वायर रूटिंग एल्गोरिथ्म (प्रकाशित 1961) में विकसित किया गया.
एक ग्राफ के लिए चौड़ाई-प्रथम ट्रैवर्सल (या खोज) एक पेड़ के चौड़ाई-प्रथम ट्रैवर्सल के समान है (इस पोस्ट की विधि 2 देखें). यहां एकमात्र पकड़ है, पेड़ों के विपरीत, रेखांकन में चक्र हो सकते हैं, इसलिए हम फिर से उसी नोड पर आ सकते हैं. नोड को एक से अधिक बार संसाधित करने से बचने के लिए, हम एक बूलियन विज़िट किए गए सरणी का उपयोग करते हैं. सादगी के लिए, यह माना जाता है कि सभी कोने प्रारंभिक शीर्ष से पहुंच योग्य हैं. उदाहरण के लिए, निम्नलिखित ग्राफ में, हम शीर्ष 2 से ट्रैवर्सल शुरू करते हैं. जब हम शीर्ष 0 पर आते हैं, तो हम इसके सभी आसन्न शीर्षों की तलाश करते हैं. 2 भी 0 का आसन्न शीर्ष है. यदि हम देखे गए शीर्षों को चिह्नित नहीं करते हैं, तो 2 को फिर से संसाधित किया जाएगा और यह एक गैर-समाप्ति प्रक्रिया बन जाएगी. निम्नलिखित ग्राफ का एक चौड़ाई-प्रथम ट्रैवर्सल 2, 0, 3, 1 है.
Breadth First Search (BFS) एल्गोरिथम एक ग्राफ़ को चौड़ाई की गति में ट्रेस करता है और किसी भी पुनरावृत्ति में एक मृत अंत होने पर खोज शुरू करने के लिए अगला शीर्ष प्राप्त करने के लिए याद रखने के लिए एक कतार का उपयोग करता है.
जैसा कि ऊपर दिए गए उदाहरण में, बीएफएस एल्गोरिथ्म ए से बी से ई से एफ तक पहले फिर सी और जी अंत में डी तक जाता है. यह निम्नलिखित नियमों को नियोजित करता है.
नियम 1 − निकटवर्ती बिना देखे गए शीर्ष पर जाएँ. इसे विज़िट किए गए के रूप में चिह्नित करें. इसे प्रदर्शित करें. इसे एक कतार में डालें.
नियम 2 - यदि कोई आसन्न शीर्ष नहीं मिलता है, तो पहले शीर्ष को कतार से हटा दें.
नियम 3 - नियम 1 और नियम 2 को तब तक दोहराएं जब तक कि कतार खाली न हो जाए.
ग्राफ़ ट्रैवर्सल का अर्थ है प्रत्येक शीर्ष और किनारे पर एक अच्छी तरह से परिभाषित क्रम में एक बार जाना. कुछ ग्राफ़ एल्गोरिदम का उपयोग करते समय, आपको यह सुनिश्चित करना चाहिए कि ग्राफ़ के प्रत्येक शीर्ष पर ठीक एक बार विज़िट किया जाए. जिस क्रम में शीर्षों का दौरा किया जाता है वह महत्वपूर्ण है और यह उस एल्गोरिथम या प्रश्न पर निर्भर हो सकता है जिसे आप हल कर रहे हैं. ट्रैवर्सल के दौरान, यह महत्वपूर्ण है कि आप ट्रैक करें कि कौन से शीर्षों का दौरा किया गया है. शीर्षों को ट्रैक करने का सबसे आम तरीका उन्हें चिह्नित करना है.
रेखांकन को पार करने के कई तरीके हैं. बीएफएस सबसे अधिक इस्तेमाल किया जाने वाला दृष्टिकोण है. बीएफएस एक ट्रैवर्सिंग एल्गोरिथम है जहां आपको एक चयनित नोड (स्रोत या शुरुआती नोड) से ट्रैवर्स करना शुरू करना चाहिए और ग्राफ को परतदार तरीके से पार करना चाहिए, इस प्रकार पड़ोसी नोड्स (नोड्स जो सीधे स्रोत नोड से जुड़े होते हैं) की खोज करते हैं. फिर आपको अगले स्तर के पड़ोसी नोड्स की ओर बढ़ना चाहिए. जैसा कि बीएफएस नाम से पता चलता है, आपको ग्राफ़ को चौड़ाई में इस प्रकार पार करना होगा: पहले क्षैतिज रूप से आगे बढ़ें और वर्तमान परत के सभी नोड्स पर जाएँ अगली परत पर जाएँ निम्नलिखित आरेख पर विचार करें.
परत 1 में नोड्स के बीच की दूरी परत 2 में नोड्स के बीच की दूरी की तुलना में तुलनात्मक रूप से कम है. इसलिए, बीएफएस में, आपको परत 2 में नोड्स में जाने से पहले परत 1 में सभी नोड्स को पार करना होगा.
एक ग्राफ़ में चक्र हो सकते हैं, जो ग्राफ़ को पार करते समय आपको फिर से उसी नोड पर ला सकते हैं. फिर से उसी नोड के प्रसंस्करण से बचने के लिए, एक बूलियन सरणी का उपयोग करें जो संसाधित होने के बाद नोड को चिह्नित करता है. ग्राफ़ की परत में नोड्स का दौरा करते समय, उन्हें इस तरह से संग्रहीत करें कि आप समान क्रम में संबंधित चाइल्ड नोड्स को पार कर सकें. पहले के आरेख में, 0 से ट्रैवर्स करना शुरू करें और इसके चाइल्ड नोड्स 1, 2, और 3 पर जाएं. उन्हें उस क्रम में संग्रहीत करें जिस क्रम में वे आए थे. यह आपको पहले 1 (यानी 4 और 5), फिर 2 (यानी 6 और 7) और फिर 3 (यानी 7) आदि के चाइल्ड नोड्स पर जाने की अनुमति देगा. इस प्रक्रिया को आसान बनाने के लिए, नोड को स्टोर करने के लिए एक कतार का उपयोग करें और इसे तब तक 'विज़िट' के रूप में चिह्नित करें जब तक कि इसके सभी पड़ोसी (सीधे जुड़े हुए कोने) चिह्नित न हो जाएं. कतार फर्स्ट इन फर्स्ट आउट (FIFO) कतार विधि का अनुसरण करती है, और इसलिए, नोड के पड़ोसियों को उस क्रम में देखा जाएगा जिसमें उन्हें नोड में डाला गया था यानी पहले डाला गया नोड पहले देखा जाएगा, और इसलिए पर.
चौड़ाई पहली खोज एक ग्राफ ट्रैवर्सल एल्गोरिदम है जो रूट नोड से ग्राफ को पार करना शुरू करता है और सभी पड़ोसी नोड्स की खोज करता है. फिर, यह निकटतम नोड का चयन करता है और सभी बेरोज़गार नोड्स का पता लगाता है. एल्गोरिथ्म प्रत्येक निकटतम नोड के लिए एक ही प्रक्रिया का अनुसरण करता है जब तक कि उसे लक्ष्य नहीं मिल जाता. चौड़ाई पहली खोज का एल्गोरिथम नीचे दिया गया है. एल्गोरिथ्म नोड ए और उसके सभी पड़ोसियों की जांच के साथ शुरू होता है. अगले चरण में, A के निकटतम नोड के पड़ोसियों का पता लगाया जाता है और आगे के चरणों में प्रक्रिया जारी रहती है. एल्गोरिथ्म सभी नोड्स के सभी पड़ोसियों की खोज करता है और यह सुनिश्चित करता है कि प्रत्येक नोड को ठीक एक बार देखा जाता है और कोई भी नोड दो बार नहीं जाता है.
ब्रेडथ फर्स्ट सर्च (बीएफएस) पेड़ या ग्राफ डेटा संरचनाओं में परत-दर-परत खोज या खोज के लिए एक एल्गोरिथ्म है. BFS का आविष्कार पहली बार 1945 में Konrad Zuse द्वारा किया गया था जो 1972 तक प्रकाशित नहीं हुआ था. इसे 1959 में एडवर्ड एफ मूर द्वारा भूलभुलैया से सबसे छोटा रास्ता खोजने के लिए फिर से खोजा गया था. बीएफएस को सी.वाई.ली द्वारा एक वायर रूटिंग एल्गोरिथम (1961 में प्रकाशित) में और विकसित किया गया था. यहां इस्तेमाल की जाने वाली रणनीति डेप्थ फर्स्ट सर्च (डीएफएस) के विपरीत है जो अन्य नोड्स को पीछे करने और एक्सप्लोर करने के लिए मजबूर होने से पहले जहां तक संभव हो (गहराई-वार) नोड्स की खोज करती है. एल्गोरिथम ट्री रूट (या 'सोर्स नोड' नामक ग्राफ के किसी भी मनमाने नोड) से शुरू होता है, और अगले स्तर पर नोड्स पर जाने से पहले वर्तमान स्तर पर सभी पड़ोसी नोड्स (सीधे स्रोत नोड से जुड़ा) की जांच करता है. . वांछित परिणाम प्राप्त होने तक प्रक्रिया को दोहराया जाता है.
चौड़ाई-प्रथम खोज (बीएफएस) एक महत्वपूर्ण ग्राफ़ खोज एल्गोरिथ्म है जिसका उपयोग कई समस्याओं को हल करने के लिए किया जाता है जिसमें ग्राफ़ में सबसे छोटा रास्ता खोजना और पहेली गेम (जैसे रूबिक के क्यूब्स) को हल करना शामिल है. कंप्यूटर विज्ञान की कई समस्याओं को रेखांकन के रूप में सोचा जा सकता है. उदाहरण के लिए, नेटवर्क का विश्लेषण, मानचित्रण मार्ग और शेड्यूलिंग ग्राफ़ समस्याएं हैं. ग्राफ़ खोज एल्गोरिदम जैसे चौड़ाई-प्रथम खोज ग्राफ़ समस्याओं के विश्लेषण और समाधान के लिए उपयोगी हैं.
चौड़ाई-पहली खोज एक स्टार्ट नोड की खोज से शुरू होती है, उसके बाद उसके आस-पास के नोड्स, फिर सभी नोड्स जिन्हें दो किनारों, तीन किनारों, और इसी तरह से प्रारंभ नोड से पथ तक पहुंचा जा सकता है. औपचारिक रूप से, BFS एल्गोरिथम किसी भी शीर्ष k+1k+1 किनारों पर जाने से पहले ग्राफ़ GG के सभी शीर्षों पर जाता है जो स्रोत शीर्ष ss से kk किनारे दूर होते हैं. यह तब तक किया जाता है जब तक ss से कोई और कोने उपलब्ध नहीं हो जाते. नीचे दी गई छवि यह दर्शाती है कि यह ट्रैवर्सल कैसे आगे बढ़ता है:-
ग्राफ़ G = (V,E)G=(V,E) और एक स्रोत शीर्ष vv के लिए, चौड़ाई-पहली खोज VV से सभी पहुंच योग्य शीर्षों को खोजने के लिए GG के किनारों को पार करती है. यह किसी भी पहुंच योग्य शीर्ष के लिए सबसे छोटी दूरी की गणना भी करता है. चौड़ाई-प्रथम खोज ट्री में दो बिंदुओं के बीच का कोई भी पथ रूट vv से किसी अन्य नोड ss के सबसे छोटे पथ से मेल खाता है. BFS में तीन प्रकार के कोने होते हैं: ट्री वर्टिस, वे जो देखे गए हैं; फ्रिंज शिखर, जो पेड़ के शीर्षों से सटे हुए हैं लेकिन अभी तक नहीं गए हैं; और अनदेखे शिखर, जिनका हमने अभी तक सामना नहीं किया है. ऊपर दिए गए एनिमेशन में, सफेद उन शीर्षों को इंगित करता है जो अनदेखे हैं, धूसर फ्रिंज शीर्षों को इंगित करता है, और काला पेड़ के शीर्षों को इंगित करता है. एक ग्राफ के एक जुड़े हुए घटक को व्यवस्थित रूप से खोजने के लिए, फ्रिंज पर एक शीर्ष से शुरू करें, अन्य सभी अनदेखी, और निम्न चरण का पालन करें जब तक कि सभी शिखरों का दौरा नहीं किया जाता है: "एक शीर्ष xx को फ्रिंज से पेड़ पर ले जाएं, और किसी भी अनदेखी को रखें फ्रिंज पर xx से सटे शीर्ष." ग्राफ़ ट्रैवर्सल विधियाँ यह तय करने में भिन्न होती हैं कि किस शीर्ष को फ्रिंज से पेड़ तक ले जाया जाना चाहिए. चौड़ाई-प्रथम खोज के लिए, उस फ्रिंज से शीर्ष को चुनें जो कम से कम हाल ही में सामने आया था; यह फ्रिंज पर शिखर धारण करने के लिए एक कतार का उपयोग करने से मेल खाता है.
कंप्यूटर विज्ञान और वास्तविक दुनिया में अधिकांश अवधारणाओं को ग्राफ डेटा संरचना के संदर्भ में देखा और दर्शाया जा सकता है. इन समस्याओं को आसानी से हल करने के लिए BFS एक ऐसा उपयोगी एल्गोरिथम है. बीएफएस की संरचना सरल, सटीक और मजबूत है. यह बहुत सहज है क्योंकि यह गारंटी है कि एल्गोरिथ्म एक अनंत लूप में नहीं पकड़ा जाएगा.
सबसे छोटा पथ: बिना भार वाले ग्राफ़ में, सबसे छोटा पथ वह पथ होता है जिसमें किनारों की संख्या कम से कम होती है. बीएफएस के साथ, हम हमेशा कम से कम संभव पथ में दिए गए स्रोत से एक
नोड तक पहुंचते हैं. उदाहरण: दिज्क्स्ट्रा का एल्गोरिथम.
जीपीएस नेविगेशन सिस्टम: बीएफएस का उपयोग किसी दिए गए स्रोत स्थान से पड़ोसी स्थानों को खोजने के लिए किया जाता है.
पथ ढूँढना: हम बीएफएस का उपयोग यह पता लगाने के लिए कर सकते हैं कि पथ दो नोड्स के बीच मौजूद है या नहीं.
एक जुड़े हुए घटक के भीतर नोड्स ढूँढना: बीएफएस का उपयोग किसी दिए गए नोड से पहुंचने योग्य सभी नोड्स को खोजने के लिए किया जा सकता है.
सोशल नेटवर्किंग वेबसाइट्स: हम बीएफएस का उपयोग करने वाले व्यक्ति से एक निश्चित दूरी 'के' के भीतर लोगों की संख्या का पता लगा सकते हैं.
P2P नेटवर्क: P2P (पीयर टू पीयर) नेटवर्क जैसे बिटटोरेंट, बीएफएस का उपयोग किसी दिए गए नोड से सभी पड़ोसी नोड्स को खोजने के लिए किया जाता है.
खोज इंजन क्रॉलर: क्रॉलर के पीछे मुख्य विचार स्रोत पृष्ठ से शुरू करना है और उस स्रोत से अन्य पृष्ठों के सभी लिंक का पालन करना और उसी को दोहराते रहना है. यहां डीएफएस का भी उपयोग किया जा सकता है, लेकिन ब्रेडथ फर्स्ट ट्रैवर्सल को गहराई या ट्रैवर्स किए गए स्तरों को सीमित करने में फायदा होता है.
चौड़ाई-पहली खोज (बीएफएस) एक एल्गोरिदम है जिसका उपयोग डेटा को ग्राफ़ करने या पेड़ या ट्रैवर्सिंग संरचनाओं को खोजने के लिए किया जाता है. BFS का फुल फॉर्म Breadth-first search होता है. एल्गोरिथम प्रभावी रूप से एक ग्राफ़ में सभी प्रमुख नोड्स को सटीक रूप से चौड़ाई के हिसाब से देखता है और चिह्नित करता है. यह एल्गोरिथम ग्राफ़ में एकल नोड (प्रारंभिक या स्रोत बिंदु) का चयन करता है और फिर चयनित नोड से सटे सभी नोड्स पर जाता है. याद रखें, BFS इन नोड्स को एक-एक करके एक्सेस करता है. एक बार जब एल्गोरिथम शुरुआती नोड पर जाता है और चिह्नित करता है, तो यह निकटतम अनजान नोड्स की ओर बढ़ता है और उनका विश्लेषण करता है. एक बार दौरा करने के बाद, सभी नोड्स चिह्नित किए जाते हैं. ये पुनरावृत्तियां तब तक जारी रहती हैं जब तक कि ग्राफ़ के सभी नोड्स को सफलतापूर्वक विज़िट और चिह्नित नहीं किया जाता है.
ग्राफ में शीर्ष स्थिति का पता लगाने के लिए एक ग्राफ ट्रैवर्सल आमतौर पर इस्तेमाल की जाने वाली पद्धति है. यह एक उन्नत खोज एल्गोरिथम है जो देखे गए शीर्षों के अनुक्रम को चिह्नित करने के साथ-साथ गति और सटीकता के साथ ग्राफ़ का विश्लेषण कर सकता है. यह प्रक्रिया आपको अनंत लूप में बंद किए बिना ग्राफ़ में प्रत्येक नोड को जल्दी से देखने में सक्षम बनाती है.
डेटा के विभिन्न स्तरों में, आप ट्रैवर्सिंग शुरू करने के लिए किसी भी नोड को शुरुआती या प्रारंभिक नोड के रूप में चिह्नित कर सकते हैं. बीएफएस नोड का दौरा करेगा और इसे विज़िट के रूप में चिह्नित करेगा और इसे कतार में रखेगा. अब बीएफएस निकटतम और गैर-विजिटेड नोड्स का दौरा करेगा और उन्हें चिह्नित करेगा. इन मानों को कतार में भी जोड़ा जाता है. कतार फीफो मॉडल पर काम करती है. इसी तरह, ग्राफ पर शेष निकटतम और गैर-विज़िट नोड्स का विश्लेषण किया जाता है और कतार में जोड़ा जाता है. इन वस्तुओं को कतार से हटा दिया जाता है और परिणाम के रूप में मुद्रित किया जाता है.
आपके डेटासेट की खोज के रूप में उपयोग करने के लिए BFS एल्गोरिथम का उपयोग करने के कई कारण हैं. इस एल्गोरिथम को आपकी पहली पसंद बनाने वाले कुछ सबसे महत्वपूर्ण पहलू हैं:-
बीएफएस ग्राफ में नोड्स का विश्लेषण करने और इनके माध्यम से ट्रैवर्सिंग के सबसे छोटे पथ के निर्माण के लिए उपयोगी है.
बीएफएस पुनरावृत्तियों की सबसे छोटी संख्या में एक ग्राफ के माध्यम से पार कर सकता है.
बीएफएस एल्गोरिथम का आर्किटेक्चर सरल और मजबूत है.
बीएफएस एल्गोरिथ्म का परिणाम अन्य एल्गोरिदम की तुलना में उच्च स्तर की सटीकता रखता है.
बीएफएस पुनरावृत्तियां निर्बाध हैं, और इस एल्गोरिथम के अनंत लूप समस्या में फंसने की कोई संभावना नहीं है.
ग्राफ़ ट्रैवर्सल के लिए एल्गोरिथम की आवश्यकता होती है, जो पेड़ जैसी संरचना में हर एक गैर-विज़िट नोड को देखने, जांचने और/या अपडेट करने के लिए है. ग्राफ़ ट्रैवर्सल को उस क्रम से वर्गीकृत किया जाता है जिसमें वे ग्राफ़ पर नोड्स पर जाते हैं. बीएफएस एल्गोरिथ्म ग्राफ में पहले या शुरुआती नोड से ऑपरेशन शुरू करता है और इसे अच्छी तरह से पार करता है. एक बार जब यह प्रारंभिक नोड को सफलतापूर्वक पार कर लेता है, तो ग्राफ़ में अगले गैर-ट्रैवर्स किए गए शीर्ष का दौरा किया जाता है और चिह्नित किया जाता है. इसलिए, आप कह सकते हैं कि वर्तमान शीर्ष से सटे सभी नोड्स का दौरा किया जाता है और पहले पुनरावृत्ति में ट्रैवर्स किया जाता है. BFS एल्गोरिथम के कार्य को लागू करने के लिए एक साधारण कतार पद्धति का उपयोग किया जाता है, और इसमें निम्नलिखित चरण होते हैं:
यहाँ, BFS एल्गोरिथम का उपयोग करने के लिए महत्वपूर्ण नियम हैं:
बीएफएस द्वारा एक क्यू (फीफो-फर्स्ट इन फर्स्ट आउट) डेटा संरचना का उपयोग किया जाता है.
आप ग्राफ में किसी भी नोड को रूट के रूप में चिह्नित करते हैं और उससे डेटा को ट्रैवर्स करना शुरू करते हैं.
बीएफएस ग्राफ में सभी नोड्स का पता लगाता है और उन्हें पूरा होने पर छोड़ देता है.
बीएफएस एक आसन्न गैर-विजिटेड नोड पर जाता है, इसे हो गया के रूप में चिह्नित करता है, और इसे एक कतार में सम्मिलित करता है.
यदि कोई आसन्न शीर्ष नहीं मिलता है तो पिछले शीर्ष को कतार से हटा देता है.
BFS एल्गोरिथ्म तब तक पुनरावृत्त होता है जब तक कि ग्राफ़ के सभी कोने सफलतापूर्वक ट्रैवर्स नहीं हो जाते और पूर्ण के रूप में चिह्नित नहीं हो जाते.
किसी भी नोड से डेटा के ट्रैवर्सिंग के दौरान BFS के कारण कोई लूप नहीं होता है.
आइए कुछ वास्तविक जीवन के अनुप्रयोगों पर एक नज़र डालें जहां एक बीएफएस एल्गोरिथम कार्यान्वयन अत्यधिक प्रभावी हो सकता है.
गैर-भारित ग्राफ़: BFS एल्गोरिथ्म आसानी से सबसे छोटा पथ और न्यूनतम फैले हुए पेड़ बना सकता है ताकि उच्च सटीकता के साथ कम से कम समय में ग्राफ़ के सभी शीर्षों पर जा सकें.
पी2पी नेटवर्क: बीएफएस को पीयर टू पीयर नेटवर्क में सभी निकटतम या पड़ोसी नोड्स का पता लगाने के लिए लागू किया जा सकता है. इससे आवश्यक डेटा तेजी से मिलेगा.
वेब क्रॉलर: खोज इंजन या वेब क्रॉलर बीएफएस को नियोजित करके आसानी से कई स्तरों के सूचकांक बना सकते हैं. बीएफएस कार्यान्वयन स्रोत से शुरू होता है, जो कि वेब पेज है, और फिर यह उस स्रोत से सभी लिंक पर जाता है.
नेविगेशन सिस्टम: बीएफएस मुख्य या स्रोत स्थान से सभी पड़ोसी स्थानों को खोजने में मदद कर सकता है.
नेटवर्क ब्रॉडकास्टिंग: एक ब्रॉडकास्ट पैकेट को बीएफएस एल्गोरिथम द्वारा निर्देशित किया जाता है ताकि वह उन सभी नोड्स को ढूंढ सके और उन तक पहुंच सके जिनके लिए इसका पता है.
एक ग्राफ ट्रैवर्सल एक अनूठी प्रक्रिया है जिसके लिए एल्गोरिदम की आवश्यकता होती है ताकि पेड़ जैसी संरचना में प्रत्येक गैर-विज़िट नोड को देखने, जांचने और/या अपडेट किया जा सके. बीएफएस एल्गोरिथ्म एक समान सिद्धांत पर काम करता है. एल्गोरिथम ग्राफ में नोड्स का विश्लेषण करने और इनके माध्यम से ट्रैवर्सिंग के सबसे छोटे पथ के निर्माण के लिए उपयोगी है. एल्गोरिथ्म ग्राफ को पुनरावृत्तियों की सबसे छोटी संख्या और कम से कम संभव समय में पार करता है. BFS ग्राफ़ में एकल नोड (आरंभिक या स्रोत बिंदु) का चयन करता है और फिर चयनित नोड से सटे सभी नोड्स पर जाता है. BFS इन नोड्स को एक-एक करके एक्सेस करता है. बीएफएस द्वारा देखे गए और चिह्नित डेटा को एक कतार में रखा गया है. एक कतार पहले पहले बाहर के आधार पर काम करती है. इसलिए, पहले ग्राफ़ में रखे गए तत्व को पहले हटा दिया जाता है और परिणामस्वरूप मुद्रित किया जाता है. BFS एल्गोरिथ्म कभी भी अनंत लूप में नहीं फंस सकता है. उच्च परिशुद्धता और मजबूत कार्यान्वयन के कारण, बीएफएस का उपयोग पी2पी नेटवर्क, वेब क्रॉलर और नेटवर्क ब्रॉडकास्टिंग जैसे कई वास्तविक जीवन समाधानों में किया जाता है.
यह पेपर डिजिटल स्टोरेज मीडिया कमांड एंड कंट्रोल (DSM-CC) डेटा हिंडोला प्रोटोकॉल पर आधारित ब्रॉडकास्ट फाइल सिस्टम के लिए एक समाधान प्रस्तुत करता है. ऑब्जेक्ट हिंडोला प्रोटोकॉल की जटिलता को देखते हुए, हम डेटा हिंडोला प्रोटोकॉल को नवीन रूप से संशोधित करते हैं ताकि पदानुक्रमित निर्देशिका संरचना को प्रसारित किया जा सके. संबंधित सॉफ्टवेयर सेट टॉप बॉक्स में लागू किया गया है. वर्चुअल फाइल सिस्टम स्विच (VFS) मैकेनिज्म की मदद से ब्रॉडकास्ट फाइल सिस्टम को यूनिफाइड इंटरफेस के जरिए एक्सेस किया जा सकता है. ब्रॉडकास्ट फाइल सिस्टम और पारंपरिक फाइल सिस्टम के बीच अंतर को ध्यान में रखते हुए, यह पेपर बेहतर प्रदर्शन दिखाने के लिए नेटवर्क से डेटा प्राप्त करने और कैशिंग करते समय अनुकूलित रणनीतियों का भी प्रस्ताव करता है.
डिजिटल वीडियो प्रसारण (डीवीबी) में, एक डेटा और ऑब्जेक्ट कैरोसेल का उपयोग निरंतर चक्र में डेटा को बार-बार वितरित करने के लिए किया जाता है. हिंडोला एक मानक प्रारूप में बार-बार डेटा सेट को प्रसारित करके एक प्रसारक से कई रिसीवरों तक डेटा को धकेलने की अनुमति देता है. एक सेट-टॉप बॉक्स रिसीवर किसी भी समय डेटा स्ट्रीम को ट्यून कर सकता है और डेटा को वर्चुअल फ़ाइल सिस्टम में पुनर्गठित करने में सक्षम होता है. इसलिए हिंडोला को एक ट्रांसपोर्ट फाइल सिस्टम या फाइल ब्रॉडकास्टिंग सिस्टम के रूप में माना जा सकता है जो डेटा फाइलों को ब्रॉडकास्टर से कई रिसीवर या क्लाइंट को एक साथ प्रसारित करने की अनुमति देता है. एक यूनिडायरेक्शनल प्रसारण वातावरण में, रिसीवर किसी भी डेटा को फिर से भेजने का अनुरोध करने में असमर्थ है जो छूट गया था या गलत तरीके से प्राप्त हुआ था. डेटा का बार-बार पुन: प्रेषण रिसीवर को अप्रत्याशित समय पर एक चैनल के लिए यादृच्छिक ट्यूनिंग से निपटने की अनुमति देता है, उदाहरण के लिए जब उपयोगकर्ता एक चैनल बदलता है. हिंडोला चक्र अवधि आम तौर पर एक रिसीवर के लिए एक आवेदन या विशिष्ट डेटा प्राप्त करने के लिए आवश्यक अधिकतम समय निर्धारित करती है. कुछ डेटा को दूसरों की तुलना में अधिक बार प्रसारित करके आमतौर पर उपयोग की जाने वाली फ़ाइलों के लिए एक्सेस समय को कम करना संभव है. कुछ दस्तावेज़ों में व्यक्तिगत ऑब्जेक्ट हिंडोला को सेवा डोमेन भी कहा जाता है. सटीक होने के लिए, एक सेवा डोमेन संबंधित DSM-CC ऑब्जेक्ट्स का एक समूह है. ब्रॉडकास्ट सिस्टम में, ऑब्जेक्ट कैरोसेल और सर्विस डोमेन के बीच शब्दावली को छोड़कर कोई अंतर नहीं है: ऑब्जेक्ट कैरोसेल एक सर्विस डोमेन है, और इसके विपरीत.
डीवीबी में डेटा और ऑब्जेक्ट हिंडोला का सबसे अधिक उपयोग किया जाता है, जिसमें हिंडोला का उपयोग करके डिजिटल टेलीविजन सामग्री को प्रसारित करने के मानक हैं. हिंडोला के लिए मानक प्रारूप को ISO/IEC 13818-6 में डिजिटल स्टोरेज मीडिया कमांड एंड कंट्रोल (DSM-CC) टूलकिट में परिभाषित किया गया है और यह डिजिटल वीडियो प्रसारण के लिए डिजिटल ऑडियो वीडियो काउंसिल (DAVIC) DVB मानक का हिस्सा है. विनिर्देश विभिन्न प्रकार के संचार मॉडल के लिए समर्थन प्रदान करता है, जिसमें द्वि-दिशात्मक वातावरण में ऑडियो और वीडियो स्ट्रीम के इंटरैक्टिव परिवहन नियंत्रण के प्रावधान शामिल हैं, जैसे कि केबल टेलीविजन वीडियो ऑन डिमांड सिस्टम. DSM-CC मानक दो प्रकार के हिंडोला, एक डेटा हिंडोला और एक वस्तु हिंडोला निर्दिष्ट करता है. ऑब्जेक्ट हिंडोला अधिक सीमित डेटा हिंडोला का विस्तार करता है और एक फ़ाइल सिस्टम निर्देशिका संरचना का प्रतिनिधित्व करने के लिए एक मानक प्रारूप निर्दिष्ट करता है जिसमें रूट निर्देशिका या सेवा गेटवे और एक या अधिक फ़ाइलें और निर्देशिका शामिल हैं. फ़ाइलें और निर्देशिका कई परतों में DSM-CC ऑब्जेक्ट हिंडोला में इनकैप्सुलेटेड हैं. ऑब्जेक्ट्स को मॉड्यूल में एनकैप्सुलेट किया जाता है, जो डाउनलोड डेटा ब्लॉक के भीतर, एमपीईजी निजी अनुभागों में एन्कोड किए गए डीएसएम-सीसी अनुभागों के भीतर ले जाया जाता है, जो पैकेट से इकट्ठे होते हैं.