DFS (Depth-First Search) ni nini?

Question

Accepted Answer

**DFS** huchunguza grafu kwa kuenda kwa kina kadiri iwezekanavyo kwenye kila tawi kabla ya kurudi nyuma. Inatumia **stack** (mara nyingi call stack kupitia rekureni) na huboresha njia kamili kabla ya kuchunguza mbadala.

## Wazo

Kutoka kwa nodi, rekursa ndani ya jibu ambalo halijatembeani, na endelea kwa kina; wakati umekwama, rudi nyuma na jaribu tawi lingine.

## Mfano

```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 dhidi ya DFS

| | BFS | DFS |
|---|-----|-----|
| Muundo | queue | stack / rekureni |
| Hupata | fupi zaidi (isiyo na uzani) | njia yoyote |
| Kumbukumbu | O(V) frontier | O(kina) |
| Nzuri kwa | njia fupi, viwango | mizunguko, topo sort, sehemu |

## Utata

- **Wakati:** O(V + E). **Nafasi:** O(V) (kina cha rekureni + zilizotembeani).

## Mitego

Grafu zenye kina kubwa inaweza kuzidi stack ya rekureni — tumia stack ya dhahiri. Fuatilia `visited` ili kushughulikia mizunguko.

## Kwa nini ni muhimu

DFS ndio msingi wa ugunduzi wa mizunguko, kupanga kwa topolojia, sehemu zilizounganishwa, na kuundwa kwa labirint/njia.

Ubora wake wa rekursivo unafanya nambari za mti na grafu kuwa fupi.

Kujua wakati kina-kwanza kinashinda upana-kwanza ni ujuzi wa msingi wa algoriti za grafu.

	BFS	DFS
Muundo	queue	stack / rekureni
Hupata	fupi zaidi (isiyo na uzani)	njia yoyote
Kumbukumbu	O(V) frontier	O(kina)
Nzuri kwa	njia fupi, viwango	mizunguko, topo sort, sehemu