Apa itu Algoritma BFS (Breadth-First Search)?
Breadth-first search (BFS) adalah algoritma yang digunakan untuk membuat grafik data atau mencari struktur pohon atau melintasi. Bentuk lengkap BFS adalah pencarian Breadth-first.
Algoritme secara efisien mengunjungi dan menandai semua node kunci dalam grafik dengan cara yang akurat secara luas. Algoritme ini memilih satu node (titik awal atau sumber) dalam grafik dan kemudian mengunjungi semua node yang berdekatan dengan node yang dipilih. Ingat, BFS mengakses node ini satu per satu.
Setelah algoritme mengunjungi dan menandai node awal, lalu algoritme bergerak menuju node terdekat yang belum dikunjungi dan menganalisisnya. Setelah dikunjungi, semua node ditandai. Iterasi ini berlanjut hingga semua node dari grafik telah berhasil dikunjungi dan ditandai.
Dalam tutorial Algoritma ini, Anda akan mempelajari:
- Apa itu Algoritma BFS (Breadth-First Search)?
- Apa itu Graph traversals?
- Arsitektur algoritma BFS
- Mengapa kita membutuhkan Algoritma BFS?
- Bagaimana Algoritma BFS Bekerja?
- Contoh Algoritma BFS
- Aturan Algoritma BFS
- Aplikasi Algoritma BFS
Apa itu Graph traversals?
Traversal grafik adalah metodologi yang umum digunakan untuk menemukan posisi puncak dalam grafik. Ini adalah algoritma pencarian lanjutan yang dapat menganalisis grafik dengan kecepatan dan presisi bersama dengan menandai urutan simpul yang dikunjungi. Proses ini memungkinkan Anda untuk mengunjungi setiap node dengan cepat dalam grafik tanpa terkunci dalam loop tak terbatas.
Arsitektur algoritma BFS
- Di berbagai level data, Anda dapat menandai node mana pun sebagai node awal atau awal untuk mulai melakukan traverse. BFS akan mengunjungi node dan menandainya sebagai telah dikunjungi dan menempatkannya dalam antrian.
- Sekarang BFS akan mengunjungi node terdekat dan yang tidak dikunjungi dan menandainya. Nilai-nilai ini juga ditambahkan ke antrian. Antrian bekerja pada model FIFO.
- Dengan cara yang sama, node terdekat dan yang belum dikunjungi pada grafik dianalisis dengan ditandai dan ditambahkan ke antrian. Item ini dihapus dari antrian saat diterima dan dicetak sebagai hasilnya.
Mengapa kita membutuhkan Algoritma BFS?
Ada banyak alasan untuk menggunakan Algoritma BFS untuk digunakan sebagai pencarian dataset Anda. Beberapa aspek terpenting yang menjadikan algoritme ini pilihan pertama Anda adalah:
- BFS berguna untuk menganalisis node dalam grafik dan membangun jalur terpendek untuk melintasi ini.
- BFS dapat melintasi grafik dalam jumlah iterasi terkecil.
- Arsitektur algoritma BFS sederhana dan kuat.
- Hasil dari algoritma BFS memiliki tingkat akurasi yang tinggi dibandingkan dengan algoritma lainnya.
- Iterasi BFS berjalan mulus, dan tidak ada kemungkinan algoritme ini terjebak dalam masalah loop tak terbatas.
Bagaimana Algoritma BFS Bekerja?
Graph traversal membutuhkan algoritme untuk mengunjungi, memeriksa, dan / atau memperbarui setiap node yang tidak dikunjungi dalam struktur seperti pohon. Traversal grafik dikategorikan berdasarkan urutan kunjungannya ke node pada grafik.
Algoritme BFS memulai operasi dari node pertama atau awal dalam grafik dan menjelajahinya secara menyeluruh. Setelah berhasil melintasi simpul awal, simpul berikutnya yang tidak dilintasi dalam grafik dikunjungi dan ditandai.
Oleh karena itu, Anda dapat mengatakan bahwa semua node yang berdekatan dengan simpul saat ini dikunjungi dan dilintasi pada iterasi pertama. Metodologi antrian sederhana digunakan untuk mengimplementasikan kerja algoritma BFS, dan terdiri dari langkah-langkah berikut:
Langkah 1)
Setiap simpul atau simpul dalam grafik diketahui. Misalnya, Anda dapat menandai node sebagai V.
Langkah 2)
Jika simpul V tidak diakses, tambahkan simpul V ke dalam Antrian BFS
Langkah 3)
Mulai pencarian BFS, dan setelah selesai, Tandai simpul V sebagai telah dikunjungi.
Langkah 4)
Antrian BFS masih tidak kosong, oleh karena itu hapus simpul V dari grafik dari antrian.
Langkah 5)
Ambil kembali semua simpul yang tersisa pada grafik yang berdekatan dengan simpul V.
Langkah 6)
Untuk setiap simpul yang berdekatan katakanlah V1, jika itu belum dikunjungi, 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 mulai 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)
Iterasi traverse diulang sampai semua node dikunjungi.
Aturan Algoritma BFS
Berikut adalah aturan penting untuk menggunakan algoritma BFS:
- Struktur data antrian (FIFO-First in First Out) digunakan oleh BFS.
- Anda menandai node mana pun dalam grafik sebagai root dan mulai melintasi datanya.
- BFS melintasi semua node dalam grafik dan terus menghapusnya setelah selesai.
- BFS mengunjungi node yang belum dikunjungi, menandainya sebagai selesai, dan memasukkannya ke dalam antrian.
- Menghapus simpul sebelumnya dari antrian jika tidak ada simpul yang berdekatan ditemukan.
- Algoritma BFS melakukan iterasi hingga semua simpul pada grafik berhasil dilintasi dan ditandai sebagai selesai.
- Tidak ada loop yang disebabkan oleh BFS selama traverse data dari node mana pun.
Aplikasi Algoritma BFS
Mari kita lihat beberapa aplikasi kehidupan nyata di mana implementasi algoritma BFS bisa 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 telusur atau perayap web dapat dengan mudah membuat beberapa tingkat indeks dengan menggunakan BFS. Implementasi BFS dimulai dari sumber, yaitu halaman web, dan 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 algoritme BFS untuk menemukan dan menjangkau semua node yang memiliki alamatnya.
Ringkasan
- Penjelajahan grafik adalah proses unik yang memerlukan algoritme untuk mengunjungi, memeriksa, dan / atau memperbarui setiap node yang tidak dikunjungi dalam struktur seperti pohon. Algoritma BFS bekerja dengan prinsip yang sama.
- Algoritme ini berguna untuk menganalisis node dalam grafik dan membangun jalur terpendek untuk melewatinya.
- Algoritme melintasi grafik dalam 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 dengan basis first in first out. Oleh karena itu, elemen yang ditempatkan di grafik terlebih dahulu dihapus terlebih dahulu dan dicetak sebagai hasilnya.
- Algoritma BFS tidak pernah bisa terjebak dalam loop tak terbatas.
- Karena presisi tinggi dan implementasi yang kuat, BFS digunakan dalam berbagai solusi kehidupan nyata seperti jaringan P2P, Perayap Web, dan Penyiaran Jaringan.