Breadth First Search

Breadth First Search: Cara Kerja, Contoh dan Kode Program

Dalam dunia ilmu komputer, pencarian dan eksplorasi data dalam struktur seperti graf dan pohon adalah tugas yang sangat penting. Salah satu algoritma yang sering digunakan untuk tujuan ini adalah Breadth First Search (BFS). BFS adalah metode eksplorasi yang dilakukan secara berlapis, dimulai dari satu simpul (node) awal, lalu menjelajahi semua tetangga terdekat sebelum beralih ke tingkat berikutnya.

Dalam artikel ini, kita akan membahas konsep dasar BFS, cara kerja, implementasi dalam kode program, kompleksitas, serta berbagai aplikasinya. Dengan pemahaman yang mendalam tentang BFS, kamu dapat menggunakannya untuk menyelesaikan berbagai permasalahan pemrograman dan algoritma secara lebih efektif.

Pengertian Breadth First Search (BFS)

Breadth First Search (BFS) adalah salah satu algoritma pencarian dalam graf dan pohon. Algoritma ini sering digunakan dalam berbagai aplikasi mulai dari pencarian jalur terpendek, pemrosesan gambar, hingga kecerdasan buatan.

Secara sederhana, BFS bekerja dengan menjelajahi semua node pada satu tingkat sebelum berpindah ke tingkat berikutnya. Pendekatan ini membuat BFS sangat efektif dalam menemukan jalur terpendek pada graf tak berbobot.

Mengapa BFS penting? Algoritma ini memiliki banyak aplikasi di berbagai bidang, termasuk sistem navigasi, kecerdasan buatan, pemrosesan gambar, hingga jaringan komputer. Bayangkan kamu sedang menggunakan Google Maps untuk menemukan rute tercepat dari rumah ke kantor. Begitu pula dalam game, misalnya saat karakter perlu menemukan jalan keluar dari labirin, BFS dapat digunakan untuk mencari solusi tercepat.

Struktur Data yang Digunakan

Untuk mengimplementasikan BFS, diperlukan struktur data berikut:

  • Queue (Antrian): Digunakan untuk menyimpan simpul yang akan dieksplorasi.
  • Visited List: Menandai simpul yang sudah dikunjungi agar tidak dikunjungi kembali.
  • Graph Representation: Bisa berupa adjacency list atau adjacency matrix.
Baca juga :   Algoritma RProp: Pengertian, Cara Kerja dan Implementasi

Perbedaan BFS dengan Algoritma Pencarian Lainnya

  • BFS vs DFS (Depth First Search): BFS menggunakan antrian (queue) sedangkan DFS menggunakan tumpukan (stack).
  • BFS vs Dijkstra: BFS efektif untuk graf tak berbobot, sementara Dijkstra digunakan untuk graf berbobot.
BFSDFS
Menggunakan antrianMenggunakan stack
Menjelajahi graf secara horizontalMenjelajahi graf secara vertikal
Cocok untuk jalur terpendekCocok untuk eksplorasi mendalam

Cara Kerja Algoritma Breadth First Search (BFS)

Algoritma Breadth First Search (BFS) bekerja dengan menelusuri setiap simpul dalam graf atau pohon secara berlapis-lapis, dimulai dari simpul awal, lalu mengunjungi semua simpul yang bertetangga sebelum berpindah ke tingkat berikutnya. BFS menggunakan struktur data antrian (queue) untuk memastikan eksplorasi dilakukan secara sistematis dari level ke level.

1. Langkah-langkah Implementasi BFS

Berikut adalah langkah-langkah yang dilakukan oleh BFS dalam menelusuri graf:

  1. Memulai dari simpul awal
    • Pilih simpul awal sebagai titik mulai pencarian.
    • Masukkan simpul ini ke dalam antrian (queue).
    • Tandai simpul ini sebagai sudah dikunjungi agar tidak dikunjungi kembali.
  2. Mengambil simpul dari antrian
    • Ambil simpul pertama dalam antrian.
    • Proses simpul ini (misalnya, mencetak atau menyimpan hasil eksplorasi).
  3. Menambahkan simpul tetangga yang belum dikunjungi
    • Temukan semua simpul yang bertetangga dengan simpul yang sedang diproses.
    • Jika simpul tetangga belum dikunjungi, tambahkan ke dalam antrian dan tandai sebagai sudah dikunjungi.
  4. Ulangi proses sampai antrian kosong
    • Lanjutkan mengambil simpul dari antrian dan mengulangi proses di atas sampai semua simpul yang dapat dijangkau sudah dikunjungi.

2. Ilustrasi Cara Kerja BFS dengan Contoh Graf

Misalkan kita memiliki graf tak berbobot berikut:

     A
    / \
   B   C
  / \   \
 D   E   F

Kita akan menjalankan BFS dari simpul A. Urutan eksplorasi adalah sebagai berikut:

  1. Mulai dari A, masukkan ke dalam antrian → Antrian: [A]
  2. Keluarkan A, kunjungi B dan C, masukkan ke antrian → Antrian: [B, C]
  3. Keluarkan B, kunjungi D dan E, masukkan ke antrian → Antrian: [C, D, E]
  4. Keluarkan C, kunjungi F, masukkan ke antrian → Antrian: [D, E, F]
  5. Keluarkan D → Antrian: [E, F]
  6. Keluarkan E → Antrian: [F]
  7. Keluarkan F → Antrian kosong, BFS selesai
Baca juga :   Graphical User Interface (GUI): Cara Kerja dan Kelebihan

Urutan hasil eksplorasi: A → B → C → D → E → F

3. Pseudocode Algoritma BFS

BFS(Graf, Simpul_Awal):
1. Buat antrian kosong dan tambahkan simpul awal ke antrian
2. Tandai simpul awal sebagai sudah dikunjungi
3. Selama antrian tidak kosong:
   a. Ambil simpul dari depan antrian
   b. Proses simpul tersebut (misalnya cetak simpul)
   c. Tambahkan semua simpul tetangga yang belum dikunjungi ke dalam antrian
   d. Tandai simpul-simpul tersebut sebagai sudah dikunjungi
4. Selesai

4. Implementasi Breadth First Search dalam Pemograman PHP

Kode:

<?php
// Fungsi BFS untuk menjelajahi graf
function bfs($graph, $start) {
    $queue = array($start); // Antrian BFS dimulai dari simpul awal
    $visited = array(); // Daftar simpul yang sudah dikunjungi

    while (!empty($queue)) {
        $node = array_shift($queue); // Mengambil elemen pertama dalam antrian
        if (!in_array($node, $visited)) {
            echo $node . " "; // Menampilkan simpul yang sedang dikunjungi
            $visited[] = $node; // Tandai sebagai dikunjungi
            
            // Menambahkan semua simpul bertetangga yang belum dikunjungi ke antrian
            foreach ($graph[$node] as $neighbor) {
                if (!in_array($neighbor, $visited)) {
                    array_push($queue, $neighbor);
                }
            }
        }
    }
}

// Representasi graf menggunakan adjacency list
$graph = array(
    'A' => array('B', 'C'),
    'B' => array('D', 'E'),
    'C' => array('F'),
    'D' => array(),
    'E' => array(),
    'F' => array()
);

// Memulai BFS dari simpul A
echo "Hasil eksplorasi BFS: ";
bfs($graph, 'A');
?>

Output:

Hasil eksplorasi BFS: A B C D E F

Penjelasan Kode:

  • Membuat daftar adjacency graf:
    Graf direpresentasikan menggunakan array asosiatif, di mana setiap simpul memiliki daftar simpul tetangga yang terhubung dengannya.
  • Menggunakan antrian (queue) untuk traversal BFS:
    BFS dimulai dengan memasukkan simpul awal ke dalam antrian, lalu memprosesnya satu per satu.
  • Menandai simpul yang sudah dikunjungi:
    Setiap simpul yang dikunjungi disimpan dalam array visited untuk menghindari kunjungan berulang.
  • Menambahkan simpul bertetangga ke dalam antrian:
    Jika simpul tetangga belum dikunjungi, maka dimasukkan ke dalam antrian untuk diproses berikutnya.
  • Menggunakan array_shift():
    Fungsi array_shift() digunakan untuk mengambil dan menghapus elemen pertama dalam antrian.
Baca juga :   Lighttpd Web Server Adalah: Kelebihan dan Konfigurasi

Kompleksitas Waktu dan Ruang BFS

FaktorAnalisis
Kompleksitas WaktuO(V + E) (V = jumlah simpul, E = jumlah sisi)
Kompleksitas RuangO(V) (karena menggunakan queue dan visited list)

Penjelasan:

  • BFS akan mengunjungi setiap simpul dan setiap sisi sekali, sehingga total waktu eksekusinya O(V + E).
  • BFS membutuhkan memori sebesar O(V) karena harus menyimpan antrian dan visited list.

Keuntungan dan Kelemahan BFS

Keuntungan

  • Menjamin jalur terpendek dalam graf tak berbobot.
  • Mudah diimplementasikan dengan struktur data antrian.
  • Sangat berguna dalam pencarian solusi optimal, misalnya dalam navigasi atau permainan puzzle.

Kelemahan

  • Memerlukan banyak memori karena harus menyimpan semua simpul dalam antrian.
  • Kurang efisien dibanding DFS untuk eksplorasi mendalam.

Kode PHP BFS untuk Mencari Jalur Terpendek

Jika kita ingin menemukan jalur terpendek dari satu simpul ke simpul lainnya dalam graf tak berbobot, kita bisa sedikit memodifikasi BFS dengan menggunakan array parent untuk melacak jalur.

Kode BFS untuk Mencari Jalur Terpendek dalam PHP

<?php
// Fungsi BFS untuk mencari jalur terpendek
function bfs_shortest_path($graph, $start, $goal) {
    $queue = array(array($start)); // Antrian berisi jalur yang sedang ditelusuri
    
    while (!empty($queue)) {
        $path = array_shift($queue); // Ambil jalur pertama dari antrian
        $node = end($path); // Ambil simpul terakhir dalam jalur
        
        if ($node == $goal) {
            return $path; // Jika sampai ke tujuan, kembalikan jalur yang ditemukan
        }
        
        foreach ($graph[$node] as $neighbor) {
            if (!in_array($neighbor, $path)) {
                $new_path = $path;
                $new_path[] = $neighbor;
                array_push($queue, $new_path);
            }
        }
    }
    return null; // Jika tidak ada jalur yang ditemukan
}

// Definisi graf
$graph = array(
    'A' => array('B', 'C'),
    'B' => array('D', 'E'),
    'C' => array('F'),
    'D' => array(),
    'E' => array(),
    'F' => array()
);

// Mencari jalur terpendek dari A ke F
$start = 'A';
$goal = 'F';
$shortest_path = bfs_shortest_path($graph, $start, $goal);

if ($shortest_path) {
    echo "Jalur terpendek dari $start ke $goal: " . implode(" → ", $shortest_path);
} else {
    echo "Tidak ada jalur yang ditemukan dari $start ke $goal";
}
?>

Output:

Jalur terpendek dari A ke F: A → C → F

Kesimpulan

Pada pembahasan kita diatas dapat kita simpulkan bahwa Algoritma Breadth First Search (BFS) adalah metode pencarian yang sangat efektif untuk traversal graf dan menemukan jalur terpendek dalam graf tak berbobot. BFS bekerja dengan menjelajahi simpul secara berlapis, menggunakan struktur data antrian (queue) untuk menjaga urutan eksplorasi.

Dengan kompleksitas waktu O(V + E) dan kompleksitas ruang O(V), BFS sangat cocok untuk berbagai aplikasi seperti sistem navigasi, pencarian solusi dalam game, hingga pemrosesan gambar.

Meskipun BFS membutuhkan lebih banyak memori dibandingkan DFS, algoritma ini tetap menjadi salah satu teknik pencarian paling fundamental dalam ilmu komputer dan pemrograman.

Artikel ini merupakan bagian dari seri artikel belajar Kecerdasan Buatan dan jika ada ide topik yang mau kita bahas silahkan komen di bawah ya.