Apa itu pencarian mendalam pertama (DFS)?

Question

Accepted Answer

**DFS** menjelajahi grafik dengan pergi sedalam mungkin di sepanjang setiap cabang sebelum mundur. Menggunakan **stack** (sering call stack melalui recursion) dan mengunjungi seluruh jalur sebelum menjelajahi alternatif.

## Ide

Dari node, recurse ke tetangga yang belum dikunjungi, dan terus pergi dalam; ketika terjebak, mundur dan coba cabang lain.

## Contoh

```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 |
|---|-----|-----|
| Struktur | queue | stack / recursion |
| Mencari | terpendek (tidak berbobot) | jalur apa pun |
| Memori | O(V) frontier | O(depth) |
| Baik untuk | jalur terpendek, level | siklus, topo sort, komponen |

## Kompleksitas

- **Waktu:** O(V + E). **Ruang:** O(V) (kedalaman recursion + dikunjungi).

## Jebakan

Grafik dalam dapat meluap stack recursion — gunakan stack eksplisit. Lacak `visited` untuk menangani siklus.

## Mengapa ini penting

DFS mendasari deteksi siklus, pengurutan topologi, komponen terhubung, dan pembuatan labirin/jalur.

Elegan rekursifnya membuat kode pohon dan grafik ringkas.

Mengetahui kapan kedalaman-pertama mengalahkan lebar-pertama adalah kelancaran algoritma-grafik inti.

	BFS	DFS
Struktur	queue	stack / recursion
Mencari	terpendek (tidak berbobot)	jalur apa pun
Memori	O(V) frontier	O(depth)
Baik untuk	jalur terpendek, level	siklus, topo sort, komponen