Algoritma Pencarian Pertama Luas: Ikhtisar, Pentingnya & Aplikasi

Grafik ada di sekitar kita. Graf dapat dianggap sebagai jaringan simpul dan tepi yang saling berhubungan. Teman-teman Anda di Facebook, koneksi Anda di LinkedIn, atau pengikut Twitter/Instagram Anda merupakan grafik sosial Anda. Demikian pula, jika Anda ingin pergi dari titik A ke titik B, Anda dapat melakukannya melalui beberapa rute, yang dapat divisualisasikan di Google Maps.

Semua pilihan rute ganda dari titik A ke titik B juga merupakan grafik. Grafik adalah salah satu struktur data paling umum yang kita temui di dunia akademis dan dunia nyata karena grafik ada di mana-mana. Dan salah satu operasi yang paling sering dilakukan pada graf adalah traversal graf.

Apa itu Graf Traversal?

Graph Traversal adalah metode mengunjungi setiap node dalam graf tepat satu kali dengan kecepatan dan presisi. Ini adalah algoritma pencarian grafik canggih yang memungkinkan Anda untuk mencetak urutan node yang dikunjungi tanpa terjebak dalam loop tak terbatas. Ada banyak algoritma traversal graf seperti Depth-First Search , Breadth-First Search , Djikstra's Algorithm , A-Star Algorithm , dan banyak lagi.

Artikel ini akan membahas lebih dalam tentang Breadth First Search Algorithm atau BFS.

Struktur Grafik

Sebelum kita melihat secara rinci di bawah kap BFS, mari kita mengenal beberapa istilah grafik dengan bantuan grafik di atas:

Root Node – Node tempat Anda memulai proses traversal. Untuk mempermudah, kita dapat menganggap A sebagai simpul akar.

Levels – Level adalah kumpulan semua node yang berjarak sama dari node root. Jadi jika kita menganggap node A berada di Level 0, node B dan C berada di Level 1, sedangkan node D, E, dan F berada di level 2. Heuristik sederhana untuk menentukan jumlah level sebuah node adalah dengan menghitung jumlahnya tepi antara simpul tersebut dan simpul akar. Perhatikan bahwa ini hanya berfungsi jika Anda menentukan simpul akar berada di Level 0.

Parent Node – Sebuah node induk node adalah salah satu yang satu tingkat di atasnya dan berdekatan dengannya. Itu dapat dianggap sebagai simpul dari mana simpul tersebut berasal. A adalah simpul induk dari B dan C.

Child / Children Node – Node yang bercabang dan berdekatan dengan parent node. B dan C adalah simpul anak dari A

Baca: 10 Teknik Visualisasi Data Teratas

BFS adalah algoritma traversal grafik untuk menjelajahi pohon atau grafik secara efisien. Algoritme dimulai dengan node awal (root node) dan kemudian melanjutkan untuk menjelajahi semua node yang berdekatan dengannya, dengan cara yang lebih luas-pertama, yang bertentangan dengan depth-first, yang turun ke cabang tertentu sampai semua node di cabang itu dikunjungi. Sederhananya, ia melintasi grafik level-bijaksana, tidak bergerak ke bawah sampai semua node di level itu dikunjungi dan ditandai.

Ini beroperasi pada prinsip first-in-first-out (FIFO), dan diimplementasikan menggunakan struktur data antrian. Setelah sebuah node dikunjungi, itu dimasukkan ke dalam antrian. Kemudian dicatat dan semua node anak-anaknya dimasukkan ke dalam antrian. Proses ini berlangsung sampai semua node dalam grafik dikunjungi dan dicatat.

Mari kita lihat operasi antrian rinci untuk algoritma BFS untuk grafik yang diberikan di atas:

() – menunjukkan antrian

[] – menunjukkan hasil cetak

1. Masukkan A ke dalam antrian (a)
2. Cetak A, masukkan B dan C ke dalam antrian (cb)[a]
3. Cetak B, masukkan node anak D dan E ke dalam antrian (edc)[ba]
4. Cetak C, masukkan simpul anaknya F ke dalam antrian (makan)[cba]
5. Cetak D, masukkan simpul anaknya ke dalam antrian. Tidak ada. (fe)[dcba]
6. Cetak E, yang simpul anaknya F telah dimasukkan ke dalam antrian. (f)[edcba]
7. Cetak F. [fedcba]

Apa yang Membuat Algoritma BFS Penting

Ada banyak sekali alasan untuk menggunakan BFS sebagai metode untuk menelusuri kumpulan data yang luas dengan cepat. Beberapa fitur menonjol yang menjadikannya pilihan utama bagi pengembang dan insinyur data adalah:

• BFS dapat secara efektif menjelajahi semua node dalam grafik dan menemukan jalur sesingkat mungkin untuk menjelajahi semuanya.
• Jumlah iterasi yang diperlukan untuk melintasi seluruh grafik lebih sedikit daripada algoritma pencarian lainnya.
• Karena diimplementasikan menggunakan antrian, arsitekturnya kuat, andal, dan elegan.
• Dibandingkan dengan algoritma lain, output BFS tepat dan bebas kesalahan.
• Iterasi BFS berjalan lancar, tanpa risiko terjebak dalam infinite loop.

Checkout: Proyek Visualisasi Data yang Dapat Anda Replikasi

Aplikasi Algoritma BFS

Karena kesederhanaan dan kemudahan pengaturannya, algoritma BFS telah digunakan secara luas di berbagai situasi dunia nyata utama. Mari kita lihat beberapa aplikasi yang menonjol:

Perayap Mesin Pencari – Coba bayangkan dunia tanpa Google atau Bing. Anda tidak bisa. Mesin pencari adalah tulang punggung internet. Dan algoritma BFS adalah tulang punggung mesin pencari. Ini adalah algoritma utama yang digunakan untuk mengindeks halaman web. Algoritme memulai perjalanannya dari halaman sumber (simpul akar) dan kemudian mengikuti semua tautan pada halaman sumber itu secara luas. Setiap halaman web dapat dianggap sebagai simpul independen dalam grafik.

Traversal Graf Tidak Berbobot – BFS dapat mengidentifikasi jalur terpendek dan pohon merentang minimum dalam graf tidak berbobot. Menemukan rute terpendek hanyalah tentang menemukan jalur dengan jumlah tepi paling sedikit, yang cocok untuk BFS. Itu bisa menyelesaikan pekerjaan dengan mengunjungi paling sedikit node.

Navigasi GPS – BFS memanfaatkan sistem GPS untuk memunculkan semua kemungkinan lokasi tetangga dari titik awal Anda, membantu Anda menavigasi dari titik A ke B dengan mulus.

Penyiaran – Jaringan siaran menggunakan paket sebagai unit untuk membawa sinyal dan data. Algoritma BFS mengarahkan paket-paket ini untuk menuju ke semua node di jaringan yang seharusnya mereka jangkau.

Jaringan P2P – Torrent atau jaringan berbagi file lainnya bergantung pada komunikasi P2P. BFS bekerja sangat baik untuk menemukan node terdekat sehingga transfer data dapat terjadi lebih cepat.

Baca Juga: Manfaat Visualisasi Data

Kesimpulan

Ergo, Breadth First Search Algorithm adalah salah satu algoritma terpenting dari internet modern. Mudah-mudahan, blog ini akan berfungsi sebagai titik awal yang berguna dalam eksplorasi algoritma pencarian Anda.

Kami menyarankan Anda untuk memilih PG Diploma dalam Ilmu Data yang ditawarkan oleh IIIT Bangalore yang dihosting di upGrad karena di sini Anda bisa mendapatkan pertanyaan 1-1 dengan instruktur kursus. Ini tidak hanya berfokus pada pembelajaran teoretis tetapi juga memberikan pentingnya pengetahuan berbasis praktis, yang penting untuk menyiapkan pelajar untuk menghadapi proyek dunia nyata dan memberi Anda sertifikat NASSCOM 1 India, yang membantu Anda mendapatkan pekerjaan bergaji tinggi di Ilmu Data.