📋 Daftar Isi
Mengunjungi tiap node dalam sebuah graph:
- DFS (Depth First Search): Pencarian mendalam, algoritma akan memanfaatkan stack
- BFS (Breadth First Search): Pencarian melebar, algoritma akan memanfaatkan queue
DPF (Depth First Search)
- Kunjungi adjacent node yang belum dikunjungi. Tandai node tersebut dengan “sudah dikunjungi”. Tampilkan (atau lakukan hal lain tergantung tujuan traversal). Push node tersebut ke stack.
- Jika adjacent node tidak ditemukan, pop sebuah node dari stack. Kunjungi adjacent node dari TOP stack.
- Ulangi langkah 1 dan 2 sampai stack habis.
Berikut ini urutan langkah-langkah yang dilakukan:
Setelah ambil B, tidak ada adjacent node yang belum dikunjungi. Jadi pop B dan cari adjacent node dari TOP stack (D) yaitu C.
BFS (Breadth First Search)
- Kunjungi adjacent node yang belum dikunjungi. Tandai node tersebut dengan “sudah dikunjungi”. Tampilkan (atau lakukan hal lain tergantung tujuan traversal). Enqueue node tersebut ke queue.
- Selama queue masih ada isinya maka Dequeue node dari queue (misal node front w dan (foreach) Kunjungi setiap adjacent node dari node w. Tandai node tersebut dengan “sudah
dikunjungi”. Tampilkan (atau lakukan hal lain tergantung tujuan traversal). Enqueue node tersebut ke queue. - Ulangi langkah 2 sampai queue habis
Berikut ini urutan langkah-langkah yang dilakukan:
Latihan
Perhatikan graph tersebut. Bagaimana traversal graph ini jika dimulai dari node 0/A dan node lebih kecil didahulukan?
- untuk gambar a, DFS : 0 1 2 4 3, BFS : 0 1 2 3 4
- untuk gambar b, DFS : A B C E D F, BFS : A B C D E F
Materi Lengkap
Silakan baca juga beberapa artikel menarik kami tentang Graph, daftar lengkapnya adalah sebagai berikut.
