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