Derinlik-öncelikli arama (DFS) nedir?

Question

Accepted Answer

**DFS** bir grafiği her dalda geri dönmeden önce mümkün olduğunca derin giderek araştırır. Bir **yığın** (genellikle özyineleme yoluyla çağrı yığını) kullanır ve alternatifleri araştırmadan önce tam bir yolu ziyaret eder.

## Fikir

Bir düğümden, ziyaret edilmemiş bir komşuya özyinelemeli olarak girin ve derin devam edin; sıkışıp kalırsanız, geri dönün ve başka bir dalı deneyin.

## Örnek

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

| | BFS | DFS |
|---|-----|-----|
| Yapı | kuyruk | yığın / özyineleme |
| Bulur | en kısa (ağırlıksız) | herhangi bir yol |
| Bellek | O(V) frontier | O(derinlik) |
| İyi | en kısa yollar, seviyeler | döngüler, topo sort, bileşenler |

## Karmaşıklık

- **Zaman:** O(V + E). **Alan:** O(V) (özyineleme derinliği + ziyaret edilmiş).

## Tuzaklar

Derin grafikler özyineleme yığınını aşabilir — açık bir yığın kullanın. Döngüleri işlemek için `visited` izleyin.

## Neden önemli

DFS döngü tespiti, topolojik sıralama, bağlı bileşenler ve labirent/yol oluşturmanın temelini oluşturur.

Onun özyinelemeli zarafeti ağaç ve grafik kodunu kısa tutup.

	BFS	DFS
Yapı	kuyruk	yığın / özyineleme
Bulur	en kısa (ağırlıksız)	herhangi bir yol
Bellek	O(V) frontier	O(derinlik)
İyi	en kısa yollar, seviyeler	döngüler, topo sort, bileşenler