Algoritma Breadth First Search (BFS) dengan CONTOH

Apa itu Algoritma BFS (Breadth-First Search)?

Breadth-first search (BFS) adalah algoritma yang digunakan untuk membuat grafik data atau menelusuri pohon atau struktur yang melintasinya. Bentuk lengkap BFS adalah Breadth-first search.

Algoritme ini secara efisien mengunjungi dan menandai semua simpul kunci dalam grafik dengan cara yang akurat. Algoritme ini memilih satu simpul (titik awal atau titik sumber) dalam grafik dan kemudian mengunjungi semua simpul yang berdekatan dengan simpul yang dipilih. Ingat, BFS mengakses simpul-simpul ini satu per satu.

Setelah algoritme mengunjungi dan menandai simpul awal, ia bergerak menuju simpul terdekat yang belum dikunjungi dan menganalisisnya. Setelah dikunjungi, semua simpul ditandai. Iterasi ini berlanjut hingga semua simpul grafik berhasil dikunjungi dan ditandai.

Apa itu traversal Grafik?

Traversal graf adalah metodologi yang umum digunakan untuk menemukan posisi titik pada graf. Ini adalah algoritma pencarian lanjutan yang dapat menganalisis grafik dengan kecepatan dan presisi serta menandai urutan simpul yang dikunjungi. Proses ini memungkinkan Anda mengunjungi setiap node dalam grafik dengan cepat tanpa terkunci dalam loop tak terbatas.

Arsitektur algoritma BFS

1. Di berbagai level data, Anda dapat menandai node mana pun sebagai node awal atau awal untuk mulai melintasi. BFS akan mengunjungi node tersebut dan menandainya sebagai telah dikunjungi dan menempatkannya dalam antrian.
2. Sekarang BFS akan mengunjungi node terdekat dan yang belum dikunjungi dan menandainya. Nilai-nilai ini juga ditambahkan ke antrian. Antrean bekerja pada model FIFO.
3. Dengan cara yang sama, simpul terdekat dan yang belum dikunjungi pada grafik dianalisis, ditandai, dan ditambahkan ke antrean. Item ini dihapus dari antrean saat diterima dan dicetak sebagai hasilnya.

Mengapa kita membutuhkan Algoritma BFS?

Ada banyak alasan untuk menggunakan Algoritma BFS untuk mencari dataset Anda. Beberapa aspek terpenting yang menjadikan algoritma ini pilihan utama Anda adalah:

• BFS berguna untuk menganalisis node dalam grafik dan membangun jalur terpendek untuk melintasinya.
• BFS dapat melintasi grafik dengan jumlah iterasi terkecil.
• Arsitektur algoritma BFS sederhana dan kuat.
• Hasil algoritma BFS memiliki tingkat akurasi yang tinggi dibandingkan dengan algoritma lainnya.
• Iterasi BFS mulus, dan tidak ada kemungkinan algoritma ini terjebak dalam masalah loop tak terbatas.

Bagaimana Cara Kerja Algoritma BFS?

Penjelajahan grafik memerlukan algoritme untuk mengunjungi, memeriksa, dan/atau memperbarui setiap node yang belum dikunjungi dalam struktur mirip pohon. Penjelajahan grafik dikategorikan berdasarkan urutan kunjungannya ke node pada grafik.

Algoritma BFS memulai operasi dari simpul pertama atau simpul awal dalam grafik dan melintasinya secara menyeluruh. Setelah berhasil melintasi simpul awal, maka simpul berikutnya yang belum dilintasi dalam grafik akan dikunjungi dan ditandai.

Oleh karena itu, dapat dikatakan bahwa semua simpul yang berdekatan dengan simpul saat ini dikunjungi dan dilintasi pada iterasi pertama. Metodologi antrean sederhana digunakan untuk mengimplementasikan cara kerja algoritma BFS, dan terdiri dari langkah-langkah berikut:

Langkah 1)

Setiap titik atau simpul pada graf diketahui. Misalnya, Anda dapat menandai simpul sebagai V.

Langkah 2)

Jika simpul V tidak diakses maka tambahkan simpul V ke dalam Antrean BFS

Langkah 3)

Mulai pencarian BFS, dan setelah selesai, Tandai simpul V sebagai telah dikunjungi.

Langkah 4)

Antrian BFS masih belum kosong, maka simpul V dari graf tersebut dihilangkan dari antrian.

Langkah 5)

Ambil semua sisa simpul pada graf yang bertetangga dengan simpul V

Langkah 6)

Untuk setiap simpul yang berdekatan misalkan V1, jika belum dikunjungi maka tambahkan V1 ke antrian BFS

Langkah 7)

BFS akan mengunjungi V1 dan menandainya sebagai telah dikunjungi dan menghapusnya dari antrian.

Contoh Algoritma BFS

Langkah 1)

Anda memiliki grafik tujuh angka yang berkisar dari 0 – 6.

Langkah 2)

0 atau nol telah ditandai sebagai simpul akar.

Langkah 3)

0 dikunjungi, ditandai, dan dimasukkan ke dalam struktur data antrian.

Langkah 4)

Sisa 0 node yang berdekatan dan belum dikunjungi dikunjungi, ditandai, dan dimasukkan ke dalam antrian.

Langkah 5)

Perulangan traversing diulang sampai semua node dikunjungi.

Aturan Algoritma BFS

Berikut adalah aturan penting untuk menggunakan algoritma BFS:

• Antrian (FIFO-Pertama masuk Pertama Keluar) struktur data digunakan oleh BFS.
• Anda menandai node mana pun dalam grafik sebagai root dan mulai melintasi data dari node tersebut.
• BFS melintasi semua node dalam grafik dan terus menghapusnya setelah selesai.
• BFS mengunjungi node berdekatan yang belum dikunjungi, menandainya sebagai selesai, dan memasukkannya ke dalam antrian.
• Menghapus simpul sebelumnya dari antrian jika tidak ditemukan simpul yang berdekatan.
• Algoritma BFS melakukan iterasi hingga semua simpul pada grafik berhasil dilintasi dan ditandai sebagai selesai.
• Tidak ada loop yang disebabkan oleh BFS selama melintasi data dari node mana pun.

Penerapan Algoritma BFS

Mari kita lihat beberapa aplikasi kehidupan nyata di mana implementasi algoritma BFS bisa menjadi sangat efektif.

• Grafik Tidak Berbobot: Algoritma BFS dapat dengan mudah membuat jalur terpendek dan pohon merentang minimum untuk mengunjungi semua simpul pada grafik dalam waktu sesingkat mungkin dengan akurasi tinggi.
• Jaringan P2P: BFS dapat diimplementasikan untuk menemukan semua node terdekat atau bertetangga dalam jaringan peer-to-peer. Ini akan menemukan data yang dibutuhkan lebih cepat.
• Perayap Web: Mesin pencari atau perayap web dapat dengan mudah membuat berbagai tingkat indeks dengan menggunakan BFS. Implementasi BFS dimulai dari sumbernya yaitu halaman web, kemudian mengunjungi semua link dari sumber tersebut.
• Sistem Navigasi: BFS dapat membantu menemukan semua lokasi tetangga dari lokasi utama atau sumber.
• Penyiaran Jaringan: Paket yang disiarkan dipandu oleh algoritma BFS untuk menemukan dan menjangkau semua node yang alamatnya dimilikinya.

Kesimpulan

• Penjelajahan grafik adalah proses unik yang memerlukan algoritme untuk mengunjungi, memeriksa, dan/atau memperbarui setiap node yang belum dikunjungi dalam struktur mirip pohon. Algoritma BFS bekerja dengan prinsip serupa.
• Algoritme ini berguna untuk menganalisis node dalam grafik dan membangun jalur terpendek untuk melintasinya.
• Algoritme melintasi grafik dengan jumlah iterasi terkecil dan waktu sesingkat mungkin.
• BFS memilih satu node (titik awal atau sumber) dalam grafik dan kemudian mengunjungi semua node yang berdekatan dengan node yang dipilih. BFS mengakses node ini satu per satu.
• Data yang dikunjungi dan ditandai ditempatkan dalam antrian oleh BFS. Antrian bekerja berdasarkan prinsip masuk pertama keluar. Oleh karena itu, elemen yang ditempatkan pada grafik terlebih dahulu dihapus terlebih dahulu dan sebagai hasilnya dicetak.
• Algoritma BFS tidak akan pernah terjebak dalam loop tak terbatas.
• Karena presisi tinggi dan implementasi yang kuat, BFS digunakan dalam berbagai solusi kehidupan nyata seperti jaringan P2P, Web Crawler, dan Network Broadcasting.