fbpx

Struktur Data : Graph Traversal

Mengunjungi tiap node dalam sebuah graph:

  1. DFS (Depth First Search): Pencarian mendalam, algoritma akan memanfaatkan stack
  2. BFS (Breadth First Search): Pencarian melebar, algoritma akan memanfaatkan queue

DPF (Depth First Search)

  1. 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.
  2. Jika adjacent node tidak ditemukan, pop sebuah node dari stack. Kunjungi adjacent node dari TOP stack.
  3. 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)

  1. 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.
  2. 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.
  3. 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.


Tonton juga video pilihan dari kami berikut ini

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up