Apakah itu depth-first search (DFS)?

Question

Accepted Answer

**DFS** meneroka sesuatu graf dengan pergi sedalam mungkin di sepanjang setiap cabang sebelum berundur (backtrack). Ia menggunakan **stack** (selalunya call stack melalui recursion) dan melawat satu laluan penuh sebelum meneroka pilihan lain.

## Ideanya

Dari sesuatu nod, recurse ke jiran yang belum dilawati, dan terus pergi mendalam; apabila tersekat, undur dan cuba 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 lwn DFS

| | BFS | DFS |
|---|-----|-----|
| Struktur | queue | stack / recursion |
| Menemui | terpendek (tak berpemberat) | sebarang laluan |
| Memori | O(V) frontier | O(depth) |
| Sesuai untuk | laluan terpendek, aras | kitaran, topo sort, komponen |

## Kompleksiti

- **Masa:** O(V + E). **Ruang:** O(V) (kedalaman recursion + visited).

## Perangkap

Graf yang dalam boleh menyebabkan recursion stack overflow — guna stack eksplisit. Jejak `visited` untuk mengendalikan kitaran.

## Mengapa ia penting

DFS menjadi asas pengesanan kitaran, topological sort, connected components, dan penjanaan maze/laluan.

Keanggunan recursifnya menjadikan kod tree dan graf ringkas.

Mengetahui bila depth-first mengatasi breadth-first ialah kefasihan teras algoritma graf.

	BFS	DFS
Struktur	queue	stack / recursion
Menemui	terpendek (tak berpemberat)	sebarang laluan
Memori	O(V) frontier	O(depth)
Sesuai untuk	laluan terpendek, aras	kitaran, topo sort, komponen