चौड़ाई पहले खोज (BFS)
BFS (चौड़ाई-पहली खोज, चौड़ाई-पहली खोज) - एक ग्राफ़ ट्रैवर्सल विधि, जिसका उपयोग अक्सर सरल और उन्नत एल्गोरिदम दोनों में किया जाता है। ब्रेड्थ-फर्स्ट सर्च ग्राफ़ के अलग-अलग स्तरों के माध्यम से काम करता है, स्रोत नोड से शुरू होता है और धीरे-धीरे इससे दूर हो जाता है। यह एनीमेशन में स्पष्ट रूप से दिखाया गया है।
सबसे सरल BFS लिखने के लिए, आपको एक डेटा संरचना के साथ काम करने में सक्षम होने की आवश्यकता है जो आपको शुरुआत से लेने और इसे अंत तक रखने की अनुमति देता है, और स्टोर करने में भी सक्षम है आसन्न सूची के रूप में ग्राफ (यानी कतार के साथ)।
एल्गोरिदम का औपचारिक विवरण
1) शुरुआती खाली कतार में उस शीर्ष की संख्या डालें जहां से खोज शुरू होती है।
2) कतार की शुरुआत से शीर्ष U निकालें और इसे एक अलग सरणी में उपयोग के रूप में चिह्नित करें।
3) कतार के अंत में, वे सभी कोने जोड़ें जिन तक हम शीर्ष U, के किनारे का उपयोग करके पहुंच सकते हैं और जिन्हें अभी तक लेबल नहीं किया गया है।
4) यदि कतार खाली है, तो जुड़े हुए ग्राफ़ के सभी नोड्स स्कैन किए गए हैं, अन्यथा चरण 2 पर वापस लौटें।
जटिलता
चूंकि एल्गोरिथम सबसे खराब स्थिति में ग्राफ़ के सभी नोड्स पर जाता है, जब ग्राफ़ को आसन्न सूचियों के रूप में संग्रहीत किया जाता है, एल्गोरिदम की समय जटिलता O(|V| + |E|) है , जहां V ग्राफ़ शीर्षों का सेट है, और E किनारों का सेट है। किनारों की संख्या + शीर्षों की संख्या।
|
बीएफएस (चौड़ाई-पहली खोज) एक ग्राफ ट्रैवर्सल विधि है, जो अक्सर सरल और उन्नत एल्गोरिदम दोनों में उपयोग की जाती है। ब्रेड्थ-फर्स्ट सर्च ग्राफ़ के अलग-अलग स्तरों के माध्यम से काम करता है, स्रोत नोड से शुरू होता है और धीरे-धीरे इससे दूर हो जाता है। यह एनीमेशन में स्पष्ट रूप से दिखाया गया है।
 > एक साधारण बीएफएस लिखने के लिए, आपको कतार के साथ काम करने में सक्षम होना चाहिए, एक डेटा संरचना जो आपको शुरू से लेने और इसे अंत तक रखने की अनुमति देती है, और फॉर्म में एक ग्राफ को स्टोर करने में भी सक्षम है। निकटता सूची की।
एल्गोरिदम का औपचारिक विवरण
1) शुरुआती खाली कतार में उस शीर्ष की संख्या डालें जहां से खोज शुरू होती है।
2) कतार की शुरुआत से वर्टेक्स यू निकालें और इसे एक अलग सरणी में उपयोग के रूप में चिह्नित करें।
3) कतार के अंत में, उन सभी शीर्षों को जोड़ें, जिन तक हम शीर्ष U से किनारे का उपयोग करके पहुंच सकते हैं और जो अभी तक चिह्नित नहीं हैं।
4) यदि कतार खाली है, तो जुड़े हुए ग्राफ़ के सभी नोड्स स्कैन किए गए हैं, अन्यथा चरण 2 पर वापस लौटें।
काम में कठिनाई
चूंकि, सबसे खराब स्थिति में, एल्गोरिथ्म ग्राफ के सभी नोड्स पर जाता है, जब ग्राफ को आसन्न सूचियों के रूप में संग्रहीत किया जाता है, तो एल्गोरिथ्म की समय जटिलता O(|V| + |E|) होती है, जहां V सेट होता है ग्राफ़ के शीर्षों की संख्या, और E किनारों का समूह है। ;
दूसरे शब्दों में, एल्गोरिदम किनारों की संख्या + शीर्षों की संख्या के लिए सबसे खराब स्थिति में काम करता है।
|
सबसे छोटे रास्तों को पुनर्स्थापित करने के लिए, "पूर्वजों" \(p[]\) की एक सरणी बनाएं , जिसमें, प्रत्येक शीर्ष के लिए, उस शीर्ष की संख्या को संग्रहित करते हैं, जिससे हम इस शीर्ष तक पहुँचते हैं।
|