BFS — Penjelasan Algoritma Breadth-First Search

Breadth-first search, atau BFS, adalah algoritma graf yang mengunjungi simpul berdasarkan urutan jaraknya dari simpul awal. Algoritma ini memeriksa setiap simpul yang berjarak satu sisi terlebih dahulu sebelum berpindah ke simpul yang berjarak dua sisi, lalu tiga sisi, dan seterusnya.

Urutan per lapis itulah gagasan utamanya. Jika graf tak berbobot, atau setiap sisi memiliki biaya yang sama, BFS juga memberikan panjang jalur terpendek dari simpul awal ke setiap simpul yang dapat dicapai.

Apa yang Dilakukan Breadth-First Search

BFS menggunakan queue, yaitu daftar dengan urutan masuk pertama keluar pertama. Queue inilah yang menjaga urutan per lapis: simpul yang ditemukan lebih awal diproses lebih awal.

Pola yang umum adalah:

• tandai simpul awal sebagai sudah dikunjungi
• masukkan simpul awal ke dalam queue
• keluarkan simpul paling depan
• tambahkan setiap tetangga yang belum dikunjungi ke bagian belakang queue
• ulangi sampai queue kosong

Jika Anda juga menyimpan parent dari setiap simpul, Anda dapat merekonstruksi salah satu jalur terpendek setelah pencarian selesai.

Mengapa Queue Membentuk Lapisan

Misalkan simpul $A$ adalah titik awal. Tetangga langsungnya berjarak $1$ dari $A$, sehingga mereka masuk ke queue lebih dulu. Hanya setelah simpul-simpul itu diproses, tetangga mereka yang belum dikunjungi akan masuk, yang berarti gelombang berikutnya berjarak $2$.

Itulah sebabnya BFS secara alami mengelompokkan simpul berdasarkan jaraknya dari titik awal. BFS tidak memperkirakan jalur mana yang pendek. Queue memaksa pencarian menyelesaikan semua jalur dengan sisi yang lebih sedikit sebelum mempertimbangkan jalur yang lebih panjang.

Contoh BFS: Menemukan Jalur Terpendek Berdasarkan Jumlah Sisi

Gunakan graf ini:

$$A \to \{B, C\}, \qquad B \to \{D\}, \qquad C \to \{E\}, \qquad D \to \{F\}, \qquad E \to \{F\}$$

Mulai dari $A$. Queue berubah seperti ini:

$$[A] \to [B, C] \to [C, D] \to [D, E] \to [E, F] \to [F]$$

Berikut artinya:

Pertama, proses $A$, lalu tambahkan $B$ dan $C$. Berikutnya, proses $B$ lalu $C$, yang menambahkan $D$ dan $E$. Setelah itu, proses $D$ dan $E$, yang mencapai $F$.

Jadi urutan kunjungan BFS adalah:

$$A,\ B,\ C,\ D,\ E,\ F$$

Jarak dari $A$ adalah:

$$\operatorname{dist}(A)=0,\quad \operatorname{dist}(B)=1,\quad \operatorname{dist}(C)=1,\quad \operatorname{dist}(D)=2,\quad \operatorname{dist}(E)=2,\quad \operatorname{dist}(F)=3$$

Ini menunjukkan manfaat utamanya. BFS mencapai $F$ pada jarak $3$, jadi jalur terpendek dari $A$ ke $F$ menggunakan $3$ sisi. Salah satu jalur terpendek adalah $A \to B \to D \to F$. Jalur terpendek lainnya adalah $A \to C \to E \to F$.

Kesalahan Umum dalam BFS

Menganggap BFS Selalu Menemukan Jalur Termurah

Itu hanya benar ketika setiap sisi memiliki biaya yang sama, atau ketika graf diperlakukan sebagai tak berbobot. Jika sisi memiliki bobot yang berbeda, BFS bisa menemukan jalur dengan sisi lebih sedikit tetapi total biaya lebih tinggi.

Menandai Simpul Terlambat

Dalam BFS standar, simpul biasanya ditandai sebagai sudah dikunjungi saat dimasukkan ke queue, bukan saat nanti dikeluarkan. Ini mencegah simpul yang sama ditambahkan ke queue berkali-kali.

Mencampuradukkan BFS dan DFS

BFS menjelajah per lapis. Depth-first search, atau DFS, terus mengikuti satu cabang sebelum kembali mundur. Keduanya cocok untuk menjawab jenis pertanyaan yang berbeda.

Lupa Bahwa Urutan Bisa Bergantung pada Urutan Tetangga

Urutan kunjungan yang tepat di dalam lapisan yang sama bisa berubah tergantung bagaimana tetangga didaftarkan. Jaminan jaraknya tetap berlaku, tetapi urutan penelusurannya bisa berbeda.

Kapan Breadth-First Search Digunakan

BFS berguna ketika Anda peduli pada ketercapaian, traversal level-order pada tree, atau panjang jalur terpendek yang diukur dari jumlah sisi.

BFS juga muncul dalam masalah ruang-keadaan ketika setiap langkah memiliki biaya yang sama. Dalam kondisi itu, BFS sering menjadi cara yang paling jelas untuk menemukan jumlah langkah minimum.

Cara Sederhana Mengingat BFS

Bayangkan BFS sebagai riak yang menyebar ke luar dari simpul awal. Setiap langkah riak menambahkan satu sisi jarak lagi.

Untuk mencoba versi Anda sendiri, gambar graf kecil, pilih simpul awal, dan tulis isi queue setelah setiap langkah. Jika ingin melangkah lebih jauh, selesaikan masalah penelusuran graf yang serupa dan periksa apakah klaim jalur terpendek masih berlaku ketika graf berbobot.