- मौजूदा
- क्यू में
- विज़िट किए
- रास्ता
ब्रेड्थ-फ़र्स्ट सर्च (BFS)
ब्रेड्थ-फ़र्स्ट सर्च ग्राफ़ को घेरों में खोजता है: पहले शुरुआत के बगल वाले सभी नोड, फिर दो एज दूर वाले सभी नोड, और इसी तरह आगे। यह काम एक क्यू से होता है, जिसमें जो पहले आए, वह पहले जाए। किसी नोड पर क्लिक करके वहाँ से शुरू करें, चाहें तो लक्ष्य चुनें, और सर्च को एक-एक चरण चलाकर देखें कि क्यू कैसे बढ़ती-घटती है, हर नोड को उसकी दूरी कैसे मिलती है, और सबसे छोटा रास्ता कैसे दिखता है। सर्च देखने के लिए “चलाएँ” दबाएँ, या एक-एक चरण चलने के लिए “आगे” और “पीछे” दबाएँ। कहीं भी जाने के लिए चरण स्लाइडर खींचें। किसी नोड को शुरुआत बनाने के लिए उस पर क्लिक करें; क्लिक को “लक्ष्य” पर बदलें और किसी दूसरे नोड पर क्लिक करें, ताकि उस तक का सबसे छोटा रास्ता खोजा जाए। हर नोड पर लिखी संख्या शुरुआत से उसकी दूरी है, और ग्राफ़ के नीचे की पंक्ति क्यू है। “नया ग्राफ़” दूसरा ग्राफ़ बनाता है; उसमें कितने नोड और एज हों, यह चुनें। बोर्ड चुना होने पर, ऐरो कुंजियाँ एक चरण चलाती हैं, स्पेस बार चलाता और रोकता है, और Home और End शुरुआत और अंत पर ले जाते हैं।
यह कैसे काम करता है
- किसी नोड को शुरुआत बनाने के लिए उस पर क्लिक करें। रास्ता खोजने के लिए क्लिक को “लक्ष्य” पर बदलें और किसी दूसरे नोड पर क्लिक करें।
- “चलाएँ” दबाएँ, या एक-एक चरण चलने के लिए “आगे” और “पीछे” का इस्तेमाल करें। सर्च में कहीं भी जाने के लिए चरण स्लाइडर खींचें।
- ग्राफ़ के नीचे की क्यू और हर नोड पर लिखी दूरी देखें। “नया ग्राफ़” आज़माने के लिए दूसरा ग्राफ़ बनाता है।
ब्रेड्थ-फ़र्स्ट सर्च कैसे काम करता है
शुरुआती नोड को दूरी 0 के साथ क्यू में रखें। फिर दोहराएँ: क्यू के आगे वाला नोड लें और उसके हर पड़ोसी को देखें। जो पड़ोसी अभी तक नहीं देखा गया, उसकी दूरी लिए गए नोड से एक ज़्यादा होती है, वह उस नोड को अपने तक पहुँचने का रास्ता मानकर याद रखता है, और क्यू के पीछे जुड़ जाता है। पहले देखे गए पड़ोसी छोड़ दिए जाते हैं। क्यू खाली होने पर, जहाँ तक पहुँचा जा सकता है उन सभी नोडों की दूरी तय हो जाती है।
यह सबसे छोटे रास्ते क्यों खोजता है
क्यू नोडों को उसी क्रम में देती है जिसमें वे मिले थे, और नोड घेरा-दर-घेरा मिलते हैं: दूरी 1 वाले सभी नोड दूरी 2 वाले किसी भी नोड से पहले क्यू में आते हैं, और इसी तरह आगे। इसलिए जब किसी नोड तक पहली बार पहुँचा जाता है, तो सबसे कम एज वाले रास्ते से पहुँचा जाता है। याद रखे गए नोडों के सहारे लक्ष्य से शुरुआत तक वापस जाने पर वही रास्ता मिलता है। यह सिर्फ़ एज गिनता है; जब एज की लंबाइयाँ अलग हों, तो डायक्स्ट्रा एल्गोरिदम चाहिए।
अक्सर पूछे जाने वाले प्रश्न
ब्रेड्थ-फ़र्स्ट सर्च क्या है?
शुरुआती नोड से ग्राफ़ खोजने का एक तरीका, जिसमें पहले उसके सभी पड़ोसियों पर जाते हैं, फिर उनके पड़ोसियों पर, और इसी तरह घेरा-दर-घेरा। यह नोडों को उनके मिलने के क्रम में रखने के लिए क्यू का इस्तेमाल करता है।
क्या ब्रेड्थ-फ़र्स्ट सर्च सबसे छोटा रास्ता खोजता है?
हाँ, जब हर एज बराबर गिना जाए: BFS जब किसी नोड तक पहली बार पहुँचता है, तो सबसे कम एज इस्तेमाल करता है। अलग-अलग लंबाई वाले एज के लिए, इसकी जगह डायक्स्ट्रा एल्गोरिदम इस्तेमाल करें।
BFS और DFS में क्या अंतर है?
ब्रेड्थ-फ़र्स्ट सर्च क्यू इस्तेमाल करता है और घेरा-दर-घेरा बराबर फैलता है। डेप्थ-फ़र्स्ट सर्च स्टैक (या रिकर्शन) इस्तेमाल करता है और पीछे लौटने से पहले एक रास्ते पर जितना गहरा जा सके जाता है। BFS एज की गिनती में सबसे छोटे रास्ते खोजता है; DFS नहीं खोजता, लेकिन वह साइकिल खोजने और टोपोलॉजिकल सॉर्टिंग के लिए काम का है।
ब्रेड्थ-फ़र्स्ट सर्च कितना तेज़ है?
यह हर नोड को क्यू से एक बार निकालता है और हर एज को दोनों सिरों से देखता है, इसलिए काम नोडों की संख्या और एज की संख्या के जोड़ के साथ बढ़ता है।
क्या मेरा ग्राफ़ कहीं भेजा जाता है?
नहीं। ग्राफ़ आपके ब्राउज़र में ही बनता और खोजा जाता है, और आपकी पिछली सेटिंग इसी ब्राउज़र के लोकल स्टोरेज में रहती हैं।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
एडिटर पर जाएँ