Graph

Motivasi: Jaring-Jaring Kehidupan

Sejauh ini kita telah belajar menyusun data secara lurus berbaris (Linked List, Stack, Queue) dan secara hierarki atas-bawah (Tree). Namun, bagaimana jika kita ingin memodelkan data pertemanan di media sosial? Teman Anda bisa berteman dengan teman dari teman Anda, membentuk jaring-jaring yang saling silang.

Bagaimana dengan peta digital? Sebuah kota bisa memiliki banyak jalan yang terhubung ke berbagai kota lain, dan Anda bisa berputar-putar kembali ke kota asal.

Struktur data yang digunakan untuk memodelkan hubungan antar objek yang kompleks seperti ini disebut Graph. Graph digunakan di hampir seluruh teknologi modern:

• Media Sosial: Analisis jaringan pertemanan.
• Internet: Rute pengiriman paket data komputer.
• Sains: Memodelkan penyebaran penyakit atau jalur migrasi.

Anatomi Graph: $G = (V, E)$

Secara formal, sebuah Graph dibangun oleh dua elemen utama:

1. V (Vertices / Simpul): Sekumpulan titik atau objek data. Himpunan ini tidak boleh kosong.
2. E (Edges / Berus / Jalur): Sekumpulan garis yang menghubungkan simpul-simpul tersebut. Himpunan ini boleh kosong (simpul tidak terhubung).

Berdasarkan arah dan bobotnya, Graph dibagi menjadi beberapa jenis:

1. Directed Graph (Graf Berarah)

Jalan satu arah. Jika A ke B, belum tentu B bisa kembali ke A (A → B).

2. Undirected Graph (Graf Tak Berarah)

Jalan dua arah (timbal balik). A ke B otomatis berarti B ke A (A ↔ B).

3. Weighted Graph (Graf Berbobot)

Setiap jalur memiliki nilai bobot atau biaya (misal: jarak dalam km, biaya tol, atau waktu tempuh).

Representasi Graph di Memori

Komputer tidak memiliki mata untuk "melihat" gambar jaring-jaring atau lingkaran yang dihubungkan dengan garis. Bagi komputer, semuanya harus diterjemahkan menjadi struktur data terstruktur.

Ada dua teknik utama untuk menerjemahkan gambar jaring-jaring ini ke dalam memori komputer:

1. Adjacency Matrix (Matriks Ketetanggaan)

Bayangkan sebuah papan catur atau tabel silang Excel. Kita membuat tabel 2 Dimensi (Array 2D) berukuran V x V (jumlah simpul dikali jumlah simpul).

• Baris mewakili simpul asal.
• Kolom mewakili simpul tujuan.
• Isi Kotak (Sel) diisi angka 1 jika ada jalan yang menghubungkan keduanya, dan angka 0 jika buntu.

Contoh: Jika kita punya 3 kota: Jakarta (0), Bandung (1), dan Semarang (2). Misal, hanya ada jalan tol dari Jakarta ke Bandung, dan Bandung ke Semarang.

• Lihat baris Jakarta(0) dan kolom Bandung(1), nilainya adalah 1 karena ada jalan langsung.

• Lihat baris Jakarta(0) dan kolom Semarang(2), nilainya 0 karena tidak ada jalan langsung tanpa melewati Bandung.

• Kelebihan: Super cepat! Untuk mengecek apakah Jakarta terhubung ke Semarang, komputer hanya perlu melihat array di indeks peta[0][2]. O(1).

• Kekurangan: Boros memori. Jika Anda membuat peta dengan 10.000 titik simpul, Anda butuh tabel berukuran 100.000.000 kotak. Padahal di dunia nyata, graf cenderung renggang/sepi (mayoritas kotak hanya akan berisi angka 0).

2. Adjacency List (Senarai Ketetanggaan)

Alih-alih membuat tabel raksasa yang banyak kosongnya, kita membuat sebuah "Buku Kontak" (Phonebook) menggunakan gabungan Array dan Linked List.

• Kita buat Array untuk mendaftar setiap simpul.
• Di sebelah setiap simpul, kita tempelkan sebuah rantai Linked List yang HANYA berisi nama-nama simpul yang terhubung dengannya.

Contoh Visual:

• [Jakarta (0)] -> berteman dengan: [Bandung] -> NULL

• [Bandung (1)] -> berteman dengan: [Jakarta] -> [Semarang] -> NULL

• [Semarang (2)] -> berteman dengan: [Bandung] -> NULL

• Kelebihan: Sangat hemat memori! Komputer hanya mencatat jalan yang benar-benar ada. Sangat cocok untuk Facebook di mana dari 2 Miliar pengguna, rata-rata orang hanya memiliki 500 teman.

• Kekurangan: Sedikit lebih lambat untuk operasi pencarian spesifik. Untuk memastikan apakah A berteman dengan Z, komputer harus menelusuri rantai Linked List milik A satu per satu dari awal hingga menemukan si Z. O(V).

Membuat Peta dengan Adjacency Matrix

Mari perhatikan kode simulasi di atas. Kita menggunakan GraphMat yang berisi tabel Array 2D matrix[5][5].

int main() {
    GraphMat peta;
    CreateEmptyGraph(&peta);

    // 1. Daftarkan Kota (Simpul)
    AddVertex(&peta, "Jakarta"); // Indeks 0
    AddVertex(&peta, "Bandung"); // Indeks 1
    AddVertex(&peta, "Semarang");// Indeks 2

    // 2. Hubungkan Kota (Bangun Jalur)
    AddEdge(&peta, 0, 1); // Jakarta <-> Bandung
    AddEdge(&peta, 1, 2); // Bandung <-> Semarang
    
    // Cek koneksi
    if (peta.matrix[0][2] == 1) {
        cout << "Ada jalan langsung Jakarta-Semarang";
    } else {
        cout << "Tidak ada jalan langsung Jakarta-Semarang";
    }

    return 0;
}