Modul 4 [Traversal Graf] - lab-kcks/Modul-STRUKDAT GitHub Wiki

Traversal Graf

BFS

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:

  1. Visited
  2. Not Visited

Cara Kerja BFS:

  1. Dimulai dengan meletakkan vertex awal dari graph di queue paling belakang (enqueue)
  2. Ambil node yang berada paling depan (deque) lalu tambahkan vertex ke list visited.
  3. Cari tetangga dari node yang berada di queue paling depan. Apabila tidak ada di list visited, masukkan ke dalam list queue paling belakang (enqueue).
  4. Ulangi langkah 2 - 3 hingga seluruh node sudah dikunjungi.

Berikut adalah ilustrasi dari penggunaan BFS.

image

image

image

image

image

Sumber gambar: programiz.com

Untuk implementasi pada codingan akan dijelaskan pada modul 5 :D

DFS

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:

  1. Visited
  2. Not Visited

Cara Kerja DFS:

  1. Dimulai dengan meletakkan vertex awal dari graph pada stack (push).
  2. Ambil node yang berada paling bawah (pop) lalu tambahkan vertex ke list visited.
  3. Cari tetangga dari node yang berada di paling bawah. Apabila tidak ada di list visited, masukkan ke dalam stack (push).
  4. Ulangi langkah 2 - 3 hingga seluruh node sudah dikunjungi

Berikut adalah ilustrasi dari penggunaan DFS.

image

image

image

image

image

Sumber gambar: programiz.com

Untuk implementasi pada codingan akan dijelaskan pada modul 5 :D

Perbedaan BFS dan DFS

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

Referensi