डेप्थ-फ़र्स्ट सर्च (DFS)
किसी भूलभुलैया में जाएँ, तब तक चलते रहें जब तक बंद रास्ता न आ जाए, फिर पिछले दोराहे पर लौटें और अगला रास्ता आज़माएँ। डेप्थ-फ़र्स्ट सर्च ग्राफ़ को इसी तरह खोजता है। यह सबसे सरल ग्राफ़ एल्गोरिदम में से एक है, और इसका स्टैक आपकी उम्मीद से ज़्यादा बताता है।
मूल विचार
ग्राफ़ एजों से जुड़े नोडों का एक समूह है: कमरे और दरवाज़े, वेब पेज और लिंक, काम और वे काम जिन पर वे निर्भर हैं। डेप्थ-फ़र्स्ट सर्च शुरुआत से पहुँचने लायक हर नोड को विज़िट करता है, लेकिन एक खास क्रम में: यह हमेशा उस नोड से आगे बढ़ता है जिस तक यह सबसे हाल में पहुँचा। यह उन नोडों का स्टैक रखता है जिनके भीतर यह है। नया नोड सबसे ऊपर जाता है, और कोई नोड तभी हटता है जब उसके आसपास सब कुछ खोज लिया गया हो।
चरण-दर-चरण
शुरुआत को स्टैक पर रखें और उसे विज़िट नंबर 1 दें। सबसे ऊपर वाले नोड का अगला पड़ोसी देखें। अगर वह पहले नहीं देखा गया, तो उसे अगला विज़िट नंबर दें, याद रखें कि वह किस नोड से पहुँचा गया, और उसे स्टैक में सबसे ऊपर रखें। अगर पहले देखा जा चुका है, तो उसे छोड़ दें। जब सबसे ऊपर वाले नोड के पास जाँचने को कोई पड़ोसी नहीं बचता, तो वह पूरा हो जाता है: उसे हटाएँ और नीचे वाले नोड के साथ आगे बढ़ें। स्टैक खाली होने पर, या लक्ष्य तक पहुँचने पर रुकें।
एक उदाहरण
A–B, A–C, B–D, C–D, C–E और D–F एजों वाला एक ग्राफ़ लें, A से शुरू करें, और पड़ोसियों को वर्णक्रम में जाँचें। सर्च A से B पर जाता है, B से D पर, D से C पर, और C से E पर, इसलिए स्टैक A, B, D, C, E है। रास्ते में C को A दिखता है, जो अभी भी स्टैक पर है: एज C–A साइकिल A, B, D, C पूरी करता है। E के पास कुछ नया नहीं है, इसलिए वह पूरा होता है, फिर C, और सर्च D पर लौटता है, जिसके पास अभी F बाकी है। विज़िट क्रम A, B, D, C, E, F है। E को लक्ष्य बनाने पर DFS रास्ते A → B → D → C → E पर रुकता है, यानी चार एज, जबकि A → C → E में सिर्फ़ दो लगते हैं।
यह किस काम आता है
स्टैक हमेशा शुरुआत से मौजूदा नोड तक का रास्ता होता है, इसलिए DFS भूलभुलैया और पहेलियों के लिए स्वाभाविक है: बैकट्रैकिंग के पीछे यही विचार है। बिना दिशा वाले ग्राफ़ में, अभी भी स्टैक पर मौजूद किसी नोड तक का एज एक साइकिल पूरी करता है। दिशा वाले ग्राफ़ में, नोडों को उनके पूरे होने के उलटे क्रम में लिखने से टोपोलॉजिकल क्रम मिलता है, ताकि हर काम उन कामों के बाद आए जिन पर वह निर्भर है। डेप्थ-फ़र्स्ट सर्च कनेक्टेड कंपोनेंट, ब्रिज और आर्टिकुलेशन पॉइंट भी खोजता है, और इसका रैंडम रूप भूलभुलैया बनाने का एक क्लासिक तरीका है।
इतिहास
19वीं सदी में फ़्रांसीसी गणितज्ञ शार्ल पियरे ट्रेमो (Charles Pierre Trémaux) ने रास्तों पर निशान लगाकर किसी भी भूलभुलैया से निकलने का तरीका बताया, जो चॉक से किया गया डेप्थ-फ़र्स्ट सर्च ही है। 1972 और 1973 में रॉबर्ट टार्जन (Robert Tarjan) और जॉन हॉपक्रॉफ़्ट (John Hopcroft) ने दिखाया कि DFS बहुत-सी ग्राफ़ समस्याओं को लीनियर समय में हल करता है, स्ट्रॉन्गली कनेक्टेड कंपोनेंट से लेकर यह जाँचने तक कि कोई ग्राफ़ बिना क्रॉसिंग के बनाया जा सकता है या नहीं। उन्हें 1986 का ट्यूरिंग पुरस्कार आंशिक रूप से इसी काम के लिए मिला।
इसे आज़माएँ
ऐप खोलें और “आगे” दबाएँ। जिस नोड के पड़ोसी जाँचे जा रहे हैं, वह हाइलाइट होता है, स्टैक पर मौजूद नोड नीले हैं, और पूरे हुए नोड हरे, हर एक पर उसका विज़िट नंबर लिखा है। स्टैक ग्राफ़ के नीचे दिखता है, शुरुआत से सबसे ऊपर वाले नोड तक। साइकिल पूरी करने वाले एजों के लिए स्टेटस लाइन पर नज़र रखें, और लक्ष्य चुनकर देखें कि ब्रेड्थ-फ़र्स्ट सर्च की तुलना में मिला रास्ता कितना लंबा हो सकता है।
अक्सर पूछे जाने वाले प्रश्न
DFS की टाइम कॉम्प्लेक्सिटी क्या है?
V नोड (वर्टेक्स) और E एज के लिए O(V + E): हर नोड एक बार स्टैक पर जाता है और एक बार हटता है, और हर एज को दोनों सिरों से जाँचा जाता है। स्टैक और निशानों के लिए इसे O(V) अतिरिक्त मेमोरी चाहिए।
DFS स्टैक क्यों इस्तेमाल करता है?
क्योंकि “जो आखिर में आए, वह पहले जाए” से सर्च सबसे नए नोड से आगे बढ़ता है और उससे पिछले नोड पर लौटता है। रिकर्शन प्रोग्राम के कॉल स्टैक से यही काम करता है। इसकी जगह क्यू हो, तो सर्च घेरा-दर-घेरा फैलेगा: वही ब्रेड्थ-फ़र्स्ट सर्च है।
क्या बड़े ग्राफ़ के लिए रिकर्सिव DFS समस्या है?
हो सकता है: लंबे रास्ते का मतलब गहरा रिकर्शन है, और कई भाषाएँ सीमित करती हैं कि कॉल कितनी गहराई तक जा सकते हैं। लूप में एक स्पष्ट स्टैक इस सीमा से बचाता है, और नोडों को उसी क्रम में विज़िट करता है।
DFS कहाँ इस्तेमाल होता है?
बैकट्रैकिंग से भूलभुलैया और पहेलियाँ हल करने, साइकिल खोजने, कामों को उनकी निर्भरता के हिसाब से क्रम देने (टोपोलॉजिकल सॉर्ट), कनेक्टेड और स्ट्रॉन्गली कनेक्टेड कंपोनेंट खोजने, भूलभुलैया बनाने में, और डिपेंडेंसी ग्राफ़ पर चलने वाले कंपाइलर और बिल्ड टूल में।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
डेप्थ-फ़र्स्ट सर्च आज़माएँ