Rangkuman: Breadth-First Search (BFS)

Graph Traversal

1. Pengertian

Breadth-First Search (BFS) adalah algoritma untuk melintasi atau mencari pohon atau struktur data graf. Algoritma ini memulai dari node (simpul) akar (atau node awal yang dipilih) dan mengeksplorasi semua node tetangga pada kedalaman saat ini sebelum bergerak ke node pada tingkat kedalaman berikutnya. Dengan kata lain, BFS mengunjungi semua node pada satu "level" sebelum melanjutkan ke "level" berikutnya.

BFS menjamin menemukan jalur terpendek dalam graf yang tidak berbobot (unweighted graph).

2. Konsep Dasar & Mekanisme

BFS menggunakan struktur data antrian (queue) untuk menyimpan node-node yang akan dikunjungi. Ini memastikan bahwa node dikunjungi secara level demi level.

Langkah-langkah Algoritma:

Mulai dari node awal (sumber), tandai node tersebut sebagai "dikunjungi" dan tambahkan ke antrian.
Selama antrian tidak kosong:
- Keluarkan (dequeue) sebuah node dari antrian.
- Proses node yang dikeluarkan tersebut (misalnya, cetak namanya).
- Untuk setiap tetangga dari node yang dikeluarkan:
  - Jika tetangga tersebut belum dikunjungi:
    - Tandai tetangga sebagai "dikunjungi".
    - Tambahkan tetangga ke antrian.

Penting untuk menggunakan set `visited` (atau array boolean) untuk melacak node mana yang sudah dikunjungi agar tidak masuk ke dalam siklus tak terbatas dalam graf.

3. Contoh Ilustrasi

Graf berikut:


    A --- B
    | \   |
    |  \  |
    C --- D
    |     |
    E --- F

Jika dimulai dari Node A:

Antrian: [A], Dikunjungi: {A}
Keluarkan A. Proses A. Tetangga A: B, C, D. Tambahkan B, C, D ke antrian.
Antrian: [B, C, D], Dikunjungi: {A, B, C, D}
Keluarkan B. Proses B. Tetangga B: A (dikunjungi), D (dikunjungi). Tidak ada tetangga baru.
Antrian: [C, D], Dikunjungi: {A, B, C, D}
Keluarkan C. Proses C. Tetangga C: A (dikunjungi), D (dikunjungi), E. Tambahkan E ke antrian.
Antrian: [D, E], Dikunjungi: {A, B, C, D, E}
Keluarkan D. Proses D. Tetangga D: A, B, C (dikunjungi), F. Tambahkan F ke antrian.
Antrian: [E, F], Dikunjungi: {A, B, C, D, E, F}
Keluarkan E. Proses E. Tetangga E: C (dikunjungi), F (dikunjungi). Tidak ada tetangga baru.
Antrian: [F], Dikunjungi: {A, B, C, D, E, F}
Keluarkan F. Proses F. Tetangga F: D, E (dikunjungi). Tidak ada tetangga baru.
Antrian: [], Dikunjungi: {A, B, C, D, E, F}

Urutan kunjungan: A -> B -> C -> D -> E -> F

4. Pseudocode Algoritma


FUNCTION BFS(graph, start_node):
    queue = new Queue()
    visited = new Set() // Atau array boolean

    queue.ENQUEUE(start_node)
    visited.ADD(start_node)

    WHILE queue IS NOT EMPTY:
        current_node = queue.DEQUEUE()
        PRINT current_node // Atau lakukan operasi lain pada node

        FOR EACH neighbor OF current_node:
            IF neighbor IS NOT IN visited:
                visited.ADD(neighbor)
                queue.ENQUEUE(neighbor)

5. Kompleksitas Waktu & Ruang

Kompleksitas Waktu:
- $O(V + E)$, di mana $V$ adalah jumlah simpul (vertices) dan $E$ adalah jumlah sisi (edges). Ini karena setiap simpul dan setiap sisi akan dikunjungi maksimal satu kali.
- Jika graf direpresentasikan dengan matriks adjacency, kompleksitas bisa menjadi $O(V^2)$.
Kompleksitas Ruang: $O(V)$ untuk menyimpan antrian dan set `visited` (dalam kasus terburuk, semua simpul mungkin berada di antrian).

6. Aplikasi

**Pencarian Jalur Terpendek:** Menemukan jalur terpendek dalam graf tak berbobot.
**Web Crawlers:** Digunakan oleh mesin pencari untuk mengindeks halaman web.
**Sistem GPS:** Menemukan rute terpendek antar lokasi.
**Networking:** Digunakan untuk menemukan broadcast path dalam jaringan.
**Social Networking:** Menemukan semua orang dalam 'N' tingkat dari seseorang.
**Garbage Collection:** Dalam bahasa pemrograman tertentu.