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.

Graf dengan simpul berhuruf yang diwarnai per lingkaran menurut jaraknya dari simpul awal, dengan antrean simpul digambar di bawahnya
Graf dengan simpul berhuruf yang diwarnai per lingkaran menurut jaraknya dari simpul awal, dengan antrean simpul digambar di bawahnya

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.

Konrad Zuse (tengah, berkacamata) dan Heinz Billing (kiri) di pameran SYSTEMS ’91 di München. Zuse menjabarkan pencarian lebar-dahulu pada 1945, dalam karya tentang bahasa Plankalkül-nya yang baru terbit 1972.
Konrad Zuse (tengah, berkacamata) dan Heinz Billing (kiri) di pameran SYSTEMS ’91 di München. Zuse menjabarkan pencarian lebar-dahulu pada 1945, dalam karya tentang bahasa Plankalkül-nya yang baru terbit 1972.

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