Python एल्गोरिदम

Python में Depth-First Search (DFS)

Backtrack करने से पहले एक path में गहराई तक जाएँ।

  • मध्यम
  • 2 मिनट में पढ़ें
  • 1 चलाने योग्य उदाहरण

में 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 के साथ।

मुख्य बातें

  1. visited.add(node) node को मार्क करता है, ताकि cycles अंतहीन recursion न बनाएँ।
  2. for neighbor in graph[node]: हर पड़ोसी को बारी-बारी देखता है।
  3. order.extend(depth_first(neighbor, visited)) अगले पड़ोसी से पहले एक पड़ोसी के नीचे की पूरी शाखा खोजता है।
  4. नतीजे में 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 देखने के लिए चलाएँ या अगला चरण दबाएँ।

उदाहरण कोड

कोड चलाएँ →
main.py
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"))
इस उदाहरण के लिए Run बटन बनाएँ

अपेक्षित आउटपुट

['A', 'B', 'D', 'C', 'E']

यह कैसे काम करता है

हर vertex और edge अधिकतम एक बार process होता है: जटिलता O(V+E) है।

मान बदलें और Python इंस्टॉल किए बिना CodeUtility ऑनलाइन Python कंपाइलर में प्रोग्राम चलाएँ।

अभ्यास के कार्य

बड़े dataset पर जाने से पहले input बदलें और edge cases की जाँच करें।

  1. खाली input, एक element और duplicate values जाँचें।
  2. हर चरण के बाद state दिखाएँ।
  3. Performance को दूसरे solution से तुलना करें।
Python IDE में चलाएँ →

आम गलतियाँ

Mutable default argument इस्तेमाल करना

visited=set() अलग-अलग कॉल के बीच शेयर हो जाएगा।

समस्या
def depth_first(node, visited=set()):
सुधार
def depth_first(node, visited=None):
    visited = visited or set()

यह पाठ पूरा कर लिया?

अपनी प्रगति ट्रैक करने के लिए इसे सीखा हुआ मार्क करें।

अगला: Python में बाइनरी सर्च ट्री →

चैलेंज से अभ्यास करें

इस पाठ में सीखी बात से एक असली समस्या हल करें। हर चैलेंज ब्राउज़र में चलता है, तुरंत टेस्ट और AI रिव्यू के साथ।

सभी चैलेंज