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