Python में Depth-First Search (DFS)
Backtrack करने से पहले एक path में गहराई तक जाएँ।
में Depth-First Search (DFS) क्या है?
समस्या क्या है
भूलभुलैया से बाहर का रास्ता ढूँढना, यह जाँचना कि graph में cycle है या नहीं, या एक-दूसरे पर निर्भर tasks को क्रम देना, इन सबमें दूसरा रास्ता आज़माने से पहले एक रास्ते पर जितना हो सके उतना आगे जाना होता है। यही depth-first search है।
ऐसे समझें
Depth-first search वैसे ही है जैसे आप धागे की गेंद लेकर गुफा खोजते हैं। आप एक सुरंग में जितना गहरा जा सकें जाते हैं। रास्ता बंद मिलने पर धागा पकड़कर पिछले मोड़ तक लौटते हैं और अगली सुरंग आज़माते हैं। आप खोजी हुई सुरंगों पर निशान लगाते हैं ताकि कभी दो बार न जाएँ।
visited.add(node)🧵 इस सुरंग पर खोजी हुई का निशान लगाइएfor neighbor in graph[node]:🔀 यहाँ से हर सुरंग देखिएdepth_first(neighbor, visited)⬇️ पहली बिना खोजी सुरंग में गहरे जाइएreturn order↩️ रास्ता बंद: धागा पकड़कर लौटिएDepth-first search (DFS) graph को backtrack करने से पहले एक शाखा में जितना गहरा हो सके जाकर खोजता है, आमतौर पर recursion या stack के साथ।
मुख्य बातें
visited.add(node)node को मार्क करता है, ताकि cycles अंतहीन recursion न बनाएँ।for neighbor in graph[node]:हर पड़ोसी को बारी-बारी देखता है।order.extend(depth_first(neighbor, visited))अगले पड़ोसी से पहले एक पड़ोसी के नीचे की पूरी शाखा खोजता है।- नतीजे में D, C से पहले आता है, क्योंकि B की शाखा पहले पूरी होती है।
इसका उपयोग कब करें?
- कोई भी रास्ता ढूँढना, backtracking से भूलभुलैया और पहेलियाँ हल करना।
- Cycles पकड़ना और निर्भरता वाले tasks को क्रम देना (topological sort)।
- Graph के सारे जुड़े हिस्से खोजना।
कब ज़रूरत नहीं
- आपको सबसे छोटा रास्ता चाहिए: depth-first search पहले लंबा रास्ता ढूँढ सकता है; breadth-first search इस्तेमाल कीजिए।
- बहुत गहरे graph: recursion Python की limit तक पहुँच सकता है; explicit stack इस्तेमाल कीजिए।
Python में Depth-First Search (DFS) Visualizer
O(V+E)हर comparison और data movement देखने के लिए चलाएँ या अगला चरण दबाएँ।
उदाहरण कोड
graph = {"A": ["B", "C"], "B": ["D"], "C": ["E"], "D": [], "E": []}
def depth_first(node, visited=None):
visited = visited or set()
visited.add(node)
order = [node]
for neighbor in graph[node]:
if neighbor not in visited:
order.extend(depth_first(neighbor, visited))
return order
print(depth_first("A"))
अपेक्षित आउटपुट
['A', 'B', 'D', 'C', 'E']
यह कैसे काम करता है
हर vertex और edge अधिकतम एक बार process होता है: जटिलता O(V+E) है।
मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।
अभ्यास के कार्य
बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।
- खाली input, एक element और duplicate values जाँचें।
- हर चरण के बाद state दिखाएँ।
- Performance को दूसरे solution से तुलना करें।
आम गलतियाँ
Mutable default argument इस्तेमाल करना
visited=set() अलग-अलग कॉल के बीच शेयर हो जाएगा।
def depth_first(node, visited=set()):
def depth_first(node, visited=None):
visited = visited or set()
यह पाठ पूरा कर लिया?
अपनी प्रगति ट्रैक करने के लिए इसे सीखा हुआ मार्क करें।
चैलेंज से अभ्यास करें
इस पाठ में सीखी बात से एक असली समस्या हल करें। हर चैलेंज ब्राउज़र में चलता है, तुरंत टेस्ट और AI रिव्यू के साथ।
- Count Islands Count groups of connected land cells in a grid. मध्यम
- Strongly Connected Components Count groups of nodes that can all reach each other. कठिन
- Longest Path in a DAG Find the heaviest path in a task dependency graph. कठिन