Pencarian melebar (BFS)
Menjelajahi graf lapis demi lapis. Antrean menentukan simpul berikutnya, jadi simpul yang paling dekat selalu dikunjungi lebih dulu.
- waktu O(V + E)
- memori O(V)
- memakai antrean
Apa artinya?
- Simpul: titik pada graf, di sini digambar sebagai lingkaran berhuruf.
- Sisi: garis yang menghubungkan dua simpul. Di sini sisi bisa dilalui ke dua arah.
- Tetangga: simpul-simpul yang terhubung ke suatu simpul lewat sisi. Tetangga diperiksa menurut urutan abjad.
- Antrean: yang pertama masuk, pertama keluar. BFS selalu mengambil simpul yang paling lama menunggu.
- Tumpukan: yang terakhir masuk, pertama keluar. DFS selalu melanjutkan dari simpul yang terakhir dicapainya.
- V dan E: jumlah simpul dan sisi. O(V + E) berarti setiap simpul dan setiap sisi diproses dalam jumlah kali yang tetap.
- di antrean
- saat ini
- tuntas
- sisi pohon pencarian
- sisi yang diabaikan
Mulai dari A. Tekan putar atau jalankan langkah demi langkah.
Spasi: putar atau jeda. Panah kiri dan kanan: melangkah. Home dan End: lompat.
Coba ini: Pilih graf dua bagian. Simpul yang tidak terhubung ke simpul awal tidak pernah tercapai.
Cara kerjanya
BFS memasukkan simpul awal ke antrean. Lalu, berulang kali, BFS mengambil simpul di depan antrean dan menambahkan tetangga barunya ke belakang. Antrean melayani sesuai urutan datang, jadi setiap simpul yang berjarak satu sisi tuntas sebelum simpul mana pun yang berjarak dua sisi. Angka di samping simpul adalah jaraknya dari awal: jumlah sisi paling sedikit untuk mencapainya.
Kapan ini pilihan yang tepat
Gunakan BFS saat Anda butuh jalur terpendek dalam jumlah langkah: langkah paling sedikit dalam teka-teki, lompatan paling sedikit dalam jaringan, orang-orang yang berjarak dua koneksi dari Anda. Pada graf besar antrean bisa menjadi panjang, karena menampung satu lapis penuh sekaligus.