Apa iku depth-first search (DFS)?

Question

Accepted Answer

**DFS** nggali graph kanthi ora ing sajrone saben cabang sadurunge mundur. Iku nggunakake **stack** (asring stack panggilan liwat rekursi) lan ngunjungi sawijine dalan lengkap sadurunge nggali alternatif liyane.

## Gagasane

Saka sawijine node, rekursi menyang tangga sing durung ditiliki, lan terus njero; yen macet, mundur lan coba cabang liyane.

## Conto

```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 / rekursi |
| Nemokake | paling cendhek (ora dibobot) | dalan apa wae |
| Memori | O(V) frontier | O(kedalaman) |
| Apik kanggo | dalan paling cendhek, tingkat | siklu, sortir topo, komponen |

## Kerumitan

- **Wektu:** O(V + E). **Ruang:** O(V) (kedalaman rekursi + ditiliki).

## Jebakan

Graf sing jero bisa nglowongake stack rekursi — gunakake stack eksplisit. Lacak `visited` kanggo nangani siklu.

## Apa iku pentinge

DFS dadi fondasi deteksi siklu, sortir topologis, komponen terkoneksi, lan generasi labirin/dalan.

Kenalan rekursifen e agawe kod tangga lan graph ringkes.

Ngreti nalika depth-first ngalahake breadth-first iku kaetahanan inti algoritmik graph.

	BFS	DFS
Struktur	queue	stack / rekursi
Nemokake	paling cendhek (ora dibobot)	dalan apa wae
Memori	O(V) frontier	O(kedalaman)
Apik kanggo	dalan paling cendhek, tingkat	siklu, sortir topo, komponen