Depth-First Search

गहरे जाएँ, फिर पीछे

DFS एक शाखा में तब तक उतरता है जब तक अंत न आए, फिर अंतिम अनदेखे कांटे तक लौटता है। Recursion (call stack) या स्पष्ट stack से। O(V + E)।

Recursive DFS

प्रवेश पर चिह्नित करें; अनदेखे पड़ोसियों में recurse करें।

def dfs(g, node, seen=None):
    if seen is None: seen = set()
    seen.add(node)
    for nb in g[node]:
        if nb not in seen:
            dfs(g, nb, seen)
    return seen

DFS किसमें अच्छा है

Cycle पहचान, connected components गिनना, topological sort, पथ अस्तित्व, और कोई भी संपूर्ण "सभी संयोजन आज़माएँ" search (जो backtracking है)।

त्वरित जाँच: आपको अभारित graph में सबसे छोटा पथ चाहिए। उपयोग करें...

• DFS
• BFS
• दोनों समान काम करते हैं