Modul 4 [Traversal Graf]
BFS atau Breadth First Search adalah metode pencarian jalur agar tidak ada 1 node yang sama terulang (untuk menghindari cycle) pada graph. BFS akan melakukan traversal untuk setiap layer dari graph. Layer 1 -> Layer 2 -> dst hingga selesai.
BFS bekerja dengan mengimplementasikan queue. BFS biasanya membagi vertex pada graph menjadi 2 kategori:
- Visited
- Not Visited
Cara Kerja BFS:
- Dimulai dengan meletakkan vertex awal dari graph di queue paling belakang (enqueue)
- Ambil node yang berada paling depan (deque) lalu tambahkan vertex ke list visited.
- Cari tetangga dari node yang berada di queue paling depan. Apabila tidak ada di list visited, masukkan ke dalam list queue paling belakang (enqueue).
- Ulangi langkah 2 - 3 hingga seluruh node sudah dikunjungi.
Berikut adalah ilustrasi dari penggunaan BFS.
Sumber gambar: programiz.com
Untuk implementasi pada codingan akan dijelaskan pada modul 5 :D
DFS atau Depth First Search adalah metode yang digunakan untuk mencari jalur agar dapat menghindari cycle pada graph. Bedanya dengan BFS adalah DFS melakukan traversal hingga ke vertex paling 'dalam'.
DFS memanfaatkan stack & mengkategorikan vertex pada graph menjadi 2 kategori:
- Visited
- Not Visited
Cara Kerja DFS:
- Dimulai dengan meletakkan vertex awal dari graph pada stack (push).
- Ambil node yang berada paling bawah (pop) lalu tambahkan vertex ke list visited.
- Cari tetangga dari node yang berada di paling bawah. Apabila tidak ada di list visited, masukkan ke dalam stack (push).
- Ulangi langkah 2 - 3 hingga seluruh node sudah dikunjungi
Berikut adalah ilustrasi dari penggunaan DFS.
Sumber gambar: programiz.com
Untuk implementasi pada codingan akan dijelaskan pada modul 5 :D
| Pembeda | BFS | DFS |
|---|---|---|
| Kepanjangan | Breadth First Search | Depth First Search |
| Struktur Data | queue | stack |
| Definisi | traversal dengan menelusuri seluruh node dalam 1 layer | traversal dengan menelusuri node sejauh mungkin hingga tidak ada nearby nodes |
| Pendekatan | First In First Out (FIFO) | Last In First Out (LIFO) |
| Cocok untuk | Mencari vertex yang lebih dekat ke source | Mencari solusi lain yang jauh dari source |
| Backtracking | tidak ada | ada |
| Memory | lebih banyak | lebih sedikit |
| Kecepatan | lebih lambat | lebih cepat |