DFS, Recursion और Iterative Stacks
गहराई तक explore करें और recursion limits से बचें
DFS, Recursion और Iterative Stacks, CoddyKit पर कोडिंग साक्षात्कार की तैयारी का एक निःशुल्क पाठ है। यह 4 में से 3वाँ पाठ है। आप नीचे पूरा पाठ निःशुल्क पढ़ सकते हैं—फिर अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर के साथ ब्राउज़र में इसका व्यावहारिक अभ्यास कर सकते हैं। यह कोडिंग साक्षात्कार की तैयारी सीखने के मार्ग का हिस्सा है और आपकी प्रगति वेब तथा CoddyKit ऐप पर सिंक होती रहती है। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 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 को पुनरावर्ती रूप से या अपने स्टैक के साथ चला सकते हैं, प्रवेश करते समय नोड को देखा गया चिह्नित कर सकते हैं और ग्राफ के बहुत गहरे होने पर पुनरावृत्तिमूलक तरीके पर जा सकते हैं। 🎉
एआई शिक्षक के साथ कोडिंग साक्षात्कार की तैयारी सीखें — निःशुल्क
अपने ब्राउज़र में वास्तविक कोड लिखें और चलाएँ, चौबीसों घंटे एआई शिक्षक से तुरंत सहायता पाएँ, और वेब या ऐप पर वहीं से शुरू करें जहाँ आपने छोड़ा था।
- पाठ्यक्रम
- 90
- पाठ
- 360
अक्सर पूछे जाने वाले प्रश्न
क्या “DFS, Recursion और Iterative Stacks” पाठ निःशुल्क है?
हाँ—“DFS, Recursion और Iterative Stacks” का पूरा पाठ यहाँ वेब पर निःशुल्क पढ़ा जा सकता है। इंटरैक्टिव अभ्यास (अंतर्निहित कोड संपादक और 24/7 एआई ट्यूटर) करने और कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम का बाकी हिस्सा अनलॉक करने के लिए CoddyKit PRO लें। कोडिंग साक्षात्कार की तैयारी पाठ्यक्रम में कुल 4 पाठ शामिल हैं।
“DFS, Recursion और Iterative Stacks” में मैं क्या सीखूँगा?
गहराई तक explore करें और recursion limits से बचें आप ब्राउज़र में सीधे चलाए जाने वाले व्यावहारिक कोड के साथ कोडिंग साक्षात्कार की तैयारी का अभ्यास करते हैं, और पाठ पूरा करते समय 24/7 एआई ट्यूटर आपके प्रश्नों के उत्तर देता है।
क्या कोडिंग साक्षात्कार की तैयारी शुरू करने के लिए मुझे किसी अनुभव की आवश्यकता है?
पहले के अनुभव की आवश्यकता नहीं है। CoddyKit पर कोडिंग साक्षात्कार की तैयारी शुरुआती से लेकर उन्नत शिक्षार्थियों तक सभी के लिए व्यवस्थित किया गया है, इसलिए आप यहीं से या शुरुआत से सीखना शुरू कर सकते हैं और अपनी गति से आगे बढ़ सकते हैं। यह 4 में से 3वाँ पाठ है।
“DFS, Recursion और Iterative Stacks” पाठ पूरा करने में कितना समय लगता है?
CoddyKit का अधिकांश पाठ लगभग 5–10 मिनट में पूरा हो जाता है। हर पाठ छोटा और संवादात्मक है, इसलिए आप लगातार प्रगति करते हैं और वेब या ऐप पर वहीं से सीखना जारी रख सकते हैं जहाँ आपने छोड़ा था।
क्या मैं इस कोडिंग साक्षात्कार की तैयारी पाठ में कोड लिख और चला सकता हूँ?
हाँ। हर कोडिंग साक्षात्कार की तैयारी पाठ में एक अंतर्निर्मित कोड संपादक शामिल है, जिससे आप सीधे अपने ब्राउज़र में वास्तविक कोड लिख और चला सकते हैं और तुरंत एआई प्रतिक्रिया पा सकते हैं—स्थानीय सेटअप की आवश्यकता नहीं है।
इस पाठ्यक्रम के सभी पाठ
- Input से Adjacency Lists
- Unweighted Paths की Shortest दूरी के लिए BFS
- DFS, Recursion और Iterative Stacks
- Connected Components और Flood Fill