Apa itu Algoritma Breadth First Search? Pengertian dan Cara Kerjanya

Graph traversal adalah metodologi yang umum digunakan untuk menentukan posisi titik dalam graph. Sebelumnya, graph adalah kumpulan dati titik (node) dan garis dimana pasangan-pasangan titik (node) tersebut dihubungkan oleh segmen garis. Node ini biasa disebut simpul (vertex) dan segmen garis disebut sisi/ruas (edge).

Graph traversal berarti mengunjungi setiap simpul (vertex) dan tepi (edge) tepat satu kali dalam urutan yang jelas atau sistematis dari sebuah grafik.

Saat menggunakan algoritma graph traversal tertentu, pastikan terlebih dahulu setiap simpul dari graph dikunjungi tepat satu kali. Urutan di mana simpul dikunjungi sangat penting dan bergantung pada algoritma yang ingin dipecahkan.

Sebelum kita melangkah, terlebih dahulu perlu kita kenali dua istilah penting terkait dengan graph traversal:

Sumber: edureka.co

1. Mengunjungi sebuah node (visiting a node): seperti namanya, mengunjungi sebuah node berarti mengunjungi atau memilih sebuah node
2. Menjelajahi node (exploring a node): menjelajahi node yang berdekatan (node tetangga) dari node yang dipilih

Terdapat dua algoritma pada graph traversal yakni Depth-First Search (DFS) dan Breadth-First Search (BFS). 

Pada artikel ini akan membahas salah satu algoritma dari graph traversal yakni breadth-first search.

Daftar Isi

Pengertian Breadth-First Search

Breadth-first search (BFS) atau Breadth-fist traversal adalah algoritma traversing yang digunakan untuk melintasi atau mencari semua simpul atau node dari suatu struktur data tree atau graph.

Pada algoritma BFS, pencarian dimulai dari pemilihan node awal kemudian dilanjutkan dengan pencarian bertahap level demi level, memeriksa seluruh node pada kedalaman tertentu sebelum masuk ke level yang lebih dalam lagi hingga ditemukan tujuan atau goal state-nya.

Cara Kerja Algoritma Breadth-First Search

Sebelum kita mulai, Anda harus terbiasa dengan struktur data utama yang terlibat dalam algoritma Breadth first search.

Queue adalah struktur data abstrak yang mengikuti prinsip First-In-First-Out (FIFO) yang mana data yang dimasukkan terlebih dahulu akan diakses lebih dulu. Struktur data ini terbuka di kedua ujungnya, di mana satu ujung selalu digunakan untuk memasukkan data (enqueue) dan ujung lainnya digunakan untuk menghapus data (dequeue)

Sumber: edureka.co

Sekarang mari kita lihat langkah-langkah yang terlibat dalam melintasi grafik dengan menggunakan algoritma breadth-first search:

• Langkah 1: Ambil antrian kosong. 

• Langkah 2: Pilih node awal (mengunjungi node) dan masukkan ke dalam antrian.

• Langkah 3: Asalkan antrian tidak kosong, ekstrak node dari antrian dan masukkan node anaknya (menjelajahi node) ke dalam antrian. 

• Langkah 4: Cetak simpul yang diekstraksi

Pseudo code

Berikut pseudocode untuk mengimplementasikan Algoritma Breadth-First Search:

Dalam kode di atas, langkah-langkah dijalankan sebagai berikut:

1. (G, s) adalah input, di sini G adalah grafik dan s adalah simpul akar 
2. Antrian 'Q' dibuat dan diinisialisasi dengan node sumber 's' 
3. Semua simpul anak dari 's' ditandai 
4. Ekstrak 's' dari antrian dan kunjungi node anak 
5. Memproses semua simpul anak dari v 
6. Menyimpan w (node anak) di Q untuk mengunjungi node turunannya lebih lanjut 
7. Lanjutkan sampai 'Q' kosong

Masih bingung? Jangan khawatir, Anda akan memahami ini dengan sebuah contoh.

Contoh Proses Breadth-First Search

Perhatikan grafik di bawah ini, kita akan menggunakan algoritma Breadth-First Search untuk melintasi grafik.

Sumber: edureka.co

Dalam kasus ini, kita akan menetapkan simpul 'a' sebagai simpul akar dan mulai melintasi ke bawah dan mengikuti langkah-langkah yang disebutkan di atas.

Sumber: edureka.co

Gambar di atas menggambarkan proses end-to-end dari Breadth-First Search Algorithm. Berikut penjelasan dari gambar diatas:

1. Simpul atau node ‘a’ akan dianggap sebagai simpul akar dan masukkan ke dalam antrian. 
2. Kemudian ekstrak node 'a' dari antrian dan masukkan node anak 'a', yaitu, 'b' dan 'c'. 
3. Cetak simpul 'a'. 
4. Dapat dilihat antrian tidak kosong dan memiliki simpul 'b' dan 'c'. Karena 'b' adalah simpul pertama dalam antrian, maka diekstrak dan kemudian masukkan simpul anak dari 'b', yaitu, simpul 'd' dan 'e'. 
5. Ulangi langkah ini sampai antrian kosong. Perhatikan bahwa node yang sudah dikunjungi tidak boleh ditambahkan ke antrian lagi.

Contoh lain:

Kelebihan dan kekurangan

Kelebihan BFS

1. Solusi pasti akan ditemukan oleh BFS apabila ada solusi. 
2. BFS tidak akan pernah terjebak di jalur buntu.
3. Jika terdapat lebih dari satu solusi maka akan dicari solusi dengan langkah minimal.

Kekurangan BFS

1. Kendala memori kerena algoritma BFS menyimpan semua node dari level saat ini untuk melanjutkan ke level berikutnya.
2. Jika solusi jauh maka membutuhkan waktu yang lama.

Referensi:

• https://www.edureka.co/blog/breadth-first-search-algorithm/
• https://medium.com/@vatsalunadkat/advantages-and-disadvantages-of-ai-algorithms-d8fb137f4df2

Berbagi :