---
# System prepended metadata

title: 'Tutorial Graph Traversal : DFS'
tags: [dfs, graph]

---

# 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<sub>1</sub> V<sub>1</sub>
U<sub>2</sub> V<sub>2</sub>
...
U<sub>M</sub> V<sub>M</sub>
</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*