ઊંડાઇ-પ્રથમ શોધ (DFS) શું છે?

Question

Accepted Answer

**DFS** એક ગ્રાફને એક-બીજાના બ્રાન્ચ વહીવટ બમણું આગળ જાય છે તે શોધે છે. તે **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) |
| માટે સારું | સૌથી ટૂંકા માર્ગ, સ્તર | ચક્ર, topo sort, ઘટક |

## જટિલતા

- **સમય:** O(V + E). **જગ્યા:** O(V) (આવર્તન ગહનતા + મુલાકાત).

## અંતર

ઊંડા આલેખ આવર્તન સ્ટેક ઓવરફ્લો કરી શકે છે — સ્પષ્ટ સ્ટેક ઉપયોગ કરો. ચક્ર સંભાળવા માટે `visited` ટ્રૅક કરો.

## તે શા માટે મહત્વપૂર્ણ છે

DFS ચક્ર શોધ, ટોપોલોજીકલ સોર્ટ, જોડાયેલ ઘટક, અને મેઝ/માર્ગ જનરેશનનો આધાર છે.

તેની આવર્તક કમનીયતા વૃક્ષ અને આલેખ કોડને સંક્ષિપ્ત બનાવે છે.

જ્યારે ઊંડાઇ-પ્રથમ પહોળાઈ-પ્રથમને હરાવે તે જાણવું મુખ્ય આલેખ-અલ્ગોરિધમ પ્રવાહીતા છે.

	BFS	DFS
માળખું	queue	stack / recursion
શોધે છે	સૌથી ટૂંકું (અવજણ્યું)	કોઈ પણ માર્ગ
મેમરી	O(V) frontier	O(depth)
માટે સારું	સૌથી ટૂંકા માર્ગ, સ્તર	ચક્ર, topo sort, ઘટક