# Tutorial Graph Traversal : BFS

###### tags: `graph` `bfs`

## Karakteristik BFS

- Melusuri node tepat sekali
- Mengunjungi node yang lebih dekat dengan node awal
- Dapat diimplementasikan dengan `queue`

## 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 dekat dengan node awal 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 6
Masuk ke node 7
Masuk ke node 10
Masuk ke node 11
Masuk ke node 3
Masuk ke node 4
Masuk ke node 8
Masuk ke node 9
Masuk ke node 5

## Solusi

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

## Kompleksitas waktu

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