Pencarian melebar (BFS)
Menjelajahi graf lapis demi lapis. Antrean menentukan simpul berikutnya, jadi simpul yang paling dekat selalu dikunjungi lebih dulu.
- O(V + E)
- memori O(V)
- antrean
V dan E: jumlah simpul dan sisi. O(V + E) berarti setiap simpul dan setiap sisi diproses dalam jumlah kali yang tetap.
Antrean: yang pertama masuk, pertama keluar. BFS selalu mengambil simpul yang paling lama menunggu.
Istilah lain di halaman ini
- 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.
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.