Breadth First Search (BFS) adalah teknik penelusuran graf atau pohon yang bekerja secara berlapis, menelusuri simpul-simpul pada level yang sama sebelum bergerak ke level berikutnya. Metode ini memastikan simpul-simpul terdekat dari titik awal diproses terlebih dahulu, membuatnya ideal untuk mencari jalur terpendek dalam graf tak berbobot. BFS juga menjadi dasar untuk berbagai algoritma dan aplikasi dalam ilmu komputer.
Pada dasarnya, BFS memulai penelusuran dari simpul awal (root) lalu menjelajahi semua tetangga (neighbor) secara menyeluruh. Setelah semua simpul pada satu tingkat terkunjungi, barulah algoritma melanjutkan ke tingkat berikutnya. Proses ini berlanjut hingga semua simpul terkunjungi atau simpul tujuan ditemukan. Dengan cara ini, BFS mampu memberikan urutan penelusuran berdasarkan kedekatan hop.
Konsep utama BFS melibatkan penggunaan struktur data queue (antrian) untuk mengatur urutan simpul yang akan dikunjungi. Setiap kali simpul diproses, semua tetangganya yang belum pernah dikunjungi dimasukkan ke dalam antrian. Setelah itu, elemen antrian di-dequeue satu per satu, dan proses penelusuran berlanjut hingga antrian kosong atau kondisi berhenti terpenuhi.
Cara Kerja dan Implementasi BFS
Prinsip kerja BFS meliputi tiga langkah utama: inisialisasi, penelusuran, dan penandaan simpul yang sudah dikunjungi. Inisialisasi mencakup penempatan simpul awal ke dalam antrian dan penandaan sebagai telah dikunjungi. Pada tahap penelusuran, simpul terdepan di-dequeue, lalu semua tetangga yang belum dikunjungi di-enqueue dan ditandai. Siklus ini terus berulang untuk mengeksplorasi graf secara berlapis.
Berikut contoh pseudocode sederhana BFS pada graf G dengan simpul s sebagai sumber:
- Queue Q = kosong; mark[s] = true; enqueue s ke Q;
- while Q tidak kosong:
- u = dequeue Q;
- for setiap tetangga v dari u:
- if mark[v] == false:
- mark[v] = true;
- enqueue v ke Q;
- if mark[v] == false:
Pseudocode di atas menekankan penggunaan queue dan penandaan simpul agar tidak terjadi kunjungan ganda.
Struktur data queue bekerja berdasarkan prinsip FIFO (First In, First Out). Dalam konteks BFS, antrian memastikan simpul yang lebih dulu dimasukkan akan diproses terlebih dahulu, memenuhi tujuan penelusuran level-order. Implementasi queue dapat menggunakan array, linked list, atau deque sesuai bahasa pemrograman.
Aplikasi Utama Breadth First Search
Pencarian Jalur Terpendek
Salah satu penerapan paling umum BFS adalah mencari jalur terpendek pada graf tak berbobot. Dengan eksplorasi berlapis, BFS menjamin menemukan jalur dengan jumlah hop paling sedikit antara simpul sumber dan tujuan. Metode ini sering digunakan pada sistem navigasi, robotika, dan pemecahan labirin.
Traversal Pohon (Level Order)
Pada struktur pohon, BFS dikenal sebagai level-order traversal. Algoritma ini mengunjungi semua node pada satu tingkat sebelum melanjutkan ke tingkat berikutnya, berguna dalam pencetakan pohon, penyeimbangan pohon biner, dan algoritma pencarian terstruktur lain.
Pemodelan Jejaring Sosial
Dalam analisis jejaring sosial, BFS dapat digunakan untuk menemukan tingkat koneksi antar pengguna (degree of separation). Misalnya, algoritma ini membantu mengukur jarak pertemanan di media sosial, mengidentifikasi komunitas, dan menganalisis penyebaran informasi.
Keunggulan dan Keterbatasan
Keunggulan BFS
Salah satu keunggulan utama BFS adalah kemampuannya menjamin jalur terpendek pada graf tak berbobot. Selain itu, algoritma ini relatif mudah diimplementasikan dan dipahami. Penggunaan queue juga membuat alurnya jelas dan sistematis, sehingga cocok untuk aplikasi real-time dan pemrosesan graf besar dengan struktur berlapis.
Keterbatasan dan Tantangan
Meski demikian, BFS memiliki keterbatasan, terutama pada penggunaan memori. Karena harus menyimpan antrian semua simpul yang akan diproses, konsumsi memori dapat meningkat pesat pada graf dengan cabang lebar (high branching factor). Selain itu, pada graf berbobot atau graf sangat besar, BFS mungkin tidak efisien dalam hal waktu dan ruang.
Kesimpulan
Beberapa strategi untuk mengoptimalkan BFS antara lain:
- Gunakan representasi graf efisien seperti adjacency list.
- Implementasikan queue dengan deque untuk operasi enqueue/dequeue O(1).
- Manfaatkan bitset untuk penandaan simpul pada graf besar.
- Lakukan filter awal untuk mengurangi tetangga yang tidak relevan.
Breadth First Search merupakan algoritma fundamental dalam ilmu komputer, banyak diaplikasikan mulai dari pencarian jalur terpendek hingga analisis jejaring sosial. Memahami konsep, implementasi, serta keunggulan dan keterbatasannya sangat penting untuk memilih metode yang tepat dalam memecahkan berbagai permasalahan graf dan pohon.