Algoritma Breadth First Search (BFS) dengan CONTOH
Sarah Chen
⚡ Ringkasan Cerdas
Breadth First Search (BFS) adalah algoritma yang menelusuri graf level demi level, mengunjungi semua tetangga suatu node sebelum bergerak lebih dalam. Algoritma ini menggunakan antrian FIFO dan menemukan jalur terpendek pada graf tanpa bobot tanpa loop tak terbatas.
Apa itu Algoritma BFS (Breadth-First Search)?
Pencarian lebar pertama (BFS) adalah algoritma yang digunakan untuk memetakan data grafik atau mencari di dalam pohon atau menelusuri struktur. Bentuk lengkap dari 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
- Pada berbagai level data, Anda dapat menandai node mana pun sebagai node awal atau node pertama untuk memulai penelusuran. BFS akan mengunjungi node tersebut, menandainya sebagai telah dikunjungi, dan menempatkannya dalam antrian.
- Sekarang BFS akan mengunjungi node terdekat dan yang belum dikunjungi, lalu menandainya. Nilai-nilai ini juga ditambahkan ke antrian. Antrian bekerja berdasarkan... model FIFO.
- Dengan cara yang serupa, node terdekat yang belum dikunjungi pada graf dianalisis, ditandai, dan ditambahkan ke antrian. Item-item ini dihapus dari antrian saat diterima dan dicetak sebagai hasilnya.
Mengapa kita membutuhkan Algoritma BFS?
Ada banyak alasan untuk menggunakan Algoritma BFS untuk pencarian dalam 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 node yang berdekatan dengan verteks saat ini telah dikunjungi dan dilalui pada iterasi pertama. Metodologi antrian 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 Antrian BFS.
Langkah 3)
Mulailah 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 simpul yang tersisa pada grafik yang berdekatan dengan simpul V.
Langkah 6)
Untuk setiap simpul yang berdekatan, misalnya V1, jika belum dikunjungi, maka tambahkan V1 ke antrian BFS.
Langkah 7)
BFS akan mengunjungi V1, menandainya sebagai sudah dikunjungi, dan menghapusnya dari antrian.
Contoh Algoritma BFS
Langkah 1)
Anda memiliki grafik yang menampilkan tujuh angka mulai dari 0 hingga 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)
Node yang tersisa yang berdekatan dengan 0 dan belum dikunjungi akan 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 – First in First Out) struktur data digunakan oleh BFS.
- Anda menandai simpul mana pun dalam grafik sebagai akar dan mulai menelusuri data dari sana.
- BFS menelusuri semua node dalam grafik dan terus menghapus node yang tidak perlu.ping setelah selesai.
- BFS mengunjungi node berdekatan yang belum dikunjungi, menandainya sebagai selesai, dan memasukkannya ke dalam antrian.
- Fungsi ini menghapus simpul sebelumnya dari antrian jika tidak ditemukan simpul yang berdekatan.
- Algoritma BFS berulang hingga semua simpul dalam graf berhasil dilalui 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 rentang minimum untuk mengunjungi semua simpul grafik dalam waktu sesingkat mungkin dengan akurasi tinggi.
- Jaringan P2P: BFS dapat diimplementasikan untuk menemukan semua node terdekat atau tetangga 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.
