# Tutorial Graph Traversal : DFS

###### tags: `graph` `dfs`

## Karakteristik DFS

- Melusuri node tepat sekali dan yang lebih dalam terlebih dulu
- Dapat diimplementasikan dengan 2 cara :
1. Pakai Stack
2. Pakai Rekursi

## Contoh Soal Sederhana

Diberikan $N$ node dan $M$ undirected edge. Tuliskan semua urutan penelusuran dari node $1$ ke $N$ jika kita harus mengunjungi node yg lebih dalam terlebih dahulu.

### Batasan

- $2 \le N \le 1000$
- $1 \le M \le \min(1000,\frac{N\times(N+1)}{2})$

### Format Masukan

<pre>
N M
U₁ V₁
U₂ V₂
...
U_M V_M
</pre>

### Format Keluaran

Keluarkan beberapa baris berisi sebuah string yang menyatakan urutan-urutan penelusuran. Jika sekarang kita sedang memasuki sebuah node, keluarkan `Masuk ke node <index node sekarang>`.

Jika ada lebih dari satu jawaban, keluarkan yang mana saja.

### Contoh Masukan

11 13
1 2
1 6
1 7
1 10
1 11
2 3
2 4
3 4
4 5
7 8
7 9
9 10
10 11

### Contoh Keluaran

Salah satu keluaran yang mungkin

Masuk ke node 1
Masuk ke node 2
Masuk ke node 3
Masuk ke node 4
Masuk ke node 5
Masuk ke node 6
Masuk ke node 7
Masuk ke node 8
Masuk ke node 9
Masuk ke node 10
Masuk ke node 11

## Solusi

1. Menggunakan `rekursi`

<details>
<summary>Solusi</summary>
<a href="https://ideone.com/tiCbZr">link</a>
</details>

2. Menggunakan `stack`

<details>
<summary>Solusi</summary>
<a href="https://ideone.com/4A6x1l">link</a>
</details>

## Kompleksitas waktu

1. $O(N^2)$, jika menggunakan *adjacency matrix*
2. $O(N+M)$, jika menggunakan *adjacency list*