Apakah Algoritma BFS (Breadth-First Search)?
Breadth-first search (BFS) adalah algoritma yang digunakan untuk membuat grafik data atau mencari struktur pokok atau melintasi. Bentuk lengkap BFS adalah carian pertama-lebar.
Algoritma dengan cekap mengunjungi dan menandai semua nod utama dalam grafik dengan cara tepat. Algoritma ini memilih simpul tunggal (titik awal atau sumber) dalam grafik dan kemudian melawat semua nod yang berdekatan dengan nod yang dipilih. Ingat, BFS mengakses nod ini satu persatu.
Setelah algoritma melawat dan menandakan nod permulaan, maka ia bergerak ke arah nod yang tidak dilawati terdekat dan menganalisisnya. Setelah dikunjungi, semua nod ditandakan. Iterasi ini berterusan sehingga semua nod grafik berjaya dilayari dan ditandai.
Dalam tutorial Algoritma ini, anda akan belajar:
- Apakah Algoritma BFS (Breadth-First Search)?
- Apa itu Graf traversal?
- Senibina algoritma BFS
- Mengapa kita memerlukan Algoritma BFS?
- Bagaimana Algoritma BFS Berfungsi?
- Contoh Algoritma BFS
- Peraturan Algoritma BFS
- Aplikasi Algoritma BFS
Apa itu Graf traversal?
Melintasi grafik adalah metodologi yang biasa digunakan untuk mencari kedudukan bucu dalam grafik. Ini adalah algoritma carian lanjutan yang dapat menganalisis grafik dengan kelajuan dan ketepatan bersama dengan menandakan urutan bucu yang dikunjungi. Proses ini membolehkan anda dengan cepat mengunjungi setiap simpul dalam grafik tanpa terkunci dalam gelung tanpa batas.
Senibina algoritma BFS
- Dalam pelbagai tahap data, anda boleh menandakan sebarang simpul sebagai simpul permulaan atau awal untuk mula melintasi. BFS akan mengunjungi nod dan menandainya sebagai dikunjungi dan meletakkannya dalam barisan.
- Sekarang BFS akan mengunjungi nod terdekat dan tidak dikunjungi dan menandakannya. Nilai-nilai ini juga ditambahkan ke dalam barisan. Antrian berfungsi pada model FIFO.
- Dengan cara yang serupa, node yang terdekat dan tidak dikunjungi pada grafik dianalisis ditandakan dan ditambahkan ke dalam barisan. Item-item ini dihapus dari barisan sebagai penerimaan dan dicetak sebagai hasilnya.
Mengapa kita memerlukan Algoritma BFS?
Terdapat banyak sebab untuk menggunakan Algoritma BFS untuk digunakan sebagai mencari set data anda. Beberapa aspek yang paling penting yang menjadikan algoritma ini menjadi pilihan pertama anda adalah:
- BFS berguna untuk menganalisis nod dalam grafik dan membina jalan terpendek melintasi ini.
- BFS dapat melintasi grafik dalam bilangan lelaran terkecil.
- Senibina algoritma BFS ringkas dan mantap.
- Hasil algoritma BFS mempunyai tahap ketepatan yang tinggi berbanding dengan algoritma lain.
- Pengulangan BFS lancar, dan tidak mungkin algoritma ini terjebak dalam masalah gelung tak terhingga.
Bagaimana Algoritma BFS Berfungsi?
Graf traversal memerlukan algoritma untuk melawat, memeriksa, dan / atau mengemas kini setiap nod yang tidak dikunjungi dalam struktur seperti pokok. Pelayaran grafik dikategorikan mengikut urutan di mana mereka mengunjungi nod pada grafik.
Algoritma BFS memulakan operasi dari nod pertama atau permulaan dalam graf dan melintasi secara menyeluruh. Setelah berjaya melintasi simpul awal, maka titik yang tidak dilalui seterusnya dalam grafik dikunjungi dan ditandakan.
Oleh itu, anda boleh mengatakan bahawa semua nod yang berdekatan dengan bucu semasa dikunjungi dan dilalui pada lelaran pertama. Metodologi antrian mudah digunakan untuk melaksanakan kerja algoritma BFS, dan terdiri daripada langkah-langkah berikut:
Langkah 1)
Setiap bucu atau simpul dalam grafik diketahui. Contohnya, anda boleh menandakan simpul sebagai V.
Langkah 2)
Sekiranya bucu V tidak diakses maka tambahkan bucu V ke dalam Antrian BFS
Langkah 3)
Mulakan carian BFS, dan setelah selesai, Tandakan bucu V seperti yang dikunjungi.
Langkah 4)
Antrian BFS masih tidak kosong, oleh itu keluarkan bucu graf V dari barisan.
Langkah 5)
Dapatkan semua baki baki pada graf yang bersebelahan dengan bucu V
Langkah 6)
Untuk setiap bucu bersebelahan katakan V1, sekiranya belum dikunjungi maka tambahkan V1 ke barisan BFS
Langkah 7)
BFS akan melawat V1 dan menandainya sebagai dikunjungi dan menghapusnya dari barisan.
Contoh Algoritma BFS
Langkah 1)
Anda mempunyai graf tujuh nombor antara 0 - 6.
Langkah 2)
0 atau sifar telah ditandakan sebagai nod akar.
Langkah 3)
0 dikunjungi, ditandai, dan dimasukkan ke dalam struktur data antrian.
Langkah 4)
Sisa 0 nod bersebelahan dan tidak dilawati dikunjungi, ditandakan, dan dimasukkan ke dalam barisan.
Langkah 5)
Pengulangan melintasi diulang sehingga semua nod dikunjungi.
Peraturan Algoritma BFS
Berikut adalah peraturan penting untuk menggunakan algoritma BFS:
- Struktur data antrian (FIFO-First in First Out) digunakan oleh BFS.
- Anda menandakan sebarang nod dalam grafik sebagai root dan mula melintasi data darinya.
- BFS melintasi semua nod dalam grafik dan terus menjatuhkannya setelah selesai.
- BFS mengunjungi nod yang tidak dikunjungi bersebelahan, menandainya sebagai selesai, dan memasukkannya ke dalam barisan.
- Mengeluarkan bucu sebelumnya dari barisan sekiranya tiada bucu bersebelahan dijumpai.
- Algoritma BFS berulang sehingga semua bucu dalam grafik berjaya dilalui dan ditandakan sebagai selesai.
- Tidak ada gelung yang disebabkan oleh BFS semasa melintasi data dari sebarang nod.
Aplikasi Algoritma BFS
Mari kita lihat beberapa aplikasi kehidupan sebenar di mana pelaksanaan algoritma BFS boleh menjadi sangat berkesan.
- Grafik Tidak Berat: Algoritma BFS dapat dengan mudah membuat jalan terpendek dan pokok rentang minimum untuk mengunjungi semua bucu grafik dalam masa sesingkat mungkin dengan ketepatan tinggi.
- Rangkaian P2P: BFS dapat dilaksanakan untuk mencari semua nod terdekat atau berdekatan dalam rangkaian peer to peer. Ini akan menemui data yang diperlukan dengan lebih pantas.
- Perayap Web: Mesin carian atau perayap web dapat membina pelbagai peringkat indeks dengan mudah menggunakan BFS. Pelaksanaan BFS bermula dari sumber, yang merupakan halaman web, dan kemudian ia mengunjungi semua pautan dari sumber tersebut.
- Sistem Navigasi: BFS dapat membantu mencari semua lokasi yang berdekatan dari lokasi utama atau sumber.
- Penyiaran Rangkaian: Paket yang disiarkan dipandu oleh algoritma BFS untuk mencari dan menjangkau semua nod yang mempunyai alamatnya.
Ringkasan
- Melintasi grafik adalah proses unik yang memerlukan algoritma untuk melawat, memeriksa, dan / atau mengemas kini setiap simpul yang tidak dikunjungi dalam struktur seperti pohon. Algoritma BFS berfungsi berdasarkan prinsip yang serupa.
- Algoritma ini berguna untuk menganalisis nod dalam grafik dan membina jalan terpendek melintasi ini.
- Algoritma melintasi grafik dalam bilangan lelaran terkecil dan masa sesingkat mungkin.
- BFS memilih nod tunggal (titik awal atau sumber) dalam grafik dan kemudian melawat semua nod yang berdekatan dengan nod yang dipilih. BFS mengakses nod ini satu persatu.
- Data yang dilawati dan ditandai diletakkan dalam barisan oleh BFS. Antrian berfungsi berdasarkan asas pertama dalam keluar. Oleh itu, elemen yang diletakkan dalam grafik terlebih dahulu dihapuskan terlebih dahulu dan dicetak sebagai hasilnya.
- Algoritma BFS tidak akan terperangkap dalam gelung tanpa batas.
- Kerana ketepatan tinggi dan pelaksanaan yang mantap, BFS digunakan dalam pelbagai penyelesaian kehidupan nyata seperti rangkaian P2P, Perayap Web, dan Penyiaran Rangkaian.