Pencarian Breit

Sebuah algoritma dasar untuk traversing graf yang mengeksplorasi node dalam lapisan untuk secara sistematis menginvestigasi semua simpul yang dapat dicapai dari titik awal.

Definisi

Pencarian Breit (BFS) adalah strategi sistematis untuk menelusuri atau mencari struktur graf dan pohon dengan mengunjungi node dalam level-level dari node sumber tertentu, memastikan semua tetangga langsung diproses sebelum node yang lebih dalam. Algoritma ini menggunakan antrian untuk mengelola frontir eksplorasi, yang mempertahankan urutan node yang ditemukan dan menunggu pemrosesan. BFS sangat efektif dalam graf tanpa bobot untuk menemukan jalur terpendek (dalam hal jumlah sisi) ke node target dan untuk analisis berorientasi breadth. Pendekatan ini menjamin kelengkapan dalam graf berhingga, artinya akan menemukan solusi yang valid jika ada. BFS juga menjadi dasar banyak algoritma graf dan aplikasi praktis di jaringan, AI, dan analisis data.

Kelebihan

• Selalu menemukan jalur terpendek dalam graf tanpa bobot karena sifatnya level by level.
• Menjamin kelengkapan: akan menemukan solusi jika ada (dalam ruang pencarian berhingga).
• Urutan traversasi dapat diprediksi dan sistematis, berguna untuk banyak tugas analitis.
• Sederhana untuk diimplementasikan dengan struktur data antrian standar.
• Mendukung pembuatan pohon jalur terpendek dan berbagai aplikasi algoritma.

Kekurangan

• Penggunaan memori bisa meningkat signifikan karena menyimpan semua node frontir di setiap kedalaman.
• Lebih tidak efisien untuk graf yang sangat dalam atau besar dibandingkan metode yang berorientasi kedalaman.
• Kinerja mungkin menurun pada dataset yang sangat terhubung karena frontir yang luas.
• Membutuhkan catatan tambahan untuk menghindari mengunjungi ulang node dalam graf siklik.
• Tidak cocok untuk graf berbobot tanpa modifikasi (misalnya, algoritma Dijkstra).

Kasus Penggunaan

• Crawling web dan eksplorasi tautan terstruktur dari URL awal.
• Menemukan rute terpendek atau koneksi dalam jaringan tanpa bobot seperti graf sosial.
• Traversal level-order pada pohon, seperti ekspansi breadth pada pohon biner.
• Penemuan jalur terpendek dalam AI, pathfinding robotik, dan penyelesaian labirin.
• Dasar untuk algoritma graf lanjutan seperti pemeriksaan keterhubungan dan struktur spanning.