depth-first search (DFS) म्हणजे काय?

Question

Accepted Answer

**DFS** एक graph ला प्रत्येक branch वर शक्य तितके खोल जाऊन, नंतर परत येऊन explore करते. हे **stack** वापरते (सहसा recursion च्या माध्यमातून call stack) आणि एक संपूर्ण path visit करून नंतर इतर पर्याय explore करते.

## संकल्पना

एका node वरून, एका unvisited neighbor मध्ये recursively जा, आणि खोलवर जाऊ; जेव्हा अडकून जा, तर परत आणि दुसरी branch वापर.

## उदाहरण

```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 |
| शोधते | सर्वात लहान (unweighted) | कोणतीही path |
| मेमोरी | O(V) frontier | O(depth) |
| चांगले असे | सर्वात लहान paths, levels | cycles, topo sort, components |

## Complexity

- **वेळ:** O(V + E). **स्पेस:** O(V) (recursion depth + visited).

## सावधानी

खोल graphs recursion stack overflow करू शकते — स्पष्ट stack वापरा. Cycles हाताळण्यासाठी `visited` track करा.

## हे महत्त्वाचे का आहे

DFS cycle detection, topological sort, connected components, आणि maze/path generation ला आधार देते.

याचे recursive elegance tree आणि graph code संक्षिप्त बनवते.

केव्हा depth-first breadth-first ला मात करते हे जाणून घेणे हे core graph-algorithm fluency आहे.

	BFS	DFS
संरचना	queue	stack / recursion
शोधते	सर्वात लहान (unweighted)	कोणतीही path
मेमोरी	O(V) frontier	O(depth)
चांगले असे	सर्वात लहान paths, levels	cycles, topo sort, components