DFS (Depth-First Search) ni nini?

Question

IT Interview Practice · 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

Wazo

Mfano

BFS dhidi ya DFS

Utata

Mitego

Kwa nini ni muhimu

Maswali yanayohusiana