Competitive Programming Academy · पाठ

DFS, Recursion और Iterative Stacks

गहराई तक explore करें और recursion limits से बचें

पाठ 3, कुल 4 में से13 चरण

DFS, Recursion और Iterative Stacks, CoddyKit पर Competitive Programming Academy का एक निःशुल्क पाठ है। यह 4 में से 3वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह Competitive Programming Academy सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। Competitive Programming Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

DFS क्या करता है

DFS किसी एक मार्ग पर जितना संभव हो उतना गहराई तक जाता है, फिर पीछे लौटकर अगला मार्ग आज़माता है। इसे भूलभुलैया के गलियारे-दर-गलियारे अन्वेषण की तरह समझें। 🧭

DFS बनाम BFS

BFS वृत्ताकार परतों में फैलता है, जबकि DFS पहले गहराई में जाता है। दोनों हर पहुँच योग्य नोड पर जाते हैं, लेकिन बहुत अलग क्रम में।

पुनरावर्ती रूप

पुनरावर्ती DFS किसी नोड को देखा गया चिह्नित करता है, फिर हर ऐसे पड़ोसी पर स्वयं को बुलाता है जिसे अभी नहीं देखा गया है। कॉल स्टैक लौटने का स्थान याद रखता है।

def dfs(u):
    visited[u] = True
    for v in adj[u]:
        if not visited[v]:
            dfs(v)

पुनरावर्तन से पहले चिह्नित करें

पड़ोसियों को खोजने से पहले, नोड में प्रवेश करते ही उसे देखा गया चिह्नित करें। ऐसा न करने पर चक्र DFS को अनंत पुनरावर्तन में भेज देंगे।

पुनरावर्तन सीमा का जाल

पाइथन पुनरावर्तन को लगभग 1000 कॉल तक सीमित रखता है। गहरा ग्राफ RecursionError उत्पन्न करता है, जो कार्यकाल त्रुटि के परिणाम के रूप में दिखाई देता है।

सीमा बढ़ाएँ

एक त्वरित समाधान setrecursionlimit से इस सीमा को बढ़ाना है। DFS चलाने से पहले इसे अपनी अधिकतम संभावित गहराई से अधिक रखें।

import sys
sys.setrecursionlimit(300000)

इसके बजाय पुनरावृत्तिमूलक तरीका अपनाएँ

सबसे सुरक्षित समाधान अपने स्वयं के स्टैक का उपयोग करके पुनरावृत्तिमूलक DFS चलाना है। कॉल की गहराई न होने से कभी पुनरावर्तन संबंधी क्रैश नहीं होगा।

stack = [start]

स्टैक से pop करें

हर चरण में स्टैक के ऊपर वाले तत्व को pop करें। बाद में आया पहले बाहर जाता है, इसलिए DFS सबसे हाल के मार्ग पर पहले गहराई में जाता है।

u = stack.pop()

पड़ोसियों को स्टैक में डालें

u को pop करने के बाद हर ऐसे पड़ोसी को स्टैक में डालें जिसे अभी नहीं देखा गया है। उन्हें चिह्नित करें ताकि वे दोबारा न डाले जाएँ।

for v in adj[u]:
    if not visited[v]:
        visited[v] = True
        stack.append(v)

पूरा पुनरावृत्तिमूलक लूप

जब तक स्टैक में नोड हों, pop और डालने की प्रक्रिया दोहराएँ। स्टैक खाली होने पर हर पहुँच योग्य नोड देखा जा चुका होगा।

while stack:
    u = stack.pop()
    for v in adj[u]:
        if not visited[v]:
            visited[v] = True
            stack.append(v)

BFS जितनी ही लागत

BFS की तरह DFS भी हर नोड और एज को एक बार देखता है, इसलिए इसकी समय-जटिलता O(n + m) है। कार्य के अनुकूल क्रम के आधार पर इनमें से चुनें।

त्वरित जाँच

गहरे ग्राफ पर आपका पुनरावर्ती DFS क्रैश हो जाता है। क्यों?

इंटरैक्टिव पाठ में इसका उत्तर दें

पुनरावलोकन

आप DFS को पुनरावर्ती रूप से या अपने स्टैक के साथ चला सकते हैं, प्रवेश करते समय नोड को देखा गया चिह्नित कर सकते हैं और ग्राफ के बहुत गहरे होने पर पुनरावृत्तिमूलक तरीके पर जा सकते हैं। 🎉

शुरुआत निःशुल्क

एआई शिक्षक के साथ Python सीखें — निःशुल्क

अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।

पाठ्यक्रम: 30
पाठ: 120

निःशुल्क सीखना शुरू करें पूरा पाठ्यक्रम देखें

अक्सर पूछे जाने वाले प्रश्न

क्या “DFS, Recursion और Iterative Stacks” पाठ निःशुल्क है?

हाँ—“DFS, Recursion और Iterative Stacks” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और Competitive Programming Academy पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। Competitive Programming Academy पाठ्यक्रम में कुल 4 पाठ शामिल हैं।

“DFS, Recursion और Iterative Stacks” में मैं क्या सीखूँगा?

गहराई तक explore करें और recursion limits से बचें आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ Competitive Programming Academy का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।

क्या Competitive Programming Academy शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?

पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर Competitive Programming Academy शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 3वाँ पाठ है।

“DFS, Recursion और Iterative Stacks” पाठ पूरा करने में कितना समय लगता है?

CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।

क्या मैं इस Competitive Programming Academy पाठ में कोड लिख और चला सकता हूँ?

हाँ। हर Competitive Programming Academy पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।

इस पाठ्यक्रम के सभी पाठ

Input से Adjacency Lists
Unweighted Paths की Shortest दूरी के लिए BFS
DFS, Recursion और Iterative Stacks
Connected Components और Flood Fill

← Competitive Programming Academy पर वापस जाएँ