BFS (Breadth First Search) : Pengertian, Kekurangan, Kelebihan, dan Contohnya

 

Assalamualaikum Warahmatullahi Wabrokatuh.

Halo teman-teman, bagaimana kabarnya hari ini? Semoga kalian semua berada dalam keadaan sehat walafiyat. Bagi yang sedang sakit, semangat yaa. Semoga Allah mengampuni dosa kalian lewat sakit itu. Semoga cepat sembuh.

Kali ini kita akan membahas tentang BFS (Breadth First Search). Berikut ini adalah beberapa uraian mengenai algoritma BFS.

BFS (Breadth First Search) : Pengertian, Kekurangan, Kelebihan, dan Contohnya

1. Pengertian BFS

    Algoritma Breadth First Search adalah algoritma pencarian melebar yang dilakukan dengan mengunjungi node pada level n terlebih dahulu sebelum mengunjungi node-node pada level n+1. Algoritma BFS berbeda dengan DFS. Hal itu dapat dilihat pada gambar dibawah ini. Untuk penjelasan algoritma DFS akan dijelaskan di postingan selanjutnya.

Gambar 1. DFS dan BFS

   

 Cara kerja algoritma Breadth First Search yaitu masukkan simpul ujung ke dalam sebuah antrean kemudian ambil simpul dari awal antrean. Lakukan pengecekan apakah simpul awal merupakan solusi. Jika simpul merupakan solusi pencarian selesai dan hasil dikembalikan. Jika simpul bukan merupakan solusi, masukan seluruh simpul yang bertetangga dengan simpul tersebut. Apabila semua simpul sudah dicek dan antrean kosong, pencarian selesai dengan mengembalikan hasil solusi tidak ditemukan. Pencarian diulang dari simpul awal antrean.

2. Kelebihan dan Kekurangan BFS

Kelebihan BFS	Kekurangan BFS
Tidak akan menemui jalan buntu.	Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon.
Jika ada satu solusi, maka BFS akan menemukannya. Dan jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.	Membutuhkan waktu yang cukup lama, karena akan menguji n level untuk mendapatkan solusi pada level ke-(n+1).

3. Contoh Penerapan BFS dalam Studi Kasus

Pencarian jarak terdekat Arad-Bucharest. Berikut ini adalah Peta Rumania.

Gambar 2. Peta Rumania

      Dalam menyelesaikan kasus diatas, kita perlu membuat peta Rumania menjadi gambaran graph yang lebih sederhana. Berikut ini adalah gambaran peta Rumania dalam bentuk graph sederhana:

Gambar 3. Graph Peta Rumania

Penyelesaian dengan BFS:

    Algoritma Breadth First Search adalah algoritma pencarian melebar yang dilakukan dengan mengunjungi node pada level n terlebih dahulu sebelum mengunjungi node-node pada level n+1. Dalam penyelesaian kasus diatas, kita dapat menggambarkan graph diatas ke dalam bentuk Tree. Node paling kiri dimulai dari jarak tetangga terdekat yaitu Z (75) lalu berurutan ke S dan T.

Gambar 4. Tree untuk BFS

Pada tree, tidak semua kota saya tuliskan. Contohnya yaitu kota D. Hal itu dikarenakan kota D tidak termasuk dalam perhitungan, dan berada di level 4. Berikut ini adalah gambaran penyelesaian pencarian kota Bucharest (B) menggunakan algoritma BFS.
Implementasi: Start (A), Goal (B)

Gambar 5. Pencarian Jarak dengan BFS

Penjelasan:

        Pencarian rute dengan BFS, yaitu dengan mengecek setiap level mulai dari level n atau level 1, baru dilanjutkan ke level n+1 hingga target atau goalnya ditemukan. Meski demikian, yang dihitung pada akhirnya bukanlah jarak yang ditempuh selama mencari target, namun rute yang dipilih adalah rute yang terhubung ke target (yaitu A S F B). Oleh karena itu, BFS membutuhkan banyak memori untuk menyimpan semua simpul dalam satu pohon dan ini menjadi salah satu kekurangan BFS.

        Dari hasil pencarian diatas, maka ditemukan jarak yang dipilih dari Arad ke Bucharest dengan menggunakan algoritma BFS adalah sebagai berikut:

Gambar 6. Hasil Pencarian

Path = A > S > F >  B
Path-cost = 140 + 99 + 211 = 450 KM

Itu tadi penjelasan seputar algoritma BFS dan contoh penyelesaian kasus yang pernah saya kerjakan dalam tugas kuliah. Mohon maaf jika ada kekurangan dan kekeliruan. Semoga bermanfaat!

Wassalamualaikum Warahmatullahi Wabarokatuh.