Depth-first search (DFS) کیا ہے؟

Question

Accepted Answer

**DFS** ایک گراف کو ہر برانچ کے ساتھ زیادہ سے زیادہ گہرائی میں جاتے ہوئے دریافت کرتا ہے اور پھر واپس آتا ہے۔ یہ ایک **stack** استعمال کرتا ہے (اکثر recursion کے ذریعے call stack) اور متبادل کو دریافت کرنے سے پہلے ایک مکمل راستہ وزٹ کرتا ہے۔

## خیال

ایک نوڈ سے، ایک غیر ملاقات شدہ ہمسائے میں recursion کریں، اور گہرائی میں جاتے رہیں؛ جب پھنس جائیں، واپس اوپر آئیں اور دوسری برانچ کو آزمائیں۔

## مثال

```python
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    order = [node]
    for nbr in graph[node]:
        if nbr not in visited:
            order += dfs(graph, nbr, visited)  # go deeper first
    return order

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
dfs(graph, 'A')                        # -> ['A', 'B', 'D', 'C']
```

## BFS بمقابلہ DFS

| | BFS | DFS |
|---|-----|-----|
| ڈھانچہ | queue | stack / recursion |
| تلاش کریں | سب سے مختصر (غیر وزنی) | کوئی بھی راستہ |
| میموری | O(V) frontier | O(depth) |
| کے لیے اچھا ہے | سب سے مختصر راستے، سطحیں | cycles، topo sort، components |

## پیچیدگی

- **وقت:** O(V + E)۔ **جگہ:** O(V) (recursion کی گہرائی + وزٹ شدہ)۔

## نقصانات

گہرے گرافس recursion stack کو overflow کر سکتے ہیں — ایک explicit stack استعمال کریں۔ cycles کو ہینڈل کرنے کے لیے `visited` کو ٹریک کریں۔

## اہمیت

DFS cycle detection، topological sort، connected components، اور maze/path generation میں بنیادی کردار ادا کرتا ہے۔

اس کی recursive خوبصورتی tree اور graph کوڈ کو جامع بناتی ہے۔

جاننا کہ کب depth-first breadth-first کو شکست دے رہا ہے، یہ graph-algorithm fluency کا بنیادی حصہ ہے۔

	BFS	DFS
ڈھانچہ	queue	stack / recursion
تلاش کریں	سب سے مختصر (غیر وزنی)	کوئی بھی راستہ
میموری	O(V) frontier	O(depth)
کے لیے اچھا ہے	سب سے مختصر راستے، سطحیں	cycles، topo sort، components