Breadth-First Search (BFS)
Jatuhkan batu ke kolam, dan riaknya menyebar merata dalam lingkaran. Breadth-first search (pencarian melebar) menjelajahi graf dengan cara yang sama: pertama semua yang berjarak satu langkah dari awal, lalu semua yang berjarak dua langkah, dan seterusnya. Urutan sederhana itulah yang membuatnya menemukan jalur terpendek.
Idenya
Graf adalah kumpulan simpul yang dihubungkan oleh sisi: tempat dan jalan, orang dan pertemanan, kotak labirin dan celah di antaranya. Breadth-first search menjawab pertanyaan: mulai dari sini, ke mana saja saya bisa sampai, dan dalam berapa langkah paling sedikit? BFS menyimpan antrean simpul yang masih harus dikunjungi. Mengambil simpul dari depan dan menambah simpul baru di belakang berarti simpul ditangani sesuai urutan ditemukannya.
Langkah demi langkah
Masukkan awal ke antrean dengan jarak 0. Ambil simpul di depan. Untuk tiap tetangga yang belum pernah dilihat, catat jaraknya satu lebih besar dari simpul saat ini, ingat simpul saat ini sebagai jalan ia dicapai, lalu tambahkan ke belakang antrean. Lewati tetangga yang sudah pernah dilihat. Ulangi sampai antrean kosong, atau sampai tujuan tercapai.
Contoh
Ambil graf dengan sisi A–B, A–C, B–D, C–D, C–E, dan D–F, lalu mulai dari A. Mengambil A dari antrean menemukan B dan C pada jarak 1. Mengambil B menemukan D pada jarak 2. Mengambil C mendapati D sudah pernah dilihat, dan menemukan E pada jarak 2. Mengambil D menemukan F pada jarak 3. E dan F tidak menemukan yang baru, dan antrean kosong. Menelusuri simpul yang diingat dari F memberi F ← D ← B ← A, jadi jalur terpendek dari A ke F adalah A → B → D → F, sepanjang tiga sisi.
Mengapa jaraknya benar
Setiap simpul berjarak 1 masuk antrean sebelum simpul berjarak 2 mana pun, setiap simpul berjarak 2 sebelum simpul berjarak 3 mana pun, dan seterusnya, karena tetangga sebuah simpul baru masuk antrean saat simpul itu sendiri keluar dari antrean. Jadi jalur pertama yang mencapai sebuah simpul adalah jalur dengan sisi paling sedikit, dan BFS tidak pernah perlu mengoreksi jarak. Tiap simpul diambil sekali dan tiap sisi dilihat dari kedua ujungnya, jadi kerjanya bertambah sesuai jumlah simpul ditambah jumlah sisi.
Sejarah dan kegunaan
Konrad Zuse menjelaskan breadth-first search pada 1945, dalam karyanya tentang bahasa Plankalkül yang baru diterbitkan pada 1972. Edward F. Moore menemukannya kembali pada 1959 untuk mencari jalur terpendek keluar dari labirin, dan C. Y. Lee memakainya pada 1961 untuk merutekan kabel di papan sirkuit. Kini BFS dipakai untuk mencari langkah paling sedikit dalam teka-teki, derajat keterpisahan di jejaring sosial, halaman yang pertama dicapai web crawler, dan sel kosong terdekat dalam game. Jika sisi punya panjang, algoritma Dijkstra memperumumnya.
Jelajahi sendiri
Buka aplikasinya dan tekan Langkah. Simpul yang sedang dikunjungi disorot, simpul yang menunggu di antrean berwarna biru, dan simpul yang sudah dikunjungi berwarna hijau, masing-masing dengan jaraknya. Antrean ditampilkan di bawah graf, bagian depan lebih dulu. Ubah klik ke Tujuan dan pilih simpul untuk berhenti di sana dan melihat jalur terpendek, atau buat graf baru dengan lebih banyak simpul dan sisi.
Pertanyaan yang sering diajukan
Berapa kompleksitas waktu BFS?
O(V + E) untuk V simpul (vertex) dan E sisi: tiap simpul masuk dan keluar antrean sekali, dan tiap sisi diperiksa dari kedua ujungnya. BFS butuh memori tambahan O(V) untuk antrean dan jarak.
Mengapa BFS memakai antrean?
Karena pertama masuk, pertama keluar menjaga simpul dalam urutan ditemukannya, yaitu urutan jaraknya. Jika memakai stack, pencarian akan menyelam ke dalam dulu: itulah depth-first search.
Bisakah BFS menemukan jalur terpendek pada graf berbobot?
Secara umum tidak: BFS menghitung sisi, bukan panjangnya. Untuk graf berbobot tanpa sisi negatif, pakai algoritma Dijkstra. Jika setiap bobot 0 atau 1, varian bernama 0-1 BFS bisa dipakai.
Di mana BFS dipakai?
Menyelesaikan teka-teki dan labirin dengan langkah paling sedikit, mencari teman dari teman di jejaring sosial, menjelajahi web tingkat demi tingkat, broadcast di jaringan, dan sebagai bagian dari algoritma lain seperti mencari aliran maksimum.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Coba Breadth-First Search