Menene sakewa mai shuni-jiya (DFS)?

Question

Accepted Answer

**DFS** tana binciken jadawali ta hanyar tafiya sosai kai da kai tare da kowane reshe kafin jiya. Tana amfani da **stack** (sau da yawa call stack ta hanyar recursion) da kuma hutu da cikakken hanya kafin bada zaure.

## Tunanin

Daga nodda, sake zirge zuwa abokin gida da ba a gana ba, kuma koma jiya; idan an kulle, koma jiya kuma gwada wani reshe.

## Misali

```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 da DFS

| | BFS | DFS |
|---|-----|-----|
| Tsari | queue | stack / recursion |
| Samu | gari (ba mai nauyi) | duk wata hanya |
| Alaƙa | O(V) frontier | O(depth) |
| Kyau don | gararrun gari, matakan | kuɗi, shan topo, abubuwan haɗi |

## Hadaddun

- **Lokaci:** O(V + E). **Sarari:** O(V) (zurummin recursion + gana).

## Maye

Zaɓuwa masu zurumi zasu iya cire jujjuya stack na zirge — yi amfani da sarari sarari. Raku aiki da `visited` don shawo harkokin kuɗi.

## Me ya sa yana muhimmi

DFS shine tushe na gano kuɗi, shan topo, abubuwan haɗi, da samuwar labari/hanya.

Sararin sa na zirge tana sauƙi jadawali da kuma koda gida.

Sanin lokaci mai zurumi-jiya ya bugi farin jiya shine mahimmanci na jadawali-algorithm gaskiya.

	BFS	DFS
Tsari	queue	stack / recursion
Samu	gari (ba mai nauyi)	duk wata hanya
Alaƙa	O(V) frontier	O(depth)
Kyau don	gararrun gari, matakan	kuɗi, shan topo, abubuwan haɗi