# Depth-First Search — डेटा स्ट्रक्चर और एल्गोरिदम

Source: https://www.geekswithgeeks.com/hi/dsa/dfs

> एक पथ को जितना गहरा हो सके अनुसरण करें, फिर backtrack करें — recursion के लिए स्वाभाविक।

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

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

## Recursive DFS

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

```python
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 है)।

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

- [ ] DFS
- [x] BFS
- [ ] दोनों समान काम करते हैं

*Answer:* BFS. BFS दूरी के क्रम में खोजता है, तो लक्ष्य तक पहली बार पहुँचना सबसे छोटा पथ है। DFS ऐसी गारंटी नहीं देता।