चौड़ाई पहले खोज

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

परिभाषा

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

लाभ

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

कमियां

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

उपयोग के मामले

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