BREADTH-FIRST SEARCH (BFS)

Breadth-First Search (BFS)

Selamat datang pada pembahasan mengenai algoritma Breadth-First Search (BFS), sebuah pendekatan yang sangat berguna untuk menemukan jalur terpendek dalam struktur data graf maupun pohon. Konsep dasarnya adalah menjelajahi semua simpul tetangga terlebih dahulu sebelum melangkah ke simpul yang lebih jauh.

---

Definisi Breadth-First Search

Breadth-First Search adalah algoritma traversal graf yang bekerja berdasarkan jarak dari simpul awal. Artinya, algoritma ini akan mengunjungi semua simpul pada satu tingkat (level) terlebih dahulu, sebelum beralih ke tingkat berikutnya.

Aplikasi Umum BFS:

• Menemukan jalur terpendek dalam graf tak berbobot
• Menelusuri hubungan dalam jaringan sosial
• Pencarian rute dalam sistem navigasi
• Analisis dan penelusuran jaringan komputer

---

Struktur Data yang Digunakan: Queue

BFS menggunakan struktur data antrian (queue) untuk menyimpan simpul-simpul yang akan dieksplorasi. Berikut langkah-langkah algoritmanya:

1. Masukkan simpul awal ke dalam queue.
2. Ambil simpul dari depan antrian, lalu tandai sebagai dikunjungi.
3. Masukkan semua tetangga dari simpul tersebut yang belum dikunjungi ke dalam queue.
4. Ulangi proses hingga antrian kosong.

---

Ilustrasi Proses BFS

Graf berikut digunakan sebagai contoh:

     S
    / \
   A   B
  / \ / \
 C  D E  F
       / \
      H   G

Simulasi antrian (queue) dan simpul yang dikunjungi:

Queue    : S → A,B → C,D,E,F → H,G
Visited  : S → A,B → C,D,E,F → H,G

---

Implementasi dalam Bahasa C++

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

void bfs(int start, vector<vector<int>>& adj, int n) 
        }}
    }}
}}

int main() ; // S
    adj[1] = 0; // A
    adj[2] = 0; // B
    adj[3] = 1; // C
    adj[4] = 1; // D
    adj[5] = 2; // E
    adj[6] = 2; // F

    bfs(0, adj, n);
    return 0;
}}

---

Aplikasi BFS dalam Kehidupan Nyata

1. Navigasi & Transportasi: Digunakan dalam sistem navigasi untuk mencari rute tercepat.
2. Kecerdasan Buatan & Permainan: BFS digunakan untuk eksplorasi dalam permainan seperti Pac-Man.
3. Jejaring Sosial: Menentukan hubungan seperti “teman dari teman”.
4. Jaringan Komputer: BFS digunakan untuk menelusuri konektivitas dalam topologi jaringan.

---

Kelebihan dan Kekurangan

Kelebihan:

• Menjamin pencarian jalur terpendek dalam graf tak berbobot
• Implementasinya relatif sederhana

Kekurangan:

• Membutuhkan memori lebih besar dibanding DFS
• Kurang efisien untuk graf yang sangat besar dan dalam

---

Kesimpulan

Breadth-First Search adalah algoritma penelusuran graf yang sistematis dan efektif. BFS bekerja dengan menjelajahi simpul berdasarkan urutan level atau kedalaman dari simpul awal, dan sangat sesuai untuk menemukan jalur terpendek dalam graf tak berbobot.

Semoga penjelasan ini bermanfaat dalam memahami konsep dan implementasi BFS secara menyeluruh.