Breadth First Search

Banyak persoalan graph berakar pada satu pertanyaan sederhana: dari titik awal, node mana saja yang dapat dicapai, dan berapa jarak minimumnya? Breadth First Search (BFS) adalah algoritma traversal graph yang menjawab pertanyaan tersebut dengan menjelajahi node layer demi layer — semua node pada jarak k dari sumber diproses sebelum node pada jarak k+1. Karena sifat level-nya, BFS adalah pilihan utama untuk pencarian jalur terpendek pada graph tak berbobot, penemuan connected component, dan deteksi graph bipartite. Pada Chapter ini kita akan membedah mekanisme BFS, mengimplementasikannya dengan std::queue, dan menelusuri urutan kunjungannya pada sebuah graph contoh.

Aturan: BFS Level-by-Level #

Diberikan graph G = (V, E) dan sebuah node sumber src, BFS memproses node dalam urutan menaik berdasarkan jarak dari src. Pada setiap langkah, node yang sedang diproses mendorong semua tetangganya yang belum dikunjungi ke dalam antrian. Antrian inilah yang menjamin urutan pemrosesan level demi level.

Mekanisme: Queue sebagai Invariant Level #

Kunci BFS ada pada struktur data queue (FIFO). Saat sebuah node u di-pop dari depan antrian, semua tetangga v yang belum dikunjungi di-push ke belakang antrian. Karena antrian FIFO, tetangga node pada level k akan diproses tepat setelah semua node level k selesai diproses — yang berarti mereka berada pada level k+1.

Setiap node ditandai visited saat dimasukkan ke antrian, bukan saat di-pop. Penandaan awal ini mencegah node yang sama dimasukkan beberapa kali ke antrian (kasus klasik: segitiga 0-1-2).

Implementasi BFS dengan std::queue #

#include <iostream>
#include <vector>
#include <queue>

void bfs(const std::vector<std::vector<int>>& adj, int src) {
    int n = static_cast<int>(adj.size());
    std::vector<bool> visited(n, false);
    std::vector<int> dist(n, -1);
    std::queue<int> q;

    visited[src] = true;
    dist[src] = 0;
    q.push(src);

    std::cout << "BFS mulai dari node " << src << ":\n";
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        std::cout << "  visit " << u << " (dist=" << dist[u] << ")\n";
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }

    std::cout << "Jarak akhir: ";
    for (int i = 0; i < n; ++i) std::cout << dist[i] << ' ';
    std::cout << '\n';
}

int main() {
    // Graph:
    //   0 -- 1 -- 2
    //   |    |    |
    //   3 -- 4 -- 5
    //        |
    //        6
    std::vector<std::vector<int>> adj(7);
    auto add_edge = [&](int a, int b) {
        adj[a].push_back(b);
        adj[b].push_back(a);
    };
    add_edge(0, 1); add_edge(1, 2);
    add_edge(0, 3); add_edge(3, 4); add_edge(4, 5);
    add_edge(1, 4); add_edge(2, 5);
    add_edge(4, 6);

    bfs(adj, 0);
    return 0;
}

Output yang Dihasilkan:

BFS mulai dari node 0:
  visit 0 (dist=0)
  visit 1 (dist=1)
  visit 3 (dist=1)
  visit 2 (dist=2)
  visit 4 (dist=2)
  visit 5 (dist=3)
  visit 6 (dist=3)
Jarak akhir: 0 1 2 1 2 3 3

Bedah Kode Baris-per-Baris #

1. std::vector<bool> visited(n, false): array penanda node yang sudah dimasukkan ke antrian. bool cukup karena hanya ada dua status.
2. std::vector<int> dist(n, -1): menyimpan jarak dari src. Nilai awal -1 berarti “tak terjangkau” — bila BFS selesai dan dist[v] masih -1, maka v tidak terhubung dengan src.
3. visited[src] = true; dist[src] = 0; q.push(src);: inisialisasi sumber. Penting: tandai visited sebelum push untuk mencegah duplikasi.
4. int u = q.front(); q.pop();: ambil node paling depan dari antrian. Urutan pemrosesan FIFO inilah yang menjaga level order.
5. for (int v : adj[u]): iterasi seluruh tetangga u dari adjacency list.
6. if (!visited[v]): hanya proses v yang belum pernah dimasukkan. Tanpa cek ini, BFS bisa memasukkan node yang sama berkali-kali (dan jaraknya salah).
7. dist[v] = dist[u] + 1: jarak v = jarak u + 1 edge. Inilah inti mengapa BFS menemukan jalur terpendek pada graph tak berbobot.
8. Urutan output: level 0 = {0}, level 1 = {1, 3}, level 2 = {2, 4}, level 3 = {5, 6}. Hasil ini konsisten dengan struktur graph.

Trace Urutan Kunjungan #

Edge (2,5) dan (1,4) menyebabkan node 5 bisa dicapai dari level 2, namun karena dist[5] di-set saat pertama kali ditemukan (dari node 4 yang level 2), hasilnya tetap 3 — sesuai dengan BFS yang menetapkan jarak saat node pertama kali di-push.

Kompleksitas #

Variasi dan Penerapan #

• BFS multi-source: masukkan beberapa sumber ke antrian sekaligus, dist-nya = 0. Berguna untuk soal “jarak ke pomp terdekat” atau penyebaran api multi-titik.
• BFS bidirectional: jalankan dua BFS dari src dan dst secara bersamaan, berhenti saat keduanya bertemu. Kompleksitas turun dari O(b^d) ke O(b^(d/2)).
• Deteksi graph bipartite: warnai node secara alternating berdasarkan level. Bila ada edge antara dua node level sama → graph bukan bipartite.
• Connected component: jalankan BFS pada setiap node yang belum visited; jumlah inisialisasi = jumlah komponen.

Ringkasan #

• BFS menjelajahi graph level demi level menggunakan std::queue (FIFO).
• Tandai visited saat push, bukan saat pop — mencegah duplikasi antrian.
• Pada graph tak berbobot, dist[v] = dist[u] + 1 menjamin jalur terpendek.
• Kompleksitas O(V + E) waktu dan O(V) ruang.
• Variasi: multi-source, bidirectional, deteksi bipartite, connected component.

Bab berikutnya akan membahas traversal graph lain — Depth First Search — yang memprioritaskan kedalaman daripada lebar, dan menjadi fondasi banyak algoritma lanjutan seperti deteksi siklus, topological sort, dan SCC.