Graph

Heap dan priority queue pada chapter sebelumnya adalah struktur bertingkat yang rapi: setiap node punya induk yang jelas dan urutannya diatur aturan heap. Dunia nyata sering lebih liar — rute jalan menghubungkan banyak kota sekaligus, akun di media sosial saling terhubung tanpa hierarki, dan modul program bergantung pada beberapa modul lain. Untuk data seperti itu kita butuh graph: kumpulan simpul (vertex) dan koneksi antar simpul (edge) yang bebas membentuk pola apa pun, termasuk lingkaran. Chapter ini membangun graph tak berarah secara manual, membandingkan dua representasinya, lalu menjalankan dua algoritma penjelajahan paling mendasar: BFS dan DFS, dengan urutan visit yang selalu sama setiap program dijalankan.

Dua Representasi: Adjacency List dan Adjacency Matrix #

Ada dua cara standar menyimpan graph di memori. Adjacency list menyimpan, untuk setiap simpul, daftar tetangganya — dalam program kita, sebuah std::vector<std::vector<int>> di mana tetangga_[u] berisi semua simpul yang tersambung ke u. Adjacency matrix menyimpan tabel V x V berisi 0/1: sel (u, v) bernilai 1 bila ada busur dari u ke v. Keduanya menyimpan graph yang sama; perbedaannya ada pada biaya operasi:

Graf dunia nyata biasanya sparse — rata-rata simpul hanya punya sedikit tetangga — sehingga adjacency list adalah pilihan bawaan. Program berikut membangun graf enam simpul dengan kedua representasi, lalu menampilkan keduanya:

// Graf tak berarah: adjacency list vs adjacency matrix, BFS dan DFS.
#include <iostream>
#include <queue>
#include <vector>

class Graf {
public:
    explicit Graf(int jumlahSimpul) : tetangga_(jumlahSimpul) {}

    void hubungkan(int u, int v) {  // graf tak berarah: catat dua arah
        tetangga_[u].push_back(v);
        tetangga_[v].push_back(u);
    }

    void tampilkanList() const {
        std::cout << "Adjacency list:\n";
        for (int u = 0; u < static_cast<int>(tetangga_.size()); ++u) {
            std::cout << "  " << u << ":";
            for (int v : tetangga_[u]) std::cout << ' ' << v;
            std::cout << '\n';
        }
    }

    void tampilkanMatriks() const {
        std::cout << "Adjacency matrix:\n";
        int n = static_cast<int>(tetangga_.size());
        std::vector<std::vector<int>> m(n, std::vector<int>(n, 0));
        for (int u = 0; u < n; ++u) {
            for (int v : tetangga_[u]) m[u][v] = 1;
        }
        for (int u = 0; u < n; ++u) {
            for (int i = 0; i < n; ++i) {
                if (i > 0) std::cout << ' ';
                std::cout << m[u][i];
            }
            std::cout << '\n';
        }
    }

    // BFS: jelajah level demi level memakai queue
    void bfs(int mulai) const {
        std::vector<bool> dikunjungi(tetangga_.size(), false);
        std::queue<int> antre;
        antre.push(mulai);
        dikunjungi[mulai] = true;
        std::cout << "BFS dari simpul " << mulai << ": ";
        bool pertama = true;
        while (!antre.empty()) {
            int simpul = antre.front();
            antre.pop();
            if (!pertama) std::cout << ' ';
            std::cout << simpul;
            pertama = false;
            for (int t : tetangga_[simpul]) {
                if (!dikunjungi[t]) {
                    dikunjungi[t] = true;
                    antre.push(t);
                }
            }
        }
        std::cout << '\n';
    }

    // DFS: menyelam sedalam mungkin sebelum mundur (rekursi)
    void dfsRekursif(int simpul, std::vector<bool>& dikunjungi, bool& pertama) const {
        dikunjungi[simpul] = true;
        if (!pertama) std::cout << ' ';
        std::cout << simpul;
        pertama = false;
        for (int t : tetangga_[simpul]) {
            if (!dikunjungi[t]) dfsRekursif(t, dikunjungi, pertama);
        }
    }

    void dfs(int mulai) const {
        std::vector<bool> dikunjungi(tetangga_.size(), false);
        std::cout << "DFS dari simpul " << mulai << ": ";
        bool pertama = true;
        dfsRekursif(mulai, dikunjungi, pertama);
        std::cout << '\n';
    }

private:
    std::vector<std::vector<int>> tetangga_;
};

int main() {
    Graf g(6);
    g.hubungkan(0, 1);
    g.hubungkan(0, 2);
    g.hubungkan(1, 3);
    g.hubungkan(2, 4);
    g.hubungkan(3, 5);
    g.hubungkan(4, 5);

    g.tampilkanList();
    g.tampilkanMatriks();
    g.bfs(0);
    g.dfs(0);
    return 0;
}

Output yang Dihasilkan:

Adjacency list:
  0: 1 2
  1: 0 3
  2: 0 4
  3: 1 5
  4: 2 5
  5: 3 4
Adjacency matrix:
0 1 1 0 0 0
1 0 0 1 0 0
1 0 0 0 1 0
0 1 0 0 0 1
0 0 1 0 0 1
0 0 0 1 1 0
BFS dari simpul 0: 0 1 2 3 4 5
DFS dari simpul 0: 0 1 3 5 4 2

Bedah baris penting:

1. Baris 6-13 (class Graf): adjacency list tunggal menjadi satu-satunya sumber data. hubungkan(u, v) mencatat dua arah (baris 11-12) karena graf kita tak berarah.
2. Baris 15-22 (tampilkanList): setiap baris adalah satu simpul beserta daftar tetangganya, misalnya 0: 1 2.
3. Baris 24-38 (tampilkanMatriks): matrix tidak disimpan — ia diturunkan dari list saat dicetak. Ini keputusan desain yang baik: satu sumber kebenaran, dua tampilan.
4. Baris 41-62 (bfs): penjelajahan melebar memakai std::queue; dibedah di bagian berikutnya.
5. Baris 65-73 (dfsRekursif): penjelajahan mendalam memakai rekursi; tumpukan pemanggilan fungsi berperan sebagai stack.
6. Baris 87-94: enam pemanggilan hubungkan membangun graf; urutannya menentukan urutan tetangga di list.

BFS: Jelajah Melebar dengan Queue #

BFS (Breadth-First Search) menjelajah per level: dulu semua simpul berjarak 1 busur dari titik awal, baru semua simpul berjarak 2, dan seterusnya. Mekanismenya adalah queue: simpul yang lebih dulu ditemukan lebih dulu diproses. Trace dari output: simpul 0 dicetak, tetangganya 1 dan 2 masuk antrean; lalu 1 dicetak dan tetangga barunya 3 masuk; lalu 2 mencatat 4; baru setelah level dua selesai, 3 dan 4 mencatat 5. Hasilnya 0 1 2 3 4 5 — persis tersusun per level {0}, {1,2}, {3,4}, {5}.

Urutan ini deterministik karena dua keputusan yang kita ambil sadar: dikunjungi[t] ditandai saat simpul dimasukkan antrean (bukan saat dikeluarkan) sehingga tidak ada duplikat, dan tetangga diperiksa sesuai urutan penyimpanan di adjacency list. Sifat level-per-level inilah yang membuat BFS menjamin jalur dengan busur paling sedikit pada graf tak berbobot — fondasi dari algoritma jarak terpendek yang diperdalam di chapter Graph Algorithms.

DFS: Menyelam Dalam dengan Rekursi #

DFS (Depth-First Search) memilih strategi berlawanan: dari simpul sekarang, langsung menyelam ke satu tetangga yang belum dikunjungi, dan terus menyelam sampai buntu, lalu mundur ke persimpangan terakhir. Rekursi memberi perilaku ini secara gratis — tumpukan pemanggilan fungsi menyimpan “jalur kembali”. Trace output: dari 0 kita menyelam ke 1, lalu 3, lalu 5, lalu 4, lalu 2; hasilnya 0 1 3 5 4 2.

Perhatikan bahwa BFS dan DFS mengunjungi himpunan simpul yang sama persis; yang berbeda hanya urutan. Bila Anda butuh versi iteratif, rekursi DFS dapat diganti std::stack eksplisit dengan pola yang sama. Keduanya berjalan O(V + E): setiap simpul dan setiap busur disentuh paling banyak dua kali.

Graph menuntut pencarian pada struktur yang tidak linear, dan itu mengingatkan kita pada pertanyaan paling dasar dari semua: bagaimana mencari satu nilai di deretan data biasa? Chapter berikutnya mulai dari titik itu — linear search, algoritma pencarian paling sederhana, dan pengukuran jujur kapan ia cukup.

Rujukan resmi: std::queue dan std::vector .