गहिराइ-पहिलो खोज (DFS) भनेको के हो?

Question

Accepted Answer

**DFS** ले ग्राफलाई प्रत्येक शाखामा जडबारी अगाडि जाएर अन्वेषण गर्छ। यसले **स्ट्याक** (अक्सर रिकर्सन माध्यमबाट कल स्ट्याक) प्रयोग गर्छ र विकल्पहरू अन्वेषण गर्नु अघी पूरो पथ भ्रमण गर्छ।

## विचार

एक नोडबाट अदर्शनीय छिमेकीमा रिकर्स गर्नुहोस्, र गहिराइमा जाँदै रहनुहोस्; अलमलमा परेपछी, फिर्ता गएर अर्को शाखा प्रयास गर्नुहोस्।

## उदाहरण

```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) सीमान्त | O(गहिराइ) |
| राम्रोको लागी | सबैभन्दा छोटो पथ, स्तरहरू | चक्र, topo sort, घटक |

## जटिलता

- **समय:** O(V + E)। **स्पेस:** O(V) (रिकर्सन गहिराइ + दर्शन गरिएको)।

## समस्याहरू

गहिराइ ग्राफ रिकर्सन स्ट्याक ओभरफ्लो गर्न सक्छ — स्पष्ट स्ट्याक प्रयोग गर्नुहोस्। चक्र सम्हाल्नको लागी `visited` ट्र्याक गर्नुहोस्।

## महत्व

DFS ले चक्र पहचान, topological sort, जोडिएको घटक, र maze/पथ उत्पादन गर्दछ।

यसको रिकर्सिभ सुन्दरता रुख र ग्राफ कोड संक्षिप्त बनाउँछ।

गहिराइ-पहिलो कहिले चौडाइ-पहिलो हराउँछ भनेर जान्नु मूल ग्राफ-एल्गोरिदम बहुमुखिताको अंश हो।

	BFS	DFS
संरचना	queue	stack / recursion
खोज्छ	सबैभन्दा छोटो (वजन बिना)	कुनै पनि पथ
मेमोरी	O(V) सीमान्त	O(गहिराइ)
राम्रोको लागी	सबैभन्दा छोटो पथ, स्तरहरू	चक्र, topo sort, घटक