ब्रेड्थ-फ़र्स्ट सर्च (BFS)
तालाब में पत्थर डालें, तो लहरें घेरों में बराबर फैलती हैं। ब्रेड्थ-फ़र्स्ट सर्च ग्राफ़ को इसी तरह खोजता है: पहले शुरुआत से एक कदम दूर का सब कुछ, फिर दो कदम दूर का सब कुछ, और इसी तरह आगे। यही सीधा-सा क्रम इसे सबसे छोटे रास्ते खोजने देता है।
मूल विचार
ग्राफ़ एज से जुड़े नोडों का समूह है: जगहें और सड़कें, लोग और दोस्तियाँ, भूलभुलैया के खाने और उनके बीच के रास्ते। ब्रेड्थ-फ़र्स्ट सर्च इस सवाल का जवाब देता है: यहाँ से शुरू करके मैं कहाँ तक पहुँच सकता हूँ, और कम से कम कितने कदमों में? यह उन नोडों की क्यू रखता है जिन पर अभी जाना है। आगे से नोड लेना और नए नोड पीछे जोड़ना यह पक्का करता है कि नोड उसी क्रम में संभाले जाएँ जिसमें वे मिले थे।
चरण-दर-चरण
शुरुआत को दूरी 0 पर क्यू में रखें। आगे वाला नोड लें। हर उस पड़ोसी के लिए जो अभी तक नहीं देखा गया, उसकी दूरी मौजूदा नोड से एक ज़्यादा लिखें, मौजूदा नोड को उस तक पहुँचने का रास्ता मानकर याद रखें, और उसे क्यू के पीछे जोड़ें। पहले देखे गए पड़ोसियों को छोड़ दें। क्यू खाली होने तक, या लक्ष्य तक पहुँचने तक दोहराएँ।
एक उदाहरण
एक ग्राफ़ लें जिसमें A–B, A–C, B–D, C–D, C–E और D–F एज हैं, और A से शुरू करें। क्यू से A लेने पर दूरी 1 पर B और C मिलते हैं। B लेने पर दूरी 2 पर D मिलता है। C लेने पर पता चलता है कि D पहले ही देखा जा चुका है, और दूरी 2 पर E मिलता है। D लेने पर दूरी 3 पर F मिलता है। E और F से कुछ नया नहीं मिलता, और क्यू खाली हो जाती है। F से याद रखे गए नोडों के सहारे वापस जाने पर F ← D ← B ← A मिलता है, इसलिए A से F तक का सबसे छोटा रास्ता A → B → D → F है, तीन एज लंबा।
दूरियाँ सही क्यों हैं
दूरी 1 वाला हर नोड दूरी 2 वाले किसी भी नोड से पहले क्यू में आता है, दूरी 2 वाला हर नोड दूरी 3 वाले किसी भी नोड से पहले, और इसी तरह आगे, क्योंकि किसी नोड के पड़ोसी तभी क्यू में आते हैं जब वह नोड खुद क्यू से निकलता है। इसलिए किसी नोड तक पहुँचने वाला पहला रास्ता सबसे कम एज वाला होता है, और BFS को कभी दूरी सुधारनी नहीं पड़ती। हर नोड एक बार लिया जाता है और हर एज दोनों सिरों से देखा जाता है, इसलिए काम नोडों की संख्या और एज की संख्या के जोड़ के साथ बढ़ता है।
इतिहास और उपयोग
Konrad Zuse ने 1945 में अपनी Plankalkül भाषा पर किए काम में ब्रेड्थ-फ़र्स्ट सर्च का वर्णन किया, जो 1972 तक प्रकाशित नहीं हुआ। Edward F. Moore ने 1959 में भूलभुलैया से बाहर निकलने का सबसे छोटा रास्ता खोजने के लिए इसे फिर से खोजा, और C. Y. Lee ने 1961 में सर्किट बोर्ड पर तारों का रास्ता तय करने के लिए इसका इस्तेमाल किया। आज यह पहेलियों में सबसे कम चालें, सोशल नेटवर्क में दूरी के स्तर, वेब क्रॉलर के सबसे पहले पहुँचने वाले पेज, और गेम में सबसे पास का खाली खाना खोजता है। जब एज की लंबाइयाँ हों, तो डायक्स्ट्रा एल्गोरिदम इसका सामान्य रूप है।
खुद आज़माएँ
ऐप खोलें और “आगे” दबाएँ। जिस नोड पर अभी जाया जा रहा है वह हाइलाइट होता है, क्यू में इंतज़ार कर रहे नोड नीले होते हैं, और विज़िट किए गए नोड हरे, हर एक पर उसकी दूरी के साथ। क्यू ग्राफ़ के नीचे दिखती है, आगे वाला पहले। क्लिक को “लक्ष्य” पर बदलें और कोई नोड चुनें ताकि सर्च वहीं रुके और सबसे छोटा रास्ता दिखे, या ज़्यादा नोड और एज वाला नया ग्राफ़ बनाएँ।
अक्सर पूछे जाने वाले प्रश्न
BFS की टाइम कॉम्प्लेक्सिटी क्या है?
V नोड (वर्टेक्स) और E एज के लिए O(V + E): हर नोड क्यू में एक बार आता और एक बार निकलता है, और हर एज दोनों सिरों से जाँचा जाता है। क्यू और दूरियों के लिए इसे O(V) अतिरिक्त मेमोरी चाहिए।
BFS क्यू का इस्तेमाल क्यों करता है?
क्योंकि जो पहले आए, वह पहले जाए, यह नियम नोडों को उनके मिलने के क्रम में रखता है, जो उनकी दूरी का क्रम है। इसकी जगह स्टैक हो, तो सर्च पहले गहराई में जाएगा: वही डेप्थ-फ़र्स्ट सर्च है।
क्या BFS वेटेड ग्राफ़ में सबसे छोटे रास्ते खोज सकता है?
आम तौर पर नहीं: यह एज गिनता है, उनकी लंबाई नहीं। बिना नेगेटिव एज वाले वेटेड ग्राफ़ के लिए डायक्स्ट्रा एल्गोरिदम इस्तेमाल करें। अगर हर वेट 0 या 1 है, तो 0-1 BFS नाम का एक रूप काम करता है।
BFS कहाँ इस्तेमाल होता है?
पहेलियाँ और भूलभुलैया सबसे कम चालों में हल करने, सोशल नेटवर्क में दोस्तों के दोस्त खोजने, वेब को लेवल-दर-लेवल क्रॉल करने, नेटवर्क में ब्रॉडकास्ट करने, और मैक्सिमम फ़्लो खोजने जैसे दूसरे एल्गोरिदम के हिस्से के रूप में।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
ब्रेड्थ-फ़र्स्ट सर्च आज़माएँ