Mengenal Algoritma Breadth-First Search (BFS)

Breadth-First Search (BFS) adalah algoritma traversing atau pencarian pada graf yang dimulai dari simpul akar dan menjelajahi semua tetangga simpul tersebut terlebih dahulu sebelum berpindah ke tingkat simpul berikutnya.

Karakteristik BFS

• Menggunakan struktur data antrian (queue).
• Menjelajahi graf secara level demi level.
• Menjamin pencarian jalur terpendek pada graf tak berbobot.

Cara Kerja BFS

1. Pilih simpul awal dan tandai sebagai dikunjungi.
2. Masukkan simpul tersebut ke dalam antrian.
3. Selama antrian tidak kosong:
   • Ambil simpul dari depan antrian.
   • Periksa semua tetangganya.
   • Jika tetangga belum dikunjungi, tandai dan masukkan ke antrian.

Pseudocode BFS

BFS(graf, simpul_awal):
  buat antrian Q
  tandai simpul_awal sebagai dikunjungi
  Q.enqueue(simpul_awal)

  selama Q tidak kosong:
    simpul = Q.dequeue()
    untuk setiap tetangga dari simpul:
      jika tetangga belum dikunjungi:
        tandai tetangga
        Q.enqueue(tetangga)

Contoh Implementasi dalam JavaScript

function bfs(graph, start) {
  let queue = [start];
  let visited = { [start]: true };

  while (queue.length > 0) {
    let node = queue.shift();
    console.log(node);

    for (let neighbor of graph[node]) {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.push(neighbor);
      }
    }
  }
}

Kapan Menggunakan BFS?

• Untuk mencari jalur terpendek pada graf tak berbobot.
• Saat ingin menjelajahi graf secara level demi level.
• Untuk pemecahan masalah seperti teka-teki atau puzzle.