GrafMenengahFase D–FE1E5

Maze BFS (Penelusuran Melebar)

Breadth-First Search menelusuri labirin lapis demi lapis untuk menemukan jalur terpendek pada grid tanpa bobot. Ia memakai antrian (queue) FIFO dan himpunan sel yang sudah dikunjungi agar setiap sel diproses satu kali. Visualisasi menampilkan gelombang sel yang dikunjungi meluas dari titik awal hingga mencapai target, lalu menyorot jalur terpendek.

Contoh kasus

Fitur pathfinding pada game agar karakter musuh menemukan rute terpendek menuju pemain di peta berbasis petak.

Silabus

BFS menelusuri graf lapis demi lapis pakai antrian, sehingga selalu menemukan jalur terpendek pada peta tanpa bobot.

Tujuan Belajar

·Memahami cara antrian FIFO memproses simpul lapis demi lapis
·Menjelaskan kenapa BFS menjamin jalur terpendek tanpa bobot
·Menerapkan BFS untuk mencari rute pada labirin grid

Cara Kerja

·Masukkan simpul awal ke antrian dan tandai sudah dikunjungi
·Ambil simpul dari depan antrian, lalu proses
·Masukkan semua tetangga yang belum dikunjungi ke belakang antrian
·Ulangi sampai antrian kosong atau target tercapai
·Karena diproses lapis demi lapis, target pertama kali ditemui via jalur terpendek

Prasyarat

·Antrian (queue)
·Graf

Contoh Nyata

·Musuh di game menemukan rute terpendek ke pemain di peta petak
·Simulasi evakuasi menghitung jalan keluar tercepat saat api menyebar
·Cari teman-terdekat sejauh 2 langkah di jejaring sosial

Kompleksitas O(V + E)