Metode breadth first search (BFS)

LancangKuning.com - BFS merupakan contoh dari algoritma pencarian. Algoritma pencarian pada ilmu komputer yaitu algoritma yang menerima input berupa masalah, lalu menghasilkan solusi dari masalah. Setelah menghasilkan beberapa solusi, maka solusi akan dikumpulkan lalu dibentuk menjadi sebuah himpunan. Ruang pencarian adalah himpunan kemungkinan semua solusi yang ada untuk menyelesaikan masalah.

Untuk melintasi grafik simpul (node) pada pohon pencarian kita dapat menggunakan banyak metode. Melintasi grafik artinya memeriksa semua node-node dari grafik. Metode breadth first search grafik transversal yang mulai melintasi grafik dari root node dan mengeksplorasi semua node tetangga. Kemudian memilih simpul terdekat dan menjelajahi semuanya yang belum  dijelajahi.

Algoritma mengikuti proses sama untuk setiap node yang paling dekat hingga menemukan tujuan. Algoritma BFS bekerja dimulai dengan memeriksa simpul A dan semua simpul tetangganya. Lalu langkah selanjutnya, tetangga dari simpul terdekat A di eksplorasi dan proses berlanjut pada langkah selanjutnya, algoritma ini menjelajahi semua tetangga dari semua node dan memastikan bahwa setiap node dikunjungi tepat satu kali dan tidak ada node yang dikunjungi dua kali. Mari kita lihat cara kerja algoritma BFS.

Baca juga : Tempat Wisata di Riau

1. Simpul ujung (akar) masukkan dalam antrian
2. Lakukan pengecekan apakah simpul merupakan solusi setelah mengambil simpul awal antrian.
3. Setelah dicek dan hasilnya bukan solusi maka simpul yang bertetangga dengan simpul tersebut masukkan dalam antrian
4. Hasil solusi tidak ditemukan jika antrian kosong dan setiap simpul sudah dicek saat melakukan pencarian

Jarak antar node dilayer 1 relatif lebih rendah daripada jarak antara node dilayer 2. Maka dari itu, pada BFS semua node dilayer 1 harus dilintasi sebelum pindah ke node dilayer 2

Grafik dapat berisi siklus, yang bisa membawa pencarian ke simpul yang sama lagi saat melintasi grafik. Untuk menghindari melakukan pemrosesan node yang sama lagi, maka harus menggunakan array Boolean yang menandai node setelah diproses. Saat mengunjungi node-node pada layer grafik, node-node itu akan disimpan sehingga bisa melintasi node child (anak simpul) yang bersesuaian dalam urutan yang sama.

Baca juga : Metode Simple Hill Climbing

Perhatikan gambar diatas, untuk melintasinya mulailah dari 0 dan kunjungi node child 1,2 dan 3. Lalu simpanlah sesuai urutan yang telah dikunjungi. Selanjutnya melakukan proses pencarian dengan mengunjungi node child dari 1 yaitu 4 dan 5, kemudian dari 2 yaitu 6 dan 7, kemudian 3 yaitu 7.  Untuk mempermudah gunakan antrian untuk menyimpan node dan menandainya sebagai “telah dikunjungi” sampai semua simpul yang terhubung langsung dengannya (tetangganya) telah ditandai. Antrian mengikuti metode firt in first out (FIFO). Artinya node yang dimasukkan pertama akan dikunjungi terlebih dahulu.

Aplikasi Algoritma BFS

Pencarian pada BFS metode grafik traversal sederhana yang memiliki jarak aplikasi yang tidak terduga. Berikut ini beberapa cara menarik yang digunakan BFS

• Crawlers in Search Engines: pencarian BFS adalah salah satu algoritma utama yang digunakan untuk mengindeks halaman web. Algoritma mulai melintasi dari halaman sumber dan mengikuti semua tautan yang terkait dengan halaman tersebut. Pada aplikasi ini simpul grafiknya adalah halaman pada web.
• GPS Navigation systems: pencarian BFS adalah salah satu algoritma terbaik yang digunakan untuk menemukan lokasi tetangga dengan menggunakan sistem  GPS

Baca juga : Tempat Wisata di Pekanbaru

• Broadcasting : jaringan memanfaatkan yang biasanya kita disebut sebagai paket untuk komunukasi. Paket-paket ini mengikuti metode traversal untuk mencapai berbagai node jaringan. BFS merupakan sebuah metode yang umum dan sering digunakan. Ini digunakan sebagai algoritma yang digunakan untuk mengkomunikasikan paket yang disiarkan disemua node dalam jaringan
• Peer to peer networking : BFS dapat digunakan sebagai metode traversal untuk menemukan semua node yang berdekatan dalam jaringan ini.(Eka)